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

On 12/19/2021 4:25 PM, Malcolm McLean wrote:

On Sunday, 19 December 2021 at 19:04:11 UTC, Jeff Barnett wrote:

On 12/19/2021 11:44 AM, olcott wrote:

I can (and will shortly) conclusively prove that pure function H
correctly detects that P specifies infinitely nested simulation.

Simple question: Since virtually everyone who has studied this problem
knows, simulation is not a feasible way to build a halt decider
(assuming one could be built). The proof you are attacking as well as
others I am aware of are not based on simulation. Why do insist that
simulation is the way to go?

I think I can answer this for PO.

The first observation is that a simulating halt decider goes into an
infinite series of nested simulations if fed H_Hat. So this leads to the question, can we somehow exploit this to get round the Linz trap?

The HP counter-examples have always assumed that both answers that the corresponding halt decider could provide, halts and does not halt would
be the wrong answer.

THIS BY ITSELF IS A BRAND NEW IDEA
These same counter-examples provided to a simulating halt decider
specify the non-halting behavior of infinitely nested simulation.

The answer is "no". But in answering that question, we set up a system
in which the simulating halt decider must get the wrong answer, for reasons

Everyone that ever said that it must get the wrong answer did not
understand the computer science well enough.

A halt decider only computes the mapping of its inputs ⟨Ĥ⟩ ⟨Ĥ⟩ to an accept / reject state. It must do this entirely on the basis of the
actual behavior specified by these actual inputs.

As long as no amount of simulation by the simulating halt decider would
ever cause the simulated input to reach its final state we know by the
Linz definition of halting that this input specifies a non halting
computation.

Computation that halts: the Turing machine will halt whenever it enters
a final state. (Linz:1990:234)

As long as the input to a halt decider specifies a non halting
computation then

this by itself is an entirely sufficient condition
this by itself is an entirely sufficient condition
this by itself is an entirely sufficient condition
this by itself is an entirely sufficient condition

for the halt decider to transition to its reject state.

which have nothing to do with LInz's "invert the result" step. So have
we broken new ground? Can we maybe say that the result is correct,
because the simulation "aborts" instead of "halting", and if it didn't "abort" it would indeed run forever, so it must have correctly "aborted".

The verified fact that the input specifies a non-halting computation to
every simulating halt decider provides these halt deciders the entirely sufficient basis for to transition to their reject state.


--
Copyright 2021 Pete Olcott

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

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