On 7/16/2021 7:33 AM, Mr Flibble wrote:
> On Thu, 15 Jul 2021 20:08:00 +0100
> Mike Terry <news.dead.person.stones@darjeeling.plus.com> wrote:
>
>> On 15/07/2021 18:22, 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.
>>
>> Well, that's awful wording, because it's liable to give readers the
>> impression that some specific g exists which no decider could decide
>> correctly. That would be nonsense - the fact is that g is derived
>> from f, so it would be better to call it N(f) or something [N for
>> Nemesis!].
>>
>> Then we could say clearly that no f can exist that handles its own
>> N(f) case. This implies that every f gets at least one input wrong
>> (e.g. N(f)), so no f can correctly decide halting for all inputs.
>>
>> Note that it's the ORDER of choices which is important: FIRST f is
>> fixed, THEN N(f) becomes defined (fixed) as a consequence, and f
>> decides N(f) incorrectly. (Another decider h may decide N(f)
>> correctly, but of course that h won't decide N(h) correctly and so
>> on.)
>>
>>>
>>> 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].
>>
>> Do you have a link for [Strachen 1965]? The only link I've been able
>> to find is a short letter of just three paragraphs, here:
>>
>> <https://academic.oup.com/comjnl/article/7/4/313/354243>
>>
>> I'll assume that's what you're referring to??
>>
>>>
>>> Strachen isn't saying the halting problem is undecidable,
>>
>> Dude, YES HE IS:
>> Quote:
>> This left me with an uneasy feeling that the proof must be long
>> and complicated, but in fact it is so short and simple it may be
>> of interest to casual readers.
>>
>> HE'S CONFIRMING THAT THE THEOREM IS CORRECT, and has a short proof
>> which he then outlines!
>
> NO HE ISN'T. He is saying that T cannot exist as a decider of P because
> P is aware of T and attempts to defeat it; this DOES NOT MEAN that a T
> cannot decide P where P isn't attempting to defeat T by recursively
> referencing it. This is why Strachen refers to is as an "impossible
> program".
>
> /Flibble
>

Conventionally it is understood that the instance of P proves that there
cannot be any T that always correctly decides the halting status of
every input.

In the case of my H and P, because my H is a simulating halt decider
that only acts as a pure simulator until after its halt status decision
is made the pathological self-reference(olcott 2004) error that you
correctly object to has no effect on either the behavior of P or the
halt status decision of H.

H aborts the simulation of its input before any nested H ever returns
any value to any P. This utterly nullifies the prior issue that seemed
to prove that P is undecidable.

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