Re: Mike Terry Proves --- How the requirements that Professor Sipser agreed to are exactly met

On 20/05/2025 05:10, olcott wrote:

On 5/19/2025 5:12 AM, Mikko wrote:

On 2025-05-18 19:18:21 +0000, olcott said:

<snip>

When the hypothetical H never aborts its simulated D then:
(a) Simulated D  NEVER HALTS
(b) Executed D() NEVER HALTS
(c) Executed H() NEVER HALTS
(d) Everything that H calls NEVER HALTS

>
You forgot
(e) H does not report
>

 HHH is required to report, that is why it
must always report on the behavior of the
hypothetical H/D pair and not the actual
behavior of the actual H/D pair for every
non-terminating input.

It's quite true that the reporter is required to report, and this is precisely where the whole idea of simulation proves to be rather wobbly. Clearly, in cases where the simulated program never terminates the simulator cannot run to completion if the reporter is ever to deliver its report. The reporter is therefore required to report a guess.
This guess could be extremely sophisticated, or it might be very naive. For example, one could devise an abstract syntax tree from the program, maybe prune it of statements that can be shown not to affect the halt state, and take a long hard look at the remaining behaviour using clever techniques yet to be discovered by a computer scientist not yet born; or one might simply compare the state of the simulation to all previous states and look for an exact match because a state that has recurred once may very well recur again, and again, and again... Such an event certainly makes a guess of 'never halts' extremely seductive, although of course it remains a mere guess.
Unfortunately, as well as making rapidly increasing demands on memory this method makes the entirely unwarranted assumption that the input tape can be ignored. Who is to say that the simulated program is not simply waiting for some specific symbol to appear under the tape's read head before it shakes off its torpor and continues on its merry way?
And so, no matter how long the simulation continues, the simulator can never with certainty deduce that the program will never halt. It must guess, and guessing means sometimes guessing /wrong/.
Unfortunately, guessing wrong isn't one of the options.
The question is whether an algorithm exists for determining whether an arbitrary program halts given arbitrary input.
The question is NOT whether an algorithm exists for determining whether an arbitrary program MIGHT halt given arbitrary input.
There is no room here for guessing, and simulation is therefore a theoretical dead end.
No. There is no substitute for analysing the tapes to get at the input and the program instructions themselves, whether they be in the expansive form of source code or the nitty gritty nuts and bolts of machine code. And the moment we take the analytical route, we run headlong into Turing's twist, and we're already dead in the water.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within