Is the halting problem still an open problem

fake-proofssolution-verificationturing-machines

(Spoiler: Turing was right!)

I was thinking about Turing's proof that the halting problem is undecidable. But can the paradox, which is often given as a proof, be broken?

Proof that a single program cannot decide the halting problem

First, I want to repeat the paradox in my own words:

Let source be the source code of a program, args some arguments to that program, and eval(source, args) an instruction that executes the program with the given arguments. Assume we had a program will_halt(source, args) that returns True if and only if eval(source, args) halts. Consider the program:

def p(source):
    while will_halt(source, (source)):
        pass  # endless loop
    return 42

p would run forever if will_halt(source of p, (source of p)) returns True, and halts otherwise. will_halt is faced with a conflict for the input (source of p, (source of p)). Turing concludes, will_halt cannot exist, because for any program will_halt a program p can be constructed that creates a conflict.

Resolving the conflict using two programs

will_halt must reason somehow whether loops terminate or not. It runs into a conflict for some inputs. However, we can define will_halt_or_true that returns True if and only if a conflict is encountered. Now, consider the following program:

def probe(source, args):
    while not will_halt_or_true(source, args):  # here we use 'not'!
        pass
    return eval(source, args)  # actually execute the program in question!

probe(source, args) behaves as follows:

will_halt_or_true(source, args) Conflict eval(source, args) probe(source, args)
True No Halts Halts
False No Runs forever Runs forever
True Yes Runs forever Runs forever

We can use probe to distinguish the conflict from the non-conflict case. will_halt_or_true(probe, (source, (args))) returns True if and only if eval(source, args) halts. Note, that a single program running will_halt_or_true(probe, (source, (args))) is as powerful as running will_halt_or_true directly. So, the decision process always involves two steps and cannot be reduced to one.

Conclusion (false)

My main argument is that no single program can decide the halting problem but two might. Knowing how will_halt_or_true handles conflicts enables us to construct a probe to decide the halting problem. This is by no means a proof that will_halt exists, but I argue that the "common" proof is not sufficient to claim that the halting problem is undecidable.

Edit

I distinguished will_halt from will_halt_or_true to be more clear. However, I found the following counter example, which is quiet obvious:

def q(args):
    while will_halt_or_true(probe, (args, (args))):
        pass
    return 42

Any value contributed to will_halt_or_true(probe, (source of q, (source of q))) will lead to a contradiction. So, will_halt_or_true(probe, ...) cannot be used. Yesterday it worked 😉

Best Answer

With your approach, the assumption on will_halt that you start out with "Assume we had a program will_halt(source, args) that returns True if eval(source, args) halts and False otherwise." does not hold anymore: there are cases where evaluating source runs forever, but your will_halt returns True. So, whatever you do afterwards does not address the halting problem anymore, because that starts out with your (original) assumptions.

(As an aside, note that it is trivial to write a will_halt function that returns True if the eval(source,args) terminates and without restriction on the return value if eval(source,args) does not terminate. It's useless, though.)

Related Question