On 7/19/2021 9:35 AM, Charlie-Boo wrote:
> On Thursday, July 15, 2021 at 1:22:19 PM UTC-4, Mr Flibble wrote:
>> Hi!
>>
>> From Wikipedia Halting Problem page:
>>
>> For any program f that might determine if programs halt, a
>> "pathological" program g, called with some input, can pass its
>> own source and its input to f and then specifically do the
>> opposite of what f predicts g will do. No f can exist that
>> handles this case.
>>
>> To me this looks like everyone is assuming that the halting problem is
>> undecidable based on a misunderstanding of the contradiction
>> crystallized by [Strachen 1965].
>>
>> Strachen isn't saying the halting problem is undecidable, he is saying that
>> there is a contradiction that means that a decider can not be a part of
>> or called by that which is being decided. This doesn't mean that the
>> halting problem is not undecidable but it does mean that if that
>> Wikipedia extract is the current state of the art then nobody has proven
>> that the HP is undecidable, at least for non-"pathological" programs.
>>
>> Olcott is on to something. :)
>>
>> /Flibble
> "a decider can not be a part of or called by that which is being decided"
> That is impossible to enforce (if definable) and not really formally definable.
> It also contradicts the definition of the Halting Problem - it has to accept any input.
> How could you even be any more explicit than "part of"? Every function can be coded in an infinite number of ways.
> That is ill-defined.
> C-B
>

void P(u32 x)
{ if (H(x, x))
HERE: goto HERE;
}

int main()
{ Output("Input_Halts = ", H((u32)P, (u32)P));
}

In my C version H can verify that its input is calling it on the basis
that P is calling its own machine address.

H correctly decides its input never halts.

The Peter Linz version has the same infinitely repeating pattern:

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

Ĥ0.q0 copies its input ⟨Ĥ1⟩ to ⟨Ĥx⟩ then Ĥ0.qx simulates this input with
the copy then
Ĥ1.q0 copies its input ⟨Ĥ2⟩ to ⟨Ĥy⟩ then Ĥ1.qx simulates this input with
the copy then
Ĥ2.q0 copies its input ⟨Ĥ3⟩ to ⟨Ĥz⟩ then Ĥ2.qx simulates this input with
the copy then ...

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein