LESSWRONG
LW

684
Wikitags
Main
1
Evidence for the Church-Turing t
4
LW Wiki

Church-Turing thesis

Edited by Jaime Sevilla Molina, Eric Rogstad, et al. last updated 22nd Jul 2016

The Church-Turing thesis (often abbreviated CT thesis) states:

Every effectively computable function is Turing-computable

That is, for every function which can be computed by physical means [1] there exists a Turing machine which computes exactly that.

The Church-Turing thesis is not a definite mathematical statement, but an inductive statement which affirms that every sensible model of computation we can come up with is equivalent or at least reducible to the model proposed by Turing. Thus, we cannot prove it in a mathematical sense, but we can gather evidence for it.

For example, this model was proven to coincide with Church's lambda calculus, another universal model of computation, and the equivalence between Church's lambda calculus and Turing's automatic machines is often taken as evidence that they correctly capture our intuition of "effectively computable".

There are many consequences of the CT thesis for computer science in general, artificial intelligence, epistemology, and other fields of knowledge.

  1. ^︎

    So no hypercomputers

Parents:
Mathematics
Children:
Strong Church Turing thesis
Church-Turing thesis: Evidence for the Church-Turing thesis
Subscribe
Discussion
1
Subscribe
Discussion
1
Posts tagged Church-Turing thesis
58Epistemological Framing for AI Alignment Research
Ω
adamShimi
5y
Ω
7
37Claude 3 Opus can operate as a Turing machine
Gunnar_Zarncke
1y
2
28Algorithmic Similarity
Ω
LukasM
6y
Ω
10
15What is the evidence on the Church-Turing Thesis?
Q
Morpheus
4y
Q
19
Add Posts