Halting problem proofs refuted (H exists)

22 views
Skip to first unread message

Mr Flibble

unread,
Aug 11, 2022, 1:42:30 PMAug 11
to
Hi!

I have an idea for a signaling simulating halt decider that forks the
simulation into two branches if the input calls the halt decider as
per [Strachey 1965]'s "Impossible Program":

void P(void (*x)())
{
if (H(x, x))
infinite_loop: goto infinite_loop;
return;
}

int main()
{
std::cout << "Input halts: " << H(P, P) << std::endl;
}

When the simulator detects the call to H in P it forks the simulation
into a non-halting branch (returning 0 to P) and a halting branch
(returning 1 to P) and continues the simulation of these two branches
in parallel.

If the non-halting branch is determined to halt AND the halting branch
is determined to not halt then pathology is detected and reported via
a sNaP (signaling Not a Program) signal (analogous to IEEE 754's
sNaN (signaling Not a Number) signal)

If EITHER branch is determined to be correctly decided then that will
be the decision of the halting decider.

Crucially this scheme will handle (and correctly decide) the
following case whereby the result of H is discarded by the input:

void Px(void (*x)())
{
(void) H(x, x);
return;
}

Obviously my idea necessitateS extending the definition of a halt
decider:

1) Decider decision is HALTS if input halts.
2) Decider decision is NON-HALTING if input does not halt.
3) Decider rejects pathological input as invalid by signaling sNaP.

Thoughts? I am probably missing something obvious as my idea
appears to refute [Strachey 1965] and associated HP proofs which
great minds have mulled over for decades.

Ben Bacarisse

unread,
Aug 11, 2022, 4:01:00 PMAug 11
to
Mr Flibble <fli...@reddwarf.jmc.corp> writes:

> Obviously my idea necessitateS extending the definition of a halt
> decider:
>
> 1) Decider decision is HALTS if input halts.
> 2) Decider decision is NON-HALTING if input does not halt.
> 3) Decider rejects pathological input as invalid by signaling sNaP.
>
> Thoughts? I am probably missing something obvious as my idea
> appears to refute [Strachey 1965] and associated HP proofs which
> great minds have mulled over for decades.

Stachey was writing about halt deciders, not partial deciders. Just
like the last time you posted this.

--
Ben.

Paul N

unread,
Aug 11, 2022, 4:11:38 PMAug 11
to
I think he's trying to parody Olcott, though I could be wrong...

It could explain why he's put in a new post which seems to be identical to a previous one.

Mr Flibble

unread,
Aug 11, 2022, 4:18:12 PMAug 11
to
I think parodying Olcott is a great idea: satire is the best weapon
against the immovable bad.

/Flibble

Ben Bacarisse

unread,
Aug 11, 2022, 5:16:14 PMAug 11
to
Oh, I wish it were so easy to tell. But I like your idea and will run
with it.

Great work Mr Flibble! Hilarious.

--
Ben.

Richard Damon

unread,
Aug 11, 2022, 11:26:27 PMAug 11
to
As has been mentioned below, you need to work up exactly how you are
going to define the term "pathological input".

Also, it doesn't actually "refute" those proofs, because you don't show
them to be incorrect, as those statement include their definition of a
Halt Decider and Halting that you don't match, so you have a disconnect.
Reply all
Reply to author
Forward
0 new messages