Tarski and Hilbert's 10th

Article View: sci.logic

Article #125

#125

From: 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

Technical Details

Message-ID: <1992Apr17.000716.21300@wuecl.wustl.edu>

Path: arc1-ca.pugleaf.net!sparky!uunet!wupost!eclnews!kevin

Show Full Headers

Complete Article Headers

Newsgroups: sci.logic
Path: arc1-ca.pugleaf.net!sparky!uunet!wupost!eclnews!kevin
From: kevin@rodin.wustl.edu (Kevin Ruland)
Subject: Tarski and Hilbert's 10th
Message-ID: <1992Apr17.000716.21300@wuecl.wustl.edu>
Originator: kevin@rodin
Sender: kevin@rodin (Kevin Ruland)
Nntp-Posting-Host: rodin
Organization: Center for Optimization and Semantic Control, Washington University
Date: Fri, 17 Apr 1992 00:07:16 GMT
Lines: 19