Open main menu

Wikipedia β

Changes

Mathematical logic

334 bytes added, 3 months ago
Recursion theory: added Rózsa Péter and source
{{Main|Recursion theory}}
 
'''[[Recursion theory]]''', also called '''computability theory''', studies the properties of [[computable function]]s and the [[Turing degree]]s, which divide the uncomputable functions into sets that have the same level of uncomputability. Recursion theory also includes the study of generalized computability and definability. Recursion theory grew from the work of [[Rózsa Péter]], [[Alonzo Church]] and [[Alan Turing]] in the 1930s, which was greatly extended by [[Stephen Cole Kleene|Kleene]] and [[Emil Leon Post|Post]] in the 1940s.<ref>{{cite web|last1=Soare|first1=Robert Irving|title=Computability Theory and Applications: The Art of Classical Computability|url=http://www.people.cs.uchicago.edu/~soare/Turing/frontice.pdf|website=Department of Mathematics|publisher=University of Chicago|accessdate=23 August 2017|date=22 December 2011}}</ref>
 
Classical recursion theory focuses on the computability of functions from the natural numbers to the natural numbers. The fundamental results establish a robust, canonical class of computable functions with numerous independent, equivalent characterizations using [[Turing machine]]s, [[lambda calculus|&lambda; calculus]], and other systems. More advanced results concern the structure of the Turing degrees and the [[lattice (order)|lattice]] of [[recursively enumerable set]]s.