Church-Turing thesis
The Church-Turing thesis states the equivalence between the mathematical concepts of algorithm or computation and Turing-Machine. It asserts that if some calculation is effectively carried out by an algorithm, then there exists a Turing machines which will compute that calculation.
The notion of algorithm, computation, a step-by-step procedure or a defined method to perform calculations has been used informally and intuitively in mathematics for centuries. However, attempts to formalize the concept only begun in the beginning of the 20th century. Three major attempts were made: λ-calculus, recursive functions and Turing Machines. These three formal concepts were proved to be equivalent; all three define the same class of functions. Hence, Church-Turing thesis also states that λ-calculus and recursive functions also correspond to the concept of computability. Since the thesis aims to capture an intuitive concept, namely the notion of computation, it cannot be formally proven. However, it has gain widely acceptance in the mathematical and philosophical community.
The thesis has been wrongly attributed to many controversial claims in philosophy, that although related are not implied in the original thesis. Some examples are:
- The universe is equivalent to a Turing Machine and non-computable functions are physically impossible.[1]
- The universe isn’t equivalent to a Turing Machine and incomputable.[2]
- The human mind is a Turing Machine, the human mind and/or consciousness are equivalent to and can be instantiated by a computer. [3]
- The human mind isn’t a Turing Machine, the human mind and/or consciousness emerge due to the existence of incomputable process, such as microtubules performing quantum process in the brain.[4]