Can this version of the halting problem be solved?

Question

I think the halting problem is not a result regarding computability, but rather expressiveness or restrictiveness. It's like asking a computer to prove $0=1$ or color a planar graph using only $3$ colors. To accommodate this lack of expressiveness, I propose to change the yes-no output options to these two:

• This program halts and it does not have a crossing structure.
• This program does not halt or it has a crossing structure.

The key here is that I merged the case "does not halt" and the case "has a crossing structure". And this will stop Rice's theorem from being able to be applied here.

Now, what is a crossing structure? It simply means that the input machine simulates the decider and does the opposite of its verdict.

So much for the definitions. My question is:

Is the halting problem solvable with these two output meanings?

My suspicion is that it's still not solvable, but yet it's consistent with all my test cases.

This is actually a paradox. The question is:

Is there a program with a crossing structure?

First suppose there is. Then this program will simulate me. Suppose I say you don't halt or you have a crossing structure. Then you must, in order to contradict me, halt and at the same time don't possess a crossing structure. Contradiction.

Next suppose there isn't any. Then "halt and don't possess a crossing structure" is equivalent to "halt" and "don't halt or possess a crossing structure" is equivalent to "don't halt". Then it's easy to contradict me, that is, there is a program possessing the crossing structure. Again, contradiction.

Answer 1

It simply means that the input machine simulates the decider and does the opposite of its verdict.

It is not that simple. "Simulating" is extremely vague.

Even if you fix it, there is another issue, with "does the opposite of its verdict".

Suppose you have a decider D for your problem. I give you a program P(X):

1. Run decider D on X(X)
2. If D says "not halts or has a crossing sequence", then halt
3. If D says "halts and does not have crossing sequence", then do some complicated loop

If step 3 contains a finite loop, the program surely halts.

If step 3 contains an infinite loop, then P simulates the decider and does the opposite of its verdict - so it has a crossing a sequence.

Let's ask the decider about P(P).

If the decider says that $P(P)$ halts, then the execution of $P(P)$ must go to step 3, and halt. In other words, the complicated loop is finite.

If the decider says that $P(P)$ does not halt or has a crossing sequence, then there are two cases:

• $P(P)$ does not halt. This is not possible, since because of D's answer in step 1 the program goes to step 2 and halts.

• $P(P)$ has a crossing sequence. This means that the program does the opposite of the verdict, so the loop in step 3 is infinite.

So if $D$ existed, you could use it to solve normal halting problem. Therefore the original problem is undecidable.

---

There is a lot of "partial halting problem deciders" - programs which always say "yes", "no", "don't know" correctly. For example, a program which always says "don't know", or a program which runs P for 100 seconds and says "yes" when halted, and "don't know" otherwise.

I disagree with your philosophy. Halting problem is about uncomputability. It means that we cannot perform general unbounded search over natural numbers. For example, there is no universal tool to prove Goldbach's conjecture, Fermat last theorem, odd perfect number conjecture etc. You have to use number theory to solve such problems. There is no apparent "crossing structure" in a program which searches for odd perfect number conjecture.

Do you remember Cantor's proof of uncountability of reals? There are MUCH more reals than naturals. Any attempt to find a surjection $\mathbb N \to \mathbb R$ will fail miserably - you will miss a LOT of numbers, much more than a single one found by diagonal reasoning. Any attempt to find an algorithm solving halting problem will also fail miserably - any "decider" will be wrong on lot of programs.

Answer 2

It will not be possible to define "has a crossing structure" broadly or precisely enough to make the halting problem be computably solvable.

For example, it is known that the following function is not computable: given a first-order sentence $\phi$, return $1$ if $\phi$ is provable and $0$ if $\phi$ is not provable, where "provable" means in one of the standard effective proof systems for first-order logic. This function can be shown to be noncomputable without already knowing that the halting problem is noncomputable, using the incompleteness theorems. (If this function was computable, we could use it to make a computable, complete extension of Robinson arithmetic, which cannot exist.)

Now for each $\phi$ we can make a program $e_\phi$ that simply searches for a proof of $\phi$, and halts if and only if $\phi$ does have a proof. None of these programs directly simulates another program - these programs just search for proofs, and in fact except for the particular formula being tested all of these programs have the same code. But it is not possible to computably solve even the special case of the halting problem for programs of this form.

We could try to define broader and broader notions of "crossing pattern", but these become vaguer and vaguer as they become more general. In particular, it is difficult to see how to make a precise definition of "crossing pattern" that would cover the example of the programs I gave above.