Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

Old mail has arrived.


computers / comp.ai.philosophy / Concise refutation of halting problem proofs V56 [ Linz Proof ]

SubjectAuthor
o Concise refutation of halting problem proofs V56 [ Linz Proof ]olcott

1
Subject: Concise refutation of halting problem proofs V56 [ Linz Proof ]
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic, sci.math
Followup: comp.theory
Date: Mon, 31 Jan 2022 21:37 UTC
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: Mon, 31 Jan 2022 15:37:36 -0600
Date: Mon, 31 Jan 2022 15:37:34 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.5.1
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
Content-Language: en-US
Followup-To: comp.theory
From: NoO...@NoWhere.com (olcott)
Subject: Concise refutation of halting problem proofs V56 [ Linz Proof ]
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <Maadneksicg9y2X8nZ2dnUU7-RHNnZ2d@giganews.com>
Lines: 53
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-6F5xWAPrmPe34aWn1GCXBhYQIcTuHeF3/zHYSTCwBg03u6LKx3WjNWbNckwtTOl9ZfFr522i4+IlKlu!BzH2gtv2tYnOePRn0Xitx+QjJoXUFaj7ms99hzrHKi+2eP+064sRU/t1+7uNkd7fPjwY6jSs/Mij
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: 3630
View all headers
Halting problem undecidability and infinitely nested simulation (V3)

A simulating halt decider H bases it halt status decision on what the behavior of its input would be if H was a UTM. If H correctly determines that its simulated input would never reach its final state then H aborts this simulation and transitions to its final reject state. Otherwise H transitions to its final accept state as soon as its simulation completes.

Simulating halt deciders determine whether or not the Linz halt criteria possibly can met:
    the Turing machine will halt whenever it enters a final state. (Linz:1990:234)
on the basis of matching infinite behavior patterns. Failure to match is construed as halting.

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 ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

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

Then these steps would keep repeating:
   Ĥ1 copies its input ⟨Ĥ2⟩ to ⟨Ĥ3⟩ then embedded_H simulates ⟨Ĥ2⟩ ⟨Ĥ3⟩
   Ĥ2 copies its input ⟨Ĥ3⟩ to ⟨Ĥ4⟩ then embedded_H simulates ⟨Ĥ3⟩ ⟨Ĥ4⟩
   Ĥ3 copies its input ⟨Ĥ4⟩ to ⟨Ĥ5⟩ then embedded_H simulates ⟨Ĥ4⟩ ⟨Ĥ5⟩...

This shows that the simulated input to embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩ would never reach its final state conclusively proving that this simulated input never halts. This enables embedded_H to abort the simulation of its input and correctly transition to Ĥ.qn.

Because a halt decider is a decider embedded_H is only accountable for computing the mapping from ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qy or Ĥ.qn on the basis of the actual behavior specified by these inputs. embedded_H is not accountable for the behavior of the computation that it is contained within: Ĥ applied to ⟨Ĥ⟩ because this is not an actual input to embedded_H.


Halting problem undecidability and infinitely nested simulation (V3)
https://www.researchgate.net/publication/358009319_Halting_problem_undecidability_and_infinitely_nested_simulation_V3



--
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
rocksolid light 0.7.2
clearneti2ptor