AI ALIGNMENT FORUM
AF

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
1
Subscribe
1
Discussion0
Discussion0
Posts tagged Church-Turing thesis
24Epistemological Framing for AI Alignment Research
adamShimi
4y
7
16Algorithmic Similarity
LukasM
6y
9
Add Posts