Tarski and Hilbert's 10th

Thread View: sci.logic

1 messages

[T] Back to Threads [V] Tree View [G] Group Articles

1 total messages Started by Kevin Ruland Fri, 17 Apr 1992 00:07

#125

Author: Kevin Ruland
Date: Fri, 17 Apr 1992 00:07

18 lines
1177 bytes

Tarski proved that there is an algorith that can translate
any proposition in first order theory of the reals into
a quantifier free formula.  Now, Hilbert's 10th problem
(existance of solutions to diaphantane equations) is unsolvable.
That is there is no algorithm that can determine if an
arbitrary diaphantane equation has a solution.  This means that
there is no result similar to Tarski's for the "first order theory
of the integers".  Okay, everyone know this, but could someone
explain why?  What I mean to ask is what is there about the integers
that makes everything so much harder.  I realize that division might
have something to do with it but I can't lay my finger on the
problems.

Thanks.

Kevin Ruland
kevin@rodin.wustl.edu

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads