# Does Church-Turing thesis also apply to artificial intelligence?

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?

• It's unlikely that an AI system can decide anything (in the formal, deterministic sense), but if it could it would certainly violate either the Church-Turing thesis or undecidability of the Halting problem. (The latter if it's writting in a Turing-complete language, the former otherwise.) – Raphael Mar 23 '15 at 7:03
• Why do you think it possible that artificial intelligence might not be covered (or concerned) by Charch-Turing Thesis? – babou Mar 23 '15 at 8:46
• @babou because it includes non determinism, learning, etc. There are non solvable problems that AI gives us very good approximation of the solution. – M a m a D Mar 23 '15 at 8:49
• @Drupalist: but decidability of some problem just means that there exists an algorithm such that for any given input from the input space of the problem, the correct output will be produced. So yes, an AI algorithm (or any other algorithm) might give good approximations for the halting problem, but this will not entail decidability. – Roy Mar 23 '15 at 10:17

• @DanielV How are you going to tell your electrician what gates to put in the $n$th circuit if there's no computable description? – David Richerby Jul 21 '17 at 0:57