novaBBS - comp.ai.philosophy - Concise refutation of halting problem proofs V44 [honest dialogue]

Concise refutation of halting problem proofs V44 [honest dialogue]

<R4ednYw3OMug60_8nZ2dnUU7-LvNnZ2d@giganews.com>

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

copy link Newsgroups: comp.theory comp.ai.philosophy sci.logic sci.math

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!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 02 Jan 2022 22:06:21 -0600
Date: Sun, 2 Jan 2022 22:06:20 -0600
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.4.1
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
Content-Language: en-US
From: NoO...@NoWhere.com (olcott)
Subject: Concise refutation of halting problem proofs V44 [honest dialogue]
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <R4ednYw3OMug60_8nZ2dnUU7-LvNnZ2d@giganews.com>
Lines: 39
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-MaiIJF5J03AaHgFwO1Y5isdRgqWkBmEHCnG1eZlzHCdFNTukJyeO5+4z7LVIX67uRiFvDRFSnCqPCJ4!TabLMz5C21So6apmzoOOWkFUbUyTnMoCQpb4Kve7Rc9U1Z4JQes28zCT2PFi8KpiVyduP4jpzELI!OQ==
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: 2451

by: olcott - Mon, 3 Jan 2022 04:06 UTC

For simplicity we will refer to the copy of Linz H at Ĥ.qx embedded_H.

Simplified syntax adapted from bottom of page 319:
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

Instead of defining what embedded_H actually does we are defining the
set of behaviors such that every embedded_H having these behaviors is
necessarily correct.

It can be easily seen that the simulated input to embedded_H never
reaches the final state of this input no matter how many steps are
simulated.

These steps would keep repeating:
Ĥ copies its input ⟨Ĥ⟩ to ⟨Ĥ⟩ then embedded_H simulates ⟨Ĥ⟩ ⟨Ĥ⟩...

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

That a simulated input cannot possibly reach it final state conclusively
proves that this input never halts.

This proves that every simulating halt decider at Ĥ.qx that somehow
computes the mapping from its input ⟨Ĥ⟩ ⟨Ĥ⟩ to Ĥ.qn it is necessarily
correct.

Peter Linz HP Proof
https://www.liarparadox.org/Peter_Linz_HP_315-320.pdf

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

This login session: $13.99

computers / comp.ai.philosophy / Concise refutation of halting problem proofs V44 [honest dialogue]

Subject	Author
Concise refutation of halting problem proofs V44 [honest dialogue]	olcott