Re: Every sufficiently competent C programmer knows --- Semantic Property of Finite String

On 14/03/2025 19:48, Keith Thompson wrote:

Richard Heathfield <rjh@cpax.org.uk> writes:

On 14/03/2025 11:02, joes wrote:

Am Thu, 13 Mar 2025 20:48:09 -0500 schrieb olcott:

<snip>

For the first time in the history of mankind it proves that a simulation
of a virtual machine according to the semantics of this machine language
DOES NOT ALWAYS HAVE THE SAME BEHAVIOR AS THE DIRECT EXECUTION OF THIS
SAME MACHINE

Bold claim. How does that make sense?

>
Well, it doesn't, but you weren't expecting it to, were you?

 No, it doesn't make sense, but I can imagine something similar to that
claim that might make sense if it were logically possible (which it
isn't).  And to be clear, I haven't read the full context.
 A simulation that doesn't have the same behavior as the thing it's
simulating (which is what Olcott claims here) simply is not a
simulation, so his claim is self-contradictory.  But such a
not-quite-simulation might still be useful.

Indeed. But in this case it doesn't move us forward. Whether S(P, D) a simulation of program P with D data, does or does not behave exactly like P is unimportant. What matters is whether P(D) halts. If the simulation S(P,D) accurately reports the halting/non-halting behaviour of P(D), Q(E), R(F) ad arbitrarium... that's all we ask of it.
If it doesn't, it contributes nothing. And if it does, we're right back with Turing's proof and the simulator might as well not exist.

The Halting Problem is about taking an arbitrary program and input and
determining whether the program halts or not.  This is of course
trivially possible in many special cases:
     int main(void) { return 0; }  // halts
     int main(void) { while (1); } // does not halt
and difficult but possible in other cases, but impossible in general.

Yes.

What Olcott *might* be claiming is that he can determine whether any
arbitrary program halts by "simulating" it in a way that isn't a true
simulation, but that tells us whether it halts or not.  So perhaps
while it's running the simulation, it's somehow able to detect and
report that the simulated program does or does not eventually halt.
(I haven't studied what he's written enough to have any idea how
it would do this, and I don't intend to.)

He thinks he can disprove Peter Linz's HP proof, which he can't... or at least hasn't yet.
Linz's proof can be found here:
https://john.cs.olemiss.edu/~hcc/csci311/notes/chap12/ch12.pdf

Which could all make sense if it were mathematically possible,
but of course it isn't.

Indeed. Back in the day, the OP would have been a circle squarer.
<snip>
--
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