Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics.
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory.
Paul Richard Halmos was a Hungarian-born American mathematician and statistician who made fundamental advances in the areas of mathematical logic, probability theory, statistics, operator theory, ergodic theory, and functional analysis. He was also recognized as a great mathematical expositor. He has been described as one of The Martians.
In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time and correctly decides whether the number belongs to the set or not.
In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.
Robert Anthony Kowalski is an American-British logician and computer scientist, whose research is concerned with developing both human-oriented models of computing and computational models of human thinking. He has spent most of his career in the United Kingdom.
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem X a successively harder decision problem X′ with the property that X′ is not decidable by an oracle machine with an oracle for X.
In computability theory, a subset of the natural numbers is called simple if it is computably enumerable (c.e.) and co-infinite, but every infinite subset of its complement is not c.e.. Simple sets are examples of c.e. sets that are not computable.
In computability theory, productive sets and creative sets are types of sets of natural numbers that have important applications in mathematical logic. They are a standard topic in mathematical logic textbooks such as Soare (1987) and Rogers (1987).
In computability theory, the UTM theorem, or universal Turing machine theorem, is a basic result about Gödel numberings of the set of computable functions. It affirms the existence of a computable universal function, which is capable of calculating any other computable function. The universal function is an abstract version of the universal Turing machine, thus the name of the theorem.
Gerald Enoch Sacks was a logician whose most important contributions were in recursion theory. Named after him is Sacks forcing, a forcing notion based on perfect sets and the Sacks Density Theorem, which asserts that the partial order of the recursively enumerable Turing degrees is dense. Sacks had a joint appointment as a professor at the Massachusetts Institute of Technology and at Harvard University starting in 1972 and became emeritus at M.I.T. in 2006 and at Harvard in 2012.
S. Barry Cooper was an English mathematician and computability theorist. He was a professor of Pure Mathematics at the University of Leeds.
In computability theory, a Turing degree [X] is low if the Turing jump [X′] is 0′. A set is low if it has low degree. Since every set is computable from its jump, any low set is computable in 0′, but the jump of sets computable in 0′ can bound any degree recursively enumerable in 0′. X being low says that its jump X′ has the least possible degree in terms of Turing reducibility for the jump of a set.
The low basis theorem is one of several basis theorems in computability theory, each of which showing that, given an infinite subtree of the binary tree , it is possible to find an infinite path through the tree with particular computability properties. The low basis theorem, in particular, shows that there must be a path which is low; that is, the Turing jump of the path is Turing equivalent to the halting problem .
Carl Groos Jockusch Jr. is an American mathematician. He graduated from Alamo Heights High School in 1959, attended Vanderbilt University in Nashville, Tennessee, and transferred to Swarthmore College, Pennsylvania in 1960, where he received his B.A. in 1963 with Highest Honors. He then enrolled at the Massachusetts Institute of Technology. He is a member of Phi Beta Kappa and Sigma Xi. In 2014, he became a Fellow of the American Mathematical Society. He is a professor emeritus at the University of Illinois at Urbana–Champaign.
Albert Abramovich Muchnik was a Russian mathematician who worked in the field of foundations and mathematical logic.
In the mathematical field of computability theory, a PA degree is a Turing degree that computes a complete extension of Peano arithmetic (Jockusch 1987). These degrees are closely related to fixed-point-free (DNR) functions, and have been thoroughly investigated in recursion theory.
In computability theory, a Π01 class is a subset of 2ω of a certain form. These classes are of interest as technical tools within recursion theory and effective descriptive set theory. They are also used in the application of recursion theory to other branches of mathematics.
Rodney Graham Downey is a New Zealand and Australian mathematician and computer scientist, an emeritus professor in the School of Mathematics and Statistics at Victoria University of Wellington in New Zealand. He is known for his work in mathematical logic and computational complexity theory, and in particular for founding the field of parameterised complexity together with Michael Fellows.
Joseph Robert Shoenfield was an American mathematical logician.
