Re: Mike Terry Reply to Fred Zwarts

Op 03.jun.2024 om 23:24 schreef olcott:

On 6/3/2024 3:09 PM, Fred. Zwarts wrote:

Op 03.jun.2024 om 14:20 schreef olcott:

On 6/3/2024 4:42 AM, Ben Bacarisse wrote:

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>

PO's D(D) halts, as illustrated in various traces that have been posted here.
PO's H(D,D) returns 0 : [NOT halting] also as illustrated in various traces.
i.e. exactly as the Linz proof claims.  PO has acknowledged both these
results.  Same for the HH/DD variants.
>
You might imagine that's the end of the matter - PO failed.  :)
>
That's right, but PO just carries on anyway!

>
He has quite explicitly stated that false (0) is the correct result for
H(D,D) "even though D(D) halts".  I am mystified why anyone continues to
discuss the matter until he equally explicitly repudiates that claim.
>

>
Deciders only compute the mapping *from their inputs* to their own
accept or reject state. The correct emulation of the machine code input
to H(DD,DD) requires DD emulated by HH to emulate each x86 instruction
of the x86 machine code of DD correctly and in the correct order.
>
*The input to HH(DD,DD) specifies non-halting behavior*
>
The only way to cause DD emulated by HH to have the same behavior as
the directly executed (non input) DD(DD) is to emulate the instructions
specified by the machine code of DD incorrectly or in the incorrect
order. *This is not the behavior that the input to HH(DD,DD) specifies*
>
The behavior of the directly executed DD(DD) has different behavior
than DD correctly emulated by HH. This is because the behavior of DD(DD)
reaps the benefits of HH having already aborted its simulation.
>
No one ever noticed that these two behaviors could ever diverge before
because everyone rejected the notion of a simulating halt decider out-
of-hand without review.
>
>
>
Two PhD computer science professors that I have communicated with
agree with me that there is something wrong with the halting problem.
>
Bill Stoddart. *The Halting Paradox*
20 December 2017
https://arxiv.org/abs/1906.05340
arXiv:1906.05340 [cs.LO]
>
E C R Hehner. *Problems with the Halting Problem*, COMPUTING2011 Symposium on 75 years of Turing Machine and Lambda-Calculus, Karlsruhe Germany, invited, 2011 October 20-21; Advances in Computer Science and Engineering v.10 n.1 p.31-60, 2013
https://www.cs.toronto.edu/~hehner/PHP.pdf
>
E C R Hehner. *Objective and Subjective Specifications*
WST Workshop on Termination, Oxford.  2018 July 18.
See https://www.cs.toronto.edu/~hehner/OSS.pdf
>
>
>
*Introduction to the Theory of Computation, by Michael Sipser*
https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X/
>
On 10/13/2022 11:29:23 AM
MIT Professor Michael Sipser agreed this verbatim paragraph is correct
(He has neither reviewed nor agreed to anything else in this paper)
>
<Professor Sipser agreed>
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.
</Professor Sipser agreed>
>
>
>
*DD correctly simulated by HH would never stop running unless aborted*
*We can see that the following DD cannot possibly halt when*
*correctly simulated by every HH that can possibly exist*

>
It is very clear that if the simulated HH would halt, then DD would halt. So your claim comes down to HH not halting when simulating itself.
>

 Mike Terry replied to this and explained it correctly
as reply directly to you
On 6/3/2024 12:36 PM, Mike Terry wrote:
 http://al.howardknight.net/?STYPE=msgid&MSGI=%3CHlGdnbvc3Ly_YsD7nZ2dnZfqn_adnZ2d%40brightview.co.uk%3E
 

It turns out that you do not understand what I am trying to say.
Maybe it is easier to understand what I mean with the following:
Olcott defends a simulating halt decider H. The problem with it is, that it introduces another halting problem: The H itself does not halt when simulated by itself. This cause false negatives: many functions are now diagnosed by H to be non-halting only by the mere fact that they call H, even if their direct execution does halt.
H even diagnoses itself to be non-halting, which is illustrated in the following example (where the D that contradicts H is eliminated):
        typedef int (*ptr)();  // ptr is pointer to int function in C
        int H(ptr p, ptr i);
        int main()
        {
          H(main, 0);
        }
The program main does nothing but calling H. H is required to halt, so main itself should also halt. Nevertheless H reports that main does not halt.
Of the infinite set of H that simulate at least one step, none of them, when simulated by H, reaches its final state. So, it follows that H determines non-halting behaviour of H and reports that main does not halt. This has no relation with a paradox in main. It is just a false negative.
This illustrates that a simulating halt-decider is a bad idea, because the decider itself does not halt and therefore its results are often false negatives.