Computability Theory

Valentina Harizanov (), Keshav Srinivasan () and Dario Verta ()
Additional contact information
Valentina Harizanov: George Washington University, Department of Mathematics
Keshav Srinivasan: George Washington University, Department of Mathematics
Dario Verta: George Washington University, Department of Mathematics

A chapter in Handbook of the History and Philosophy of Mathematical Practice, 2024, pp 1933-1961 from Springer

Abstract: Abstract Computability theory is the mathematical theory of algorithms, which explores the power and limitations of computation. Classical computability theory formalized the intuitive notion of an algorithm and provided a theoretical basis for digital computers. It also demonstrated the limitations of algorithms and showed that most sets of natural numbers and the problems they encode are not decidable (Turing computable). Important results of modern computability theory include the classification of the computational difficulty of sets and problems. Arithmetical and hyperarithmetical hierarchies and the Turing degrees provide important measures of the level of such difficulty. There are uncountably many Turing degrees and they are partially ordered. These classifications are used in contemporary research to investigate the complexity of problems in modern computable mathematics, for example, regarding structures and their properties.

Keywords: Turing machine; Partial recursive; Recursively enumerable; Diophantine; Undecidable problems; Arithmetical; Hyperarithmetical; Turing degree; Computable structure; Computable formulas (search for similar items in EconPapers)
Date: 2024
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-3-031-40846-5_101

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

DOI: 10.1007/978-3-031-40846-5_101

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 ().