Software Development

Instead of asking about halting or not, let's try something simpler just so I can explain how absurd the Halting Problem really is. Let's assume ALL programs DO halt. Any program that doesn't halt is not considered. We leave those out. Instead of asking for a Halting Oracle, we will instead ask if it's possible for a Result Oracle to exist. If we give it any given program and its input, we want to know the output value.

Is it possible to create a Result Oracle?

Of course it is. You just run the given program. We know it will halt, so we'll get a result every time. Even so, I can use the Halting Problem Proof to 'prove' that it can't be done. And yet all programmers know that if you call a function that is known to halt, you will get a result.

How do I 'prove' that it can't be done? Well, we take advantage of a little property about functions. What is this property? Let me explain using the Socratic method.

Q: What is a function?
A: It's something that sets up a mathematical relationship between inputs and outputs.

Q: BEFORE you see any of the inputs, can you tell what the output will be?
A: No, of course not.

Q: So a function is undecidable?
A: Yes, that is by definition one of the properties of a mathematical relationship. (Note: the reader may look this up.)

Q: If you were to combine two functions, could you create a single function that is equivalent?
A: Yes.

Q: So even if you pass a function to another function, the aggregate would remain undecidable?
A: Yes, because compound functions are still functions.

In order to 'prove' that it's impossible to have a Result Oracle, I'm going to create a deceiver program P that calls Q (the Result Oracle) and asks what P will return. So whatever Q returns, P will add 1 and return that. This will mean that no matter what Q returns, it will always be wrong by one. Therefore the Result Oracle cannot exist. End of 'proof'.

We know for a fact that this is bogus. We can just run any function with its input and get a result. So why aren't we getting a valid result here? Well, we took advantage of the fact that functions are undecidable and made sure we provided no input that was decidable.

Basically, we end up with a compound function. What part of Q(P,Q) is decidable? None. They are all functions. A compound function is still a function and is undecidable. So all we did was refuse to produce a decidable input. A function without an actual input value can only produce another function. Otherwise, it doesn't have enough information and cannot execute.

And that's why the Halting Problem is bogus (undecidable inputs and forcing true/false as output). We just tackled a MUCH easier problem. One that we KNOW exists. The Result Oracle is today known as an Operating System (edit: or a CPU or a Universal Turing Machine).

The Halting Problem is unfortunately setting up its own answer from its formulation. A premise that gives its own answer is circular logic. In 350BC, this is what Aristotle called begging the question. BTW, you can incorrectly prove that God doesn't exist by this same method. Ask God what you will do and then do the opposite after you've been given an answer. No one or no thing can give you a correct answer as to what you will do, therefore there can be no God.

Not only is this patently absurd, but it's sad that it has been accepted as a genuine proof in computing since 1936.

The Halting Proof has a few other complications, but the essentials are that you are trying to convert undecidable inputs (P,Q) into a decidable output of true/false. This has nothing to do with halting, but rather with composability.

It's like connecting tubes to other tubes and asking if the water that comes out is hot or cold. There is no water. So there cannot be a valid answer. That's what's happening with programs composed in this manner. Composability breaks down when there is no actual input to match to output.

Some may say that P is never actually executed. It could be sent as text. The problem is that it's still undecidable because P is treated as a function. Q is interested in the BEHAVIOUR of P as a function. But even if it was a decidable input, you could merge it into Q and produce a new equivalent function R. So now you have R(Q). Here, you want to map a function Q to true/false. Can't be done because there is no decidable input to Q. Q is itself the input.

One important point!

Decidability is dependent on the interpretation of the input. If you treat it as a function where you want to know about its behaviour (especially its output), then it's undecidable (assuming you don't provide it any decidable input, and even then there is no guarantee). However, a function may be treated as decidable input if the entirety of it is used without regard to its behaviour. For example, a compiler taking text input and producing binary output. So the format is irrelevant. It's the interpretation that is paramount.

This is a mistake that many mathematicians make. The execution is irrelevant. So just because neither inputs to the Halting Oracle are executed does not change the fact that both inputs are treated as undecidable functions according to the definition of the Halting Oracle.

More than that, the deceiver program in the halting problem is impossible to execute. Sure, you can write the code for it. But you'll never be able to create ANY function that the deceiver can invoke. It's impossible to write a function that takes a function as input (and treats it as such) and gives out true/false. This has nothing to do with Oracles.

True that this conversion can be done in SOME cases where the input is not needed to make the determination. For example, we know that "return a+1;" halts regardless what the input is. But in the cases where the input is needed to make that determination, it's impossible to do since no decidable input is provided.

What the Halting Problem Proof does is create an incomplete program. It creates a compound function and then says, "Look, no input. Since you can't produce output without input, the Oracle can't exist". That's ALL the Halting Problem Proof says. Nothing more. Nothing less.

The Halting Problem Proof is, and always has been, a hoax. Circular logic can be VERY difficult to notice and the greatest minds of the past century have failed to notice it. It erroneously asks you to treat the input as decidable input. That error is the cause of circular logic. In other words, the Halting Proof is nothing more than a demonstration of this error. It is in effect eating its own tail.