Key Facts
- According to the Church-Turing thesis, a calculation method may only be considered systematic if it can be performed by a Turing machine.
- Although no calculation exists as yet which is beyond the capabilities of the Turing machine, the fact is that we are yet to exhaust every calculation which exists in the universe.
- As a result, its efficiency has been the subject of lively debate.
What is the Church-Turing Thesis?: A Complete Explanation
In simple terms, the Church-Turing Thesis, formerly known as “Church’s Thesis,” states that any computable function performed on natural numbers can be calculated by an effective method if, and only if, a Turing machine can perform the function.
The Church-Turing thesis is not easily broken down into layman’s terms, as it deals partly with graduate-level mathematical theory. However, it states that a calculation method can only be considered systematic if a Turing machine can perform it.
There is also a lot of debate as to whether the Church-Turing thesis stands the test of time. While there has yet to be a systematic calculation that the Turing machine can’t calculate, there are also plenty of things we don’t yet understand about our universe. In addition, the Church-Turing thesis does not have a designated mathematical proof (a mathematical statement showing that the given method logically guarantees the intended outcome).
So, there’s no designated “proof” that the Church-Turing thesis works. Rather than proving it works, we’ve yet to disprove its efficacy.
The Church-Turing Thesis: Exact Definition
The Church-Turing Thesis states that a computational method can only be considered effective if a Turing machine can complete it.
How Does the Church-Turing Thesis Work?
Now that’s a lot of math jargon, so let us break down what those words mean. “Effective” in this case does not carry the same meaning as it does outside for maths. What “effective” means in this situation is that the method of operation has a finite number of exact finite steps.
When applied to a problem of its class, it does the following:
- The method terminates (finishes) after a finite number of steps.
- The method always produces a correct answer.
- In principle, the solution must be achievable using nothing but writing materials. (This does not have to carry into practice).
- The method must need only to be followed rigorously to succeed. No creativity or additional knowledge should be necessary.
Now, the Church-Turing thesis goes a little deeper into what can be determined as an “effective” method by positing that methods are only “effective” if a Turing machine can perform them.
A Turing machine is a computational model that calculates numbers on a strip of tape using a table of rules. It’s a very simplistic machine in theory, yet it remains undefeated. The Turing machine has been able to calculate all mathematical problems put through it accurately.
In application, it would be challenging to test the efficacy of the Church-Turing thesis because the Turing machine is an abstract machine. However, abstract machines are theoretical models, not inventions that translate well into the real world.
Turing Complete Machines
However, in the modern day, we have a series of terms known as “Turing completeness,” which determines whether a machine can operate at the same capacity as the abstract model of the Turing machine. Additionally, modern technology has allowed us to build out the Turing machine with some adjustments to suit a real-world application of the design.
Turing completeness essentially measures how many functions a piece of technology can perform accurately. The Turing machine can complete any mathematical function at any level. To be Turing complete, a machine must be able to perform all mathematical functions at all levels. Machines that can perform a limited number of functions are incomplete, but that doesn’t mean they’re bad or worse than other machines. After all, the Turing machine is a theoretical model.
Calculators are considered “Turing incomplete” because they have a limited number of functions they can perform. However, personal computers are considered “Turing complete” because they have an unlimited number of functions they can perform.
Not Disproven, But Not Yet Proven
Since the Church-Turing thesis uses abstract machines, it’s naturally difficult to prove. However, while we don’t have an actual Turing machine available to test, we can use Turing complete machines to test whether otherwise effective mathematical functions against a Turing complete machine. Thus far, all effective parts put through a Turing complete machine are solvable.
It’s also worth noting that the Church-Turing thesis only applies mathematical functions that are considered effective. So this does not apply to most theoretical mathematics, and some higher mathematics won’t be covered by the Church-Turing thesis either.
However, since the Church-Turing thesis has not been given a mathematical proof, not all scholars agree that it is a valid mathematical truth, even if all applicable tests seem to point to it being true. People who believe that the Church-Turing thesis isn’t a mathematical truth tend to take the standpoint of the thesis being a definition for computation rather than a valid thesis.
How Was the Church-Turing Thesis Created?
The First Definition: Lambda Calculus
The history of the Church-Turing thesis takes us back to the 1930s. Then, when the most critical issue in theoretical mathematics was the potential introduction of a mechanical way of separating mathematical truths from mathematical falsehoods. This concept is known as the Entscheidungsproblem and was pioneered by Wilhelm Ackermann and David Hilbert.
Alonzo Church and his student Stephen Kleene began working on the Entscheidungsproblem. Church and Kleene introduced the concept of Lambda calculus. This classification showed that several large classes of calculations were lambda-definable.
The Debate Begins
The debate begins with Kurt Gödel, who worked with Jaques Herdbrand to define general recursive functions. Church suggested to Gödel that “effectively computable” functions should be lambda-definable. Gödel was not convinced that it was a practical solution and called the notion “thoroughly unsatisfactory.”
In correspondence between Gödel and Church circa 1934–1935, Gödel suggested that the idea of “effective computability” should be axiomatic rather than a simple definition. Gödel proposed that there should be multiple accepted axioms to solving effectively computable functions and that a function should only have to satisfy one of the axioms to be considered effectively computable.
Additionally, some problems are effectively computable using more than one function. More efficient functions can be used to solve some higher mathematics. For instance, it’s assumed that a quantum computer will reach a higher maths solution faster, more efficiently, and with lower complexity than a standard computer.
Gödel’s guidance on these axioms was limited as, at the time, he was not yet convinced that his theory of recursiveness could be applied to all recursive functions.
These functions would have to be proven to be equivalent as the next step to defining calculability. Working with Church and J. Barkley Rosser, Stephen Kleene produced proofs to show that Lambda calculus and recursion were equivalent functions.
Church also modified his methods to include Herdbrand-Gödel recursion, proving that the Entscheidungsproblem is unsolvable; no algorithm could determine whether a well-formed formula has a beta normal form.
Turing’s Involvement
By 1936, Turing’s paper, which showed that the Entscheidungsproblem was unsolvable, had been delivered orally but had yet to appear in print. Emil Post’s 1936 paper was also provided and certified independently of Turing’s paper.
Post’s paper dismissed the notion of “effective calculability” as a definition or an axiom. Instead, Post posited that the notion of effective calculability related to a natural law that was not yet discovered, a theory heavily criticized by Alonzo Church.
Turing’s paper introduced the a-machines, now known as the Turing machine. This theoretical machine was capable of completing any mathematical function that it performed by writing data on an infinitely long strip of film.
Turing would further define and put effort into “effective computability” by positing that the definition should be those functions that the Turing machine can solve. Finally, Turing would become sure of his definition of effective computability and, like Church and Kleene, publish his definition as the actual definition.
However, Rosser had better ideas. He equated the three notions as definitions of effective compatibility, stating that, “it does not matter which one is used as they are equivalent.”
Thesis I
Still, by this point, no thesis had been done regarding the concept of effective calculability. While many mathematicians had tried to define the concepts needed to determine effective calculability, they had yet to do a thesis statement on the direct terms of effective calculations.
Kleene then proposed Thesis I, which stated that all effectively calculable functions are generally recursive. Thus, Kleene sort of switched sides and took the notion of general recursiveness and applied it to the working definitions from Church and Turing. Since Rosser had already equated the three definitions, the only real work left to do was to join them into one coherent thesis, which was Kleene’s aim.
At this time, Church and Turing’s names had not yet been put to their work. However, the review of Thesis I found that the concept had compelling research and proofs behind it, suggesting that the thesis should be explored in more detail.
Kleene would then publish Introduction to Mathematics which formally defined Church’s Thesis and Turing’s Thesis, applying his theory of recursive realizability to them. This book and future books would be written using what would be called Gödel-Kleene recursiveness. Kleene modified Gödel’s theories of recursiveness to allow for proofs showing the unsolvability of problems presented in the Institutionism of E. J. Bouwer.
In Kleene’s graduate textbook, Kleene starts by introducing “Church’s Thesis,” which he shows are unrealizable problems. Then, he presents “Turing’s Thesis” and shows that the problems become uncomputable. He then equates the two theses using a simplified derivation of the Turing machine based on Emil Post’s work.
Finally, both theses are proven equivalent using Theorem XXX, which states that every effectively calculable function (effectively decidable predicate) is generally recursive. The following classes of partial functions are coextensive, i.e., have the same members: (a) the partial recursive functions, (b) the computable functions… and Turing’s thesis that every function which would naturally be regarded as computable is computable under his definition, i.e., by one of his machines, is equivalent to Church’s thesis by Theorem XXX.
Kleene ultimately coins the term, “Church-Turing thesis,” in a section in which he gives clarifications to concepts from Turing’s The Word Problem in Semi-Groups with Cancellation, which had been requested — nay, demanded — by Willaim Boone in a critique of the paper.
What are the Applications of the Church-Turing Thesis?
The Church-Turing thesis remains the subject of intense discussion and research. With modern improvements to computers and computation, there is use for the Church-Turing thesis as a method of defining computability in quantum and molecular computation. Additionally, the Church-Turing thesis is often used to define an algorithm in mathematics. It’s also used in solving the 10th Problem by Hilbert.
In truth, the Church-Turing thesis doesn’t have many applications people can see daily. While many of the background uses for the Church-Turing thesis apply to technology we have in our homes, the use of the Church-Turing thesis remains one that is primarily seen in theoretical mathematics, which is something by, for, and populated almost entirely by math geeks that go beyond the pale of standard mathematics.
Examples of the Church-Turing Thesis in the Real World?
The most poignant examples of the Church-Turing thesis in the real world are computing and higher mathematics. Notably, the Church-Turing thesis is used to define and research algorithms, define computation devices like molecular and quantum computers, and solve the 10th Problem by Hilbert, one of the primary problems posed to mathematicians as a problem that needed to be solved to make significant progress in the field of mathematics.
The 10th Problem by Hilbert
The 10th Problem by Hilbert was first proposed in 1900 as one of the problems that needed to be solved to make significant progress in mathematics. The 10th Problem posed the question of whether a process with a finite number of steps can determine if a given polynomial with integer coefficients and integral roots exists.
In 1970, it was proven that no such process exists.
Are All Algorithms Able to Be Completed by a Turing Machine?
There are many working definitions of an algorithm, and understanding the process behind them and what they are is integral to understanding the 10th Problem. Unfortunately, algorithms have a few significant definitions, many of which are now defunct.
For example, in 1936, an algorithm was defined as either a Lambda calculus function or a function that a Turing machine could perform. First, however, there is the famous halting problem with the Turing machine, which is a process that the machine performs with no indication of if or when the process will terminate.
Turing Conversion
Eventually, a definition of computability was coined and accepted, which posited that any computational process could be considered an algorithm as long as it could be converted to a Turing machine. However, it’s also worth noting that this definition is now defunct as situations such as the halting problem have disproven the idea that all algorithms can be converted to a Turing machine.
Despite this, the Church-Turing thesis remains a practical and straightforward way of determining a problem’s computability. While many problems may remain computable even if not convertible to a Turing machine, the Church-Turing thesis persists in its simplicity in dealing with a very complex concept.
Final Thoughts
While it may not be as practical as it once was, the Church-Turing thesis is an essential mathematical cornerstone that helps us better understand the mathematical world around us. While the definition of computability posed by the Church-Turing thesis may now be defunct, its processes and concepts are crucial to understanding higher mathematics.
The image featured at the top of this post is ©Sergey Tarasov/Shutterstock.com.