7
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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
    Commented Mar 23, 2015 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
    Commented Mar 23, 2015 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$
    – M a m a D
    Commented Mar 23, 2015 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
    Commented Mar 23, 2015 at 10:17

1 Answer 1

Reset to default
18
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Jul 20, 2017 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
    Commented Jul 20, 2017 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
    Commented Jul 20, 2017 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
    Commented Jul 21, 2017 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
    Commented Apr 3, 2018 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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