Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

If it's not in the computer, it doesn't exist.


computers / comp.ai.philosophy / Refuting the Peter Linz Halting Problem Proof V7

SubjectAuthor
o Refuting the Peter Linz Halting Problem Proof V7olcott

1
Refuting the Peter Linz Halting Problem Proof V7

<wf-dna-bx_hKd6D_nZ2dnUU7_8zNnZ2d@giganews.com>

  copy mid

https://www.novabbs.com/computers/article-flat.php?id=8194&group=comp.ai.philosophy#8194

  copy link   Newsgroups: comp.theory comp.ai.philosophy sci.logic sci.math
Followup: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 25 Mar 2022 11:16:23 -0500
Date: Fri, 25 Mar 2022 11:16:21 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.7.0
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
Content-Language: en-US
Followup-To: comp.theory
From: NoO...@NoWhere.com (olcott)
Subject: Refuting the Peter Linz Halting Problem Proof V7
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <wf-dna-bx_hKd6D_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 72
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-j0mnfizwRd74z48yo2G3aUzGiNBCBzJSOfWLFw29fnHUTUiu3+r4rLjhH5tUC2ALnvYNYHnqMMwJtej!Xbp9vCoMS/8RXb7HuVLgU+8EOuhvJ/INSXTJUqFnm6msWcF93YLbXd9xCNSg8NSxuyxkAYt0PPyq
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 4428
 by: olcott - Fri, 25 Mar 2022 16:16 UTC

A Simulating Halt Decider (SHD) computes the mapping from its input to
its own accept or reject state based on whether or not the pure
simulation of its input could reach the final state of this input in a
finite number of simulated steps.

The following simplifies the syntax for the definition of the Linz
Turing machine Ĥ, it is now a single machine with a single start state.
A copy of Linz H is embedded at Ĥ.qx

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
If the pure simulation of ⟨Ĥ⟩ ⟨Ĥ⟩ by embedded_H would reach its final state.

Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
If the pure simulation of ⟨Ĥ⟩ ⟨Ĥ⟩ by embedded_H would never reach its
final state.

When Ĥ is applied to ⟨Ĥ⟩
Ĥ copies its input ⟨Ĥ0⟩ to ⟨Ĥ1⟩ then embedded_H simulates ⟨Ĥ0⟩ ⟨Ĥ1⟩

Then these steps would keep repeating:
Ĥ0 copies its input ⟨Ĥ1⟩ to ⟨Ĥ2⟩ then embedded_H0 simulates ⟨Ĥ1⟩ ⟨Ĥ2⟩
Ĥ1 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then embedded_H1 simulates ⟨Ĥ2⟩ ⟨Ĥ3⟩
Ĥ2 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then embedded_H2 simulates ⟨Ĥ3⟩ ⟨Ĥ4⟩...

The above shows that the simulated input to embedded_H never reaches its
own final state whether or not its simulation is aborted.
(a) If the simulation is not aborted the above sequence never ends.
(b) If the simulation is aborted the entire chain of recursive
simulations immediately stops.

In no case does the simulated input ⟨Ĥ⟩ ⟨Ĥ⟩ ever reach its final state
⟨Ĥ⟩.qn thus never meets the Linz definition of halting:

computation that halts … the Turing machine will halt whenever it enters
a final state. (Linz:1990:234) Thus if embedded_H rejects its input it
is necessarily correct.

Because all halt deciders are deciders they compute the mapping from
their input finite strings inputs to their own accept or reject state.
Halt deciders (because they are deciders) do not compute any mappings
from non-finite string non-inputs.

No halt decider ever determines the halt status of the computation that
contains its actual self thus embedded_H does not compute the mapping
from Ĥ ⟨Ĥ⟩ because it is neither an input nor a finite string.

Even Linz was confused by this. embedded_H is not supposed to report on
itself or the computation that it is contained within.

As long as it is verified that the simulated input to embedded_H cannot
reach its final state then we know that this simulated input cannot meet
the Linz definition of halting.

As long as we know that this simulated input cannot meet the Linz
definition of halting we know that this input specifies a non-halting
sequence of configurations.

As long as we know that this input specifies a non-halting sequence of
configurations then we know that embedded_H would be correct to reject
this input.

Halting problem undecidability and infinitely nested simulation (V4)

https://www.researchgate.net/publication/359349179_Halting_problem_undecidability_and_infinitely_nested_simulation_V4

--
Copyright 2021 Pete Olcott

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

1
server_pubkey.txt

rocksolid light 0.9.8
clearnet tor