0
$\begingroup$

Here's Alan Turing's halting problem in pseudocode:

function halts(f: Function, input: any): boolean {
  // Some logic that can supposedly solve the halting problem
  // ...
}

// A function that takes itself as an argument and does the opposite of what halts says
function paradox(f: Function, input: any) {
  if (halts(f, input)) {
    while (true) {}
  } else {
    return;
  }
}

halts(paradox, paradox); // returns false

In line 1 of paradox, we have to detether or not paradox is halting. However, halts will also recognize that we're attempting to call paradox with paradox as a parameter, therefore invoking infinite recursion, therefore paradox is non-halting.

Where's the problem?

$\endgroup$
2
  • 1
    $\begingroup$ Why do you say halts will also recognize that we're attempting to call paradox with paradox as a parameter? halts is generic function that decides the halting problem, we don't care how this is done. Notice that halts always returns either true or false and cannot run forever (otherwise it wouldn't decide the halting problem). Now either halts reports that paradox(paradox) halts, but (by definition of paradox) this is absurd since, in this case, the while(true) {}' line reached, or halts` reports paradox(paradox) as non halting, but then you can check that it halts. $\endgroup$
    – Steven
    Commented Apr 20, 2023 at 17:56
  • $\begingroup$ to expand on Steven's comment, if someone did invent a halting decider, it wouldn't actually call the function it was analyzing. It would analyze the source code using some algorithm. There is no recursion halts(func, input) would not call func(input). (If you try to invent a halting decider that does call it, well, now you know why that won't work) $\endgroup$ Commented Jul 27, 2023 at 8:31

1 Answer 1

3
$\begingroup$

However, halts will also recognize that we're attempting to call paradox with paradox as a parameter, therefore invoking infinite recursion

You seem to have a particular implementation of halts in mind. Also, your reasoning is not correct even assuming that implementation.

Remember that the proof works for any possible implementation, it doesn't matter what the actual implementation is.

As for where your reasoning is incorrect, you seem to think that if halts can check for a function calling itself, then that means it will detect an infinite loop. This is not the case. There are many functions that do not infinite loop when calling themselves; for example

function foo(x):
    if x == foo:
        print "Called foo on input foo!"
    return

Additionally, halts cannot just look into the implementation to see whether paradox(paradox) infinite loops, because if it does so, it will find that the infinite loop while (true) is guarded by a call to halts(paradox, paradox). So, there is no trivial implementation of halts that works here. Indeed, the whole point of Turing's proof is to show that no such implementation of halts exists.


P.S.: You have a typo in your pseudocode. The paradoxical function should only take one argument and call it on itself:

function paradox(f: Function) {
  if (halts(f, f)) {
    while (true) {}
  } else {
    return;
  }
}
$\endgroup$

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.