Computability theory

Some tasks are easy for a machine. We can give it steps to follow. These steps are called an algorithm. But some tasks are too hard. A machine cannot solve them. This is a big idea in math.

People like Alan Turing studied this. He thought about how machines work. He found that some problems have no answer. A machine can never find the answer. This helps us know what math can do. It shows us what is possible.

Math can be very tricky. Some things cannot be decided. This means no set of steps works. Even the smartest machines cannot do it. We can study these hard problems. It is a way to learn about math.

Can a machine solve every math problem? This is the main question in computability theory. This field began in the 1930s. Many smart people worked on it. These people include Alan Turing and Kurt Gödel. They wanted to know what math can actually do.

They found that some tasks are impossible. These tasks have no answer that a machine can find. We call these undecidable problems. For example, there is no way to tell if every math statement is true or false. This was a big discovery. It showed that math has limits.

A machine uses a set of steps called an algorithm. Some sets of numbers are computable. This means a machine can sort them. Other sets are not computable. The halting problem is a famous example. It asks if a machine will ever stop its work. We now know a machine cannot always answer this.

Math thinkers also study how hard problems are. They use something called an oracle. An oracle is like a magic helper. It can answer questions that a normal machine cannot. This helps us rank how hard a problem is. This ranking is called a Turing degree.

Computability theory is a branch of math and computer science. It asks if a machine can solve certain problems. This field looks at functions and sets of numbers. It explores what can be done with a set of steps. These steps are called an algorithm. Some tasks are easy for an algorithm to finish. Other tasks are impossible for any machine to solve. This study helps us understand the limits of math.

To understand this, we look at how machines work. Alan Turing introduced a model called a Turing machine. A set of numbers is computable if a machine can sort them. The machine follows a rule to give an answer. For example, it might output a one or a zero. If a machine can always find the answer, the set is decidable. But some sets are not computable at all. The halting problem is a famous example of this. It asks if a machine will ever stop its work.

Many famous thinkers built this field in the 1930s. Kurt Gödel, Alonzo Church, and Alan Turing were leaders. They worked on the idea of effective calculation. In 1952, Stephen Kleene named two important ideas. These are known as Church's thesis and Turing's thesis. Today, we call them the Church–Turing thesis. This idea says that any algorithm can be done by a computable function. Even Kurt Gödel changed his mind to support this idea by 1946.

Researchers found many problems that have no solution. In 1936, Church and Turing showed some things are undecidable. This means no algorithm can decide if a math statement is true. In 1947, Markov and Post showed a problem with semigroups. Later, in the 1950s, Novikov and Boone studied groups. They showed the word problem for groups cannot be solved. In 1970, Yuri Matiyasevich solved Hilbert's tenth problem. He proved there is no way to solve certain equations.

We can also rank how hard problems are. This is done using something called an oracle. An oracle is a hypothetical helper for a machine. It can answer questions that a normal machine cannot. This helps us find the Turing degree of a problem. This degree measures how uncomputable a set is. In 1954, Kleene and Post found intermediate degrees. This means some problems are harder than others. This study helps us see the structure of math.

Computability theory is a specialized branch of mathematical logic and computer science. It focuses on the theory of computation and the study of computable functions. This field investigates which mathematical constructions can be effectively performed through specific steps. Researchers explore the boundaries between what can be solved by a machine and what cannot. It overlaps with other complex areas like proof theory and effective descriptive set theory. By studying these limits, mathematicians understand the fundamental nature of calculation itself.

To understand this field, one must look at the mechanism of a Turing machine. This model was introduced by Alan Turing in 1936 to formalize the idea of effective calculation. A set of natural numbers is considered computable, or decidable, if a Turing machine can process it. If given a number *n*, the machine must halt and output 1 if the number is in the set. If the number is not in the set, the machine must halt and output 0. A function is also computable if a Turing machine can return the correct result for any input. While Turing machines are the primary model, other systems like μ-recursive functions possess the same computing power.

Computability theory distinguishes between different types of sets and functions. A computable set is often called a recursive set. There are also computably enumerable (c.e.) sets, which are also known as recursively enumerable or semidecidable sets. A set is computably enumerable if a Turing machine can produce an infinite list of its members. This means the set is the range of some computable function. However, being computably enumerable does not guarantee that a set is decidable. The halting problem is a famous example of a set that is computably enumerable but not computable.

The history of this field began in the 1930s with several key figures. Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene, and Emil Post all contributed to its origins. In 1936, Church and Turing independently proved that certain problems are not effectively decidable. This meant no algorithmic procedure could correctly determine if any mathematical proposition is true or false. In 1952, Kleene coined the terms "Church's thesis" and "Turing's thesis." These are now combined into the Church–Turing thesis. This hypothesis states that any function computable by an algorithm is a computable function.

Many specific mathematical problems have been proven undecidable over the decades. In 1947, Markov and Post published papers showing the word problem for semigroups is undecidable. During the 1950s, Pyotr Novikov and William Boone independently showed the word problem for groups is also not effectively solvable. This means no procedure can decide if a word in a finitely presented group represents the identity element. In 1970, Yuri Matiyasevich proved that Hilbert's tenth problem has no effective solution. This settled the question of whether a procedure could decide if a Diophantine equation has integer solutions.

Researchers also use the concept of relative computability to rank the difficulty of problems. This involves a hypothetical device called an oracle Turing machine. An oracle machine can ask a specific set of questions to an "oracle." The oracle provides instant, correct answers even if the set is not computable. This allows scientists to study how one set can be reduced to another. If set A is Turing reducible to set B, an oracle machine using B can solve A. This relationship helps define the Turing degree, which measures a set's specific level of uncomputability.

The study of these degrees reveals a highly complex and non-trivial structure. In 1944, Post asked if every c.e. set was either computable or equivalent to the halting problem. This became known as Post's problem. In 1954, Kleene and Post showed that intermediate Turing degrees do exist. Later, Friedberg and Muchnik independently solved Post's problem by proving the existence of intermediate c.e. degrees. Today, research continues into the overall structure of Turing degrees and the relationship between the Turing jump and the arithmetical hierarchy.