patternModerate
Does Church-Turing thesis also apply to artificial intelligence?
Viewed 0 times
thesisapplyartificialalsointelligencedoeschurchturing
Problem
By Church-Turing's thesis, it is impossible to design an algorithm to decide the halting problem.
Does the word algorithm in this context include artificial
intelligence or not, that is, does Church-Turing thesis also apply to artificial intelligence?
Is it possible to design an intelligence system in the future to decide this problem, or, by Church-Turing thesis, no AI will also be able to decide the halting problem?
Does the word algorithm in this context include artificial
intelligence or not, that is, does Church-Turing thesis also apply to artificial intelligence?
Is it possible to design an intelligence system in the future to decide this problem, or, by Church-Turing thesis, no AI will also be able to decide the halting problem?
Solution
The Church-Turing thesis says that the informal notion of an algorithm as a sequence of instructions coincides with Turing machines. Equivalently, it says that any reasonable model of computation has the same power as Turing machines.
An artificial intelligence is a computer program, i.e., an algorithm. If the Church-Turing thesis holds, then you could implement that algorithm on a Turing machine. Since Turing machines cannot decide their own halting problem, it follows that, under the Church-Turing thesis, artificial intelligences cannot decide the halting problem for Turing machines.
An artificial intelligence is a computer program, i.e., an algorithm. If the Church-Turing thesis holds, then you could implement that algorithm on a Turing machine. Since Turing machines cannot decide their own halting problem, it follows that, under the Church-Turing thesis, artificial intelligences cannot decide the halting problem for Turing machines.
Context
StackExchange Computer Science Q#40657, answer score: 18
Revisions (0)
No revisions yet.