[Solved]: Does Church's Thesis include artificial intelligence?

Problem Detail: 

By Church's Thesis it is impossible to design an algorithm to decide halting problem. I would like to know the word algorithm in this context includes artificial intelligence or not? I mean is it possible to design an intelligence system in the future to decide this problem or by Church's Thesis this option is also impossible?

Asked By : Drupalist

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40657

3.2K people like this

 Download Related Notes/Documents