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?

  • 2
    $\begingroup$ 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.) $\endgroup$ – Raphael Mar 23 '15 at 7:03
  • $\begingroup$ Why do you think it possible that artificial intelligence might not be covered (or concerned) by Charch-Turing Thesis? $\endgroup$ – babou Mar 23 '15 at 8:46
  • $\begingroup$ @babou because it includes non determinism, learning, etc. There are non solvable problems that AI gives us very good approximation of the solution. $\endgroup$ – No one Mar 23 '15 at 8:49
  • 4
    $\begingroup$ @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. $\endgroup$ – Roy O. Mar 23 '15 at 10:17

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.

  • $\begingroup$ On the other hand, if the AI was written on some sort of analogue computer, or nonuniform infinite circuit, then the Halting problem for Turing machines is back on the board. $\endgroup$ – DanielV Jul 20 '17 at 3:55
  • 3
    $\begingroup$ @DanielV A non-uniform infinite circuit doesn't help. If it has a computable description, it can't solve the halting problem; if it doesn't have a computable description, you can't build it. $\endgroup$ – David Richerby Jul 20 '17 at 19:51
  • $\begingroup$ You can't build it with a Turing Machine. That doesn't mean it doesn't mean that it's existence is any more paradoxical than 2 points being an arbitrary distance apart. $\endgroup$ – DanielV Jul 20 '17 at 20:41
  • 2
    $\begingroup$ @DanielV How are you going to tell your electrician what gates to put in the $n$th circuit if there's no computable description? $\endgroup$ – David Richerby Jul 21 '17 at 0:57
  • 1
    $\begingroup$ @DanielV There are some problems you simply cannot compute. You need to be able to decide when you've solved the problem, just as well as what the answer is. In the case of the halting problem, there is no way to determine that you have solved the problem, let alone figure out what the answer is. $\endgroup$ – Clearer Apr 3 '18 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.