Church–Turing thesis

In computability theory, the Church-Turing thesis hypothetically formulates the equivalence between the concepts of computable function and Turing machine, which expressed in ordinary language would be "everything algorithm is equivalent to a Turing machine". It is not a mathematical theorem, it is a formally unprovable statement that, however, has practically universal acceptance.

Introduction

In the 1930s, one of the problems most studied by mathematicians was the Entscheidungsproblem proposed by David Hilbert: given a proposition in a formal system, is there such an algorithm that can decide whether the proposition is true (and why? is it both a theorem of the system) or is it false? In 1936 Alonzo Church and Alan Turing independently proved the impossibility of such an algorithm, using the lambda calculus in Church's case and the Turing machine in Turing's case. Subsequently, the initial concept of said "machine" (which has no physical existence, it is really a formal description) was amplified in various ways:

• Turing machines with more than one tape,
• Turing machines with n-dimensional tapes,
• Turing machines with a limited number of states and symbols,
• Probabilist Turing Machines,
• Non-determinist Turing machines.

The formal languages that are accepted by a Turing machine are all those that can be generated by a formal grammar. On the other hand, the functions that can be computed with Church's Lambda calculus are exactly those that can be computed with a Turing machine. These three formalisms, Turing machines, formal languages and Lambda calculus have been developed independently and yet have been proven to be equivalent; This notable coincidence seems to indicate that the Church-Turing thesis is true, the notion of algorithm or effective computation procedure being equivalent to the notion of computation in a Turing machine.

Among the formal languages that are accepted by a Turing machine are:

• finite automatons with two batteries;
• finite automatons with two counters;
• formal grammar;
• the Post System;
• Lambda calculation;
• partial recursive functions;
• cellular automatons: like the game of life of Conway or cell automaton with one dimension, two states, three cells per neighbor and rule 110;
• Quantum computers.

Where the last three examples use a slightly different Definition of language acceptance in that they accept a string if there is only one computation that accepts it or a majority accepts it and then it is Turing machine equivalent.

Why is it a thesis?

Although it is assumed to be true, the Church-Turing thesis cannot be proven since the necessary means are not available, which is why it is a thesis. This is because "effective procedure" and "algorithm" are not concepts within any mathematical theory and are not easily definable. The evidence of its truth is abundant but not definitive. Precisely Church's thesis establishes that the definition of effective algorithm or procedure is a Turing machine.

It has been agreed that an effective procedure or algorithm consists of a finite and precise number of steps described in a finite number of symbols that could also be executed by a human being. In general, the execution of an algorithm does not require more intelligence than the one necessary to understand and follow the instructions (even just follow).

Examples of effective methods or algorithms abound, for example addition, subtraction, multiplication or division are algorithms for arithmetic operations. Euclid's algorithm to obtain the greatest common divisor of two natural numbers is another example. However, none of this has been a formal definition as it is not clear what "precise instruction" means or what kind of intelligence is necessary to follow instructions. For this very reason, the abstract idea of a machine that functions as a parameter to decide when something is an effective algorithm or procedure is of great value. This is a Turing machine.

Thesis success

The Church-Turing thesis has been so successful that most assume it to be true. The terms derived from it, such as effective and computable method are commonly used, when actually computable refers to Turing-computable, in the jump between one and the other is Church's thesis, and among many other concepts and terms commonly used in the theory of computability or recursive functions.

Detractors

Clearly it is "easier" prove the falsity of the thesis than the truth of it. It is enough to expose an effective method or algorithm that is not computable in the Turing sense (i.e. Turing-computable).

Although exposing a non-Turing-computable algorithm is not that easy, but, it is "easier" to prove the truth of the thesis, since it seems impossible to deny that it is true even though that is a logical possibility.

There is a relativized Church-Turing thesis that depends on Turing degrees defined by Turing machines with oracles. Oracles are formal means that assume that certain information is provided to the Turing machine to solve a problem, this defines a hierarchy that has been studied both in Computability theory and in Complexity Theory.

Implications

The Church-Turing thesis also has profound implications. When the thesis is applied to physics, it has various meanings: that the universe is a Turing machine and therefore it is not possible to physically build a machine with greater computational power or that computes non-recursive functions (the computational capacity that can contain the universe is coupled to the type of universe in which we live). This has been called the strong Church-Turing thesis.

A possible valid interpretation is that the universe is not a Turing machine, that is, the laws of the universe are not computable but this does not affect the possibility of creating a machine more powerful than a Turing machine (power decoupled universe computing power of the devices it contains).

Another possibility is that the universe is a hypercomputer and then it is possible to build machines more powerful than Turing machines. For this, it would possibly be enough for the universe to be continuous and make use of that continuity (another question is how dense its continuity is), using the results of said super computer as input:

The universe or nature.