novaBBS - comp.ai.philosophy - Concise refutation of halting problem proofs V43 [computer scientist]

Concise refutation of halting problem proofs V43 [computer scientist]

<E5mdnebOrIhuX038nZ2dnUU7-bvNnZ2d@giganews.com>

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

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!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 01 Jan 2022 15:09:07 -0600
Date: Sat, 1 Jan 2022 15:09:07 -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
Followup-To: comp.theory
From: NoO...@NoWhere.com (olcott)
Subject: Concise refutation of halting problem proofs V43 [computer scientist]
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <E5mdnebOrIhuX038nZ2dnUU7-bvNnZ2d@giganews.com>
Lines: 38
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-tQZLCjqV9rLFN8n0bjgjDzsGLFiytJyhiW6zhlmMs/kznVffY0FjrOOMLNlBbNvLHVL2QYJe4Qneh1s!KyzgUeLurjOvj2X3RadrAKKCuT2imWVvpCyfQwZfVo7LxN/4PBMaiqexcw/54rFeht33Vb6yXR6h!gw==
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: 2548

by: olcott - Sat, 1 Jan 2022 21:09 UTC

Showing how the Linz Ĥ can be correctly decided as non-halting

Revised Linz H halt deciding criteria (My criteria Ben's notation)
H.q0 wM w ⊢* H.qy iff UTM(wM, w) halts
H.q0 wM w ⊢* H.qn iff UTM(wM, w) does not halt

For simplicity we will refer to the copy of Linz H at Ĥ.qx embedded_H.
embedded_H correctly determines that its input ⟨Ĥ⟩ ⟨Ĥ⟩ never halts.

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

If embedded_H would never stop simulating its input ⟨Ĥ⟩ ⟨Ĥ⟩
this input would never reach a final state and stop running.

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 the pure simulation of an input would never reaches its final state
conclusively proves that this input specifies a non-halting computation.

This proves that the input ⟨Ĥ⟩ ⟨Ĥ⟩ to embedded_H maps to Ĥ.qn

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

The first version always gets thrown away.

computers / comp.ai.philosophy / Concise refutation of halting problem proofs V43 [computer scientist]

Subject	Author
Concise refutation of halting problem proofs V43 [computer scientist]	olcott