XPost: comp.theory, sci.logic, sci.math

On 9/5/2021 4:37 AM, Alan Mackenzie wrote:

Ben Bacarisse <[email protected]> wrote:

Richard Damon <[email protected]> writes:

On 9/4/21 2:13 PM, olcott wrote:

On 9/4/2021 1:04 PM, Alan Mackenzie wrote:

[ Malicious cross posting snipped. ]

In comp.theory olcott <[email protected]> wrote:

.... valid on the basis of the known equivalence between the direct >>>>>> execution of a computation and its simulation by a UTM.

Not really.  There might well not be a simulation of the program.

I am stopping here. If it is impossible to simulate the TM description >>>> of a TM then it is not a proper TM.

I am pretty sure he is referring to the unwarranted assumption that any
simulation at all is involved.

Thanks, Ben, that's exactly what I was trying to say. Apologies to PO
for being unclear, here.

Yet the point that I am making is that when a simulating halt decider
applies this criteria to its input:

whether the simulation of this program must be aborted to
prevent it from running forever.

Then the Peter Linz H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly decides that its input halts and transitions to H.qy on the basis of Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩ correctly decides that its input does not halt and transitions to Ĥ.qn.

The context has been lost, including the key part that Alan was
objecting to:

|| In computability theory, the halting problem is the
|| problem of determining, from a description of an arbitrary
|| computer program and an input,
|| whether the simulation of this program must be aborted to
|| prevent it from running forever.

The phrase "the simulation" implies there is simulation involved. Had
PO written "whether /a/ simulation of this program runs forever" the
reference to simulation would be silly and superfluous, but not wrong.

--
Ben.

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)