Some strongly undecidable natural arithmetical problems, with an application to intuitionistic theories
Journal of Symbolic Logic 68 (1):262-266 (2003)
| Abstract | Although Church and Turing presented their path-breaking undecidability results immediately after their explication of effective decidability in 1936, it has been generally felt that these results do not have any direct bearing on ordinary mathematics but only contribute to logic, metamathematics and the theory of computability. Therefore it was such a celebrated achievement when Yuri Matiyasevich in 1970 demonstrated that the problem of the solvability of Diophantine equations is undecidable. His work was building essentially on the earlier work by Julia Robinson, Martin Davis and Hilary Putnam (1961), who had showed that the problem of solvability of exponential Diophantine equations is undecidable. One should note, however, that although it was only Matiyasevich’s result which finally solved Hilbert’s tenth problem, already the earlier result had provided a perfectly natural problem of ordinary number theory which is undecidable. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,653 |
| External links |
  Try with proxy. Try with proxy. Try with proxy. |
| Through your library | Configure |
Similar books and articlesMartin K. Solomon (1978). Some Results on Measure Independent Gödel Speed-Ups. Journal of Symbolic Logic 43 (4):667-672.
Thomas F. Kent (2006). The Π₃-Theory of the $\Sigma _{2}^{0}$ -Enumeration Degrees Is Undecidable. Journal of Symbolic Logic 71 (4):1284 - 1302.
Klaus Ambos-Spies, André Nies & Richard A. Shore (1992). The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable. Journal of Symbolic Logic 57 (3):864-874.
Aldo Ursini (1985). Decision Problems for Classes of Diagonalizable Algebras. Studia Logica 44 (1):87 - 89.
Yves Lafont (1996). The Undecidability of Second Order Linear Logic Without Exponentials. Journal of Symbolic Logic 61 (2):541-548.
Alfred Tarski (1968/2010). Undecidable Theories. Amsterdam, North-Holland Pub. Co..
Roger D. Maddux (1994). Undecidable Semiassociative Relation Algebras. Journal of Symbolic Logic 59 (2):398-418.
Roman Kontchakov, Agi Kurucz & Michael Zakharyaschev (2005). Undecidability of First-Order Intuitionistic and Modal Logics with Two Variables. Bulletin of Symbolic Logic 11 (3):428-438.
J. Siekmann & P. Szabó (1989). The Undecidability of the DA-Unification Problem. Journal of Symbolic Logic 54 (2):402 - 414.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads13 ( #87,816 of 548,984 )Recent downloads (6 months)3 ( #25,729 of 548,984 )How can I increase my downloads? |
My notes
Discussion
