On 10/17/2022 6:55 AM, wij wrote:
> On Monday, 17 October 2022 at 17:30:59 UTC+8, Fred. Zwarts wrote:
>> I have been following the discussions about Halt deciders with interest.
>> As a retired software designer and developer, I have a lot of practical
>> experience, but not much theoretical education, although the theoretical
>> background is very interesting. I learned a lot. I would like to verify
>> that I understand it correctly. Could you point out any errors in the
>> summary below?
>>
>> 1) (Definition of halt) A program X with input Y is said to halt if it
>> reaches its end condition after a finite number of steps. It does not
>> halt if it continues to execute infinitely.
>> (So, X(Y) either halts, or it does not halt.)
>> (It is irrelevant whether the end condition is reached in the 'normal'
>> way, or by other means, e.g. an unhandled 'exception'.)
>
> Basically, yes. The HP (most formal one) is specified using TM.
> A TM halts means it reaches designated final state. This is equivalent to a
> program 'returns' (whatever, you define the 'final state').
> OTHER conditions are non-halting.
>
>> 2) (Definition of halt decider) A halt decider H is a program that,
>> given a program X with input Y decides, after a finite number of steps,
>> whether X(Y) halts or not.
>> (H(X,Y) itself must halt after a finite number of steps. It must return
>> either 1 if X(Y) halts, or 0 if X(Y) does not halt, where 1 and 0 are a
>> convention, which could also be two other arbitrary values.)
>
> I find it not quite simple to define 'halt decider', probably not necessary.
> So, I say any program X that tries to test whether a given program (as X's input)
> halts or not is a 'halt decider'.
>
>> From 1 and 2 it follows:
>>
>> 3) If X(Y) halts, then H must return 1. If H does not return 1 in a
>> finite number of steps, it might return another interesting result, but
>> it is not a halt decider. (Not returning 1 includes returning other
>> values, not halting, or throwing 'exceptions'.)
>
> Yes, according to the definition (a failed halt decider)
>
>> 4) If X(Y) does not halt, then H must return 0. If it does not return 0
>> in a finite number of steps, it might return another interesting result,
>> but it is not a halt decider. (Not returning 0 includes returning other
>> values, not halting, or throwing 'exceptions'.)
>>
>
> Yes, according to the definition (a failed halt decider)
>
>> Paradoxical program:
>>
>> 5) It is always possible to construct a program P, that uses code with
>> the same logic as H, in order to do the opposite of what H(P,P) returns.
>> (P does not necessarily need to use the exact same code as H does,
>> amongst others it could use a modified copy of H, or a simulation of H.)
>>
>> From 5 it follows that a general halt decider that works for any X and
>> Y does not exist:
>>
>> From 3, 4 and 5 it follows:
>
> There are many details, but yes, you are correct.
>
>> 6) If P(P) halts, then H should return 1, but if H would do so, P(P)
>> would not halt.
>
> Correct.
>
>> 7) If P(P) does not halt, H should return 0, but if H would do so, P(P)
>> would halt.
>
> Correct.
>
>> 8) If P(P) halts and H does not return 1 after a finite number of steps,
>> then H is not a halt decider.
>> (The result could nevertheless be interesting for other purposes.)
>> (It is irrelevant what causes P(P) to halt.)
>>
>> 9) If P(P) does not halt and H does not return 0 after a finite number
>> of steps, then H is not a halt decider.
>> (The result could nevertheless be interesting for other purposes.)
>
> H is not the halt decider the Halting Problem specifies (a failed halt decider).

*Professor Sipser has agreed to these verbatim words* (and no more)
If simulating halt decider H correctly simulates its input D until H
correctly determines that its simulated D would never stop running
unless aborted then H can abort its simulation of D and correctly report
that D specifies a non-halting sequence of configurations.

An alternative definition for a halt decider approved by MIT Professor
Michael Sipser (author of the best selling book on the theory of
computation)
https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295
is shown above and paraphrased below:

Would D correctly simulated by H ever stop running if not aborted?
Is proven on page 3 of this paper to be "no" thus perfectly meeting the
Sipser approved criteria shown above.

*Rebutting the Sipser Halting Problem Proof*
https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof

This is applied to the Peter Linz Halting Problem proof on page 4 of the
above paper.

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer