Turing reduction

In the field of computability theory, a Turing reduction is a powerful way to compare the difficulty of two problems. It is a mathematical method used to show that one problem is no harder than another. If we have a decision problem, we can solve it by using an oracle machine. This machine acts as an algorithm that has access to a special subroutine. This subroutine is called an oracle, and it provides instant answers to a specific problem. By using these answers, the machine can solve its own problem in a finite number of steps.

The mechanism of a Turing reduction works through a process of querying. Imagine you are running an algorithm to solve problem A. During the process, your algorithm reaches a point where it needs information about problem B. Instead of solving B itself, the algorithm asks the oracle for the answer. This oracle acts as a perfect source of information for problem B. If a Turing reduction from A to B exists, then every algorithm for B can be used to build an algorithm for A. You simply take the algorithm for B and insert it wherever the oracle machine would have made a query. However, this process might take much longer than the original algorithms. The resulting process may require more time asymptotically than either the original algorithm for A or the oracle machine for B.

There are several different types of reductions that vary in their strictness. A Turing reduction where the oracle machine runs in polynomial time is called a Cook reduction. This is important for studying computational complexity. Other, more restrictive versions include many-one reductions. In a many-one reduction, an element is in set A if and only if its transformed version is in set B. There are also truth table reductions and weak truth table reductions. In a truth table reduction, the machine must present all its oracle queries at the same time. It then uses a Boolean function to turn those answers into a final result. A weak truth table reduction is a "bounded Turing" reduction. In this version, the use of the reduction is limited by a computable function.

The history of these ideas involves several key mathematicians. Alan Turing provided the first formal definition of relative computability in 1939. He described it using the concept of oracle machines. Later, Stephen Kleene developed an equivalent concept using recursive functions in 1943 and 1952. In 1944, Emil Post introduced the specific term "Turing reducibility." These thinkers were trying to understand how different sets of numbers relate to one another through computation. Their work laid the foundation for how we categorize the complexity of mathematical problems today.

We can use these reductions to group problems into specific categories. If two sets are Turing equivalent, it means they can be reduced to each other. We call these groups of equivalent sets "Turing degrees." The degree of a set is written as the symbol d. We can also identify sets that are "Turing hard" for a certain class. If a set is both Turing hard and belongs to that class, it is called "Turing complete." This concept is closely related to computational universality. A machine is a universal Turing machine if its halting problem is many-one complete for the set of recursively enumerable sets.

There are several fascinating properties of Turing reducibility. First, every set is Turing equivalent to its own complement. Second, any computable set is Turing reducible to every other set. This is because a computable set can be solved without any oracle at all. The relationship is also transitive. This means if A is reducible to B, and B is reducible to C, then A is reducible to C. However, the relationship is not a total order. There are pairs of sets where A cannot be reduced to B, and B cannot be reduced to A. Additionally, there are infinite decreasing sequences of sets under this relation.

Finally, Turing reductions connect to much broader mathematical systems. They help us understand the limits of what can be calculated. For example, every set is reducible to its own Turing jump. However, the Turing jump of a set is never reducible back to the original set. This shows a clear hierarchy of difficulty. We also see these ideas in set theory through the notion of relative constructibility. Even weaker reductions exist, such as when a set is defined by a formula of Peano arithmetic. These layers of complexity help mathematicians map the entire landscape of what is possible to know through computation.