The Gödel Incompleteness Theorem and Decidability over a Ring

Lenore Blum and Steve Smale

Chapter 32 in From Topology to Computation: Proceedings of the Smalefest, 1993, pp 321-339 from Springer

Abstract: Abstract Here we give an exposition of Gödel’s result in an algebraic setting and also a formulation (and essentially an answer) to Penrose’s problem. The notions of computability and decidability over a ring R underly our point of view. Gödel’s Theorem follows from the Main Theorem: There is a definable undecidable set ovis Z. By way of contrast, Tarski’s Theorem asserts that every definable set over the reals or any real closed field R is decidable over R. We show a converse to this result: Any sufficiently infinite ordered field with this latter property is necessarily real closed.

Keywords: Finite Extension; Incompleteness Theorem; Real Closed Field; Computable Isomorphism; Weak Conjecture (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-2740-3_32

Ordering information: This item can be ordered from
http://www.springer.com/9781461227403

DOI: 10.1007/978-1-4612-2740-3_32

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().