Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

Why won't sharks eat lawyers? Professional courtesy.


computers / comp.ai.philosophy / Halting problem undecidability and infinitely nested simulation(V11)(proxy inputs)[no contradictions]

SubjectAuthor
o Halting problem undecidability and infinitely nested simulation(V11)(proxy inputolcott

1
Halting problem undecidability and infinitely nested simulation(V11)(proxy inputs)[no contradictions]

<38GdnelDtMCM1TD9nZ2dnUU7-SPNnZ2d@giganews.com>

  copy mid

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

  copy link   Newsgroups: comp.theory sci.math.symbolic comp.ai.philosophy comp.software-eng
Followup: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!tr3.eu1.usenetexpress.com!feeder.usenetexpress.com!tr2.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 25 May 2021 13:55:13 -0500
Newsgroups: comp.theory,sci.math.symbolic,comp.ai.philosophy,comp.software-eng
X-Mozilla-News-Host: news://news.giganews.com:119
Followup-To: comp.theory
From: NoO...@NoWhere.com (olcott)
Subject: Halting problem undecidability and infinitely nested simulation(V11)(proxy inputs)[no contradictions]
Date: Tue, 25 May 2021 13:55:13 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.10.2
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <38GdnelDtMCM1TD9nZ2dnUU7-SPNnZ2d@giganews.com>
Lines: 118
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-onlms3QU6ax8MX2tYG7WHQeenxaKrCNVWfEDa3SVIYVoofwWWawORrKa1wBD4G1c/TyshijGzG9wqlD!kMXDQFLA01yMMdMMbv92EBUXn93CGLK5P1Kn3r6R4DzPCiz0oML4KTdb/ggisQU8ri+rqXdWhF0h!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: 6138
 by: olcott - Tue, 25 May 2021 18:55 UTC

What has been mistaken as a contradiction consistently used as the basis
of rebuttals of my work is addressed in the last paragraph of this post.

Halting problem undecidability and infinitely nested simulation

When input P to simulating halt decider H has the pathological
self-reference error (PSRE) simulating halt decider H decides this input
P on the basis of proxy input P2 that has the pathological
self-reference error removed.

void H_Hat(u32 P)
{ u32 Input_Halts = Halts(P, P);
if (Input_Halts)
HERE: goto HERE;
}

The pathological self-reference error arises in the halting theorem from
the fact that both return values: {0, 1} from Halts() to H_Hat() are
incorrect when H_Hat() is invoked with its own machine address as input.

When we define H_Hat2() by replacing the call to Halts() with a call to
Simulate()

u32 Simulate(u32 P, u32 I)
{ ((void(*)(int))P)(I);
return 1;
}

H_Hat2() never halts on its own machine address as input.
This key fact is leveraged to correctly decide halting:
Halts((u32)H_Hat, (u32)H_Hat);

We hypothesize that input P having the pathological self-reference error
(PSRE) can be substituted for equivalent proxy input P2 such that the
halting status of P2 derives the halting status of P. If this
hypothesis is correct it becomes the basis for refuting the halting
theorem.

To put this in concrete terms if Halts((u32)H_Hat2, (u32)H_Hat2);
provides the correct halting value for Halts((u32)H_Hat, (u32)H_Hat);
then H_Hat becomes a decidable input. The rest of the proof will attempt
to show this.

Generic halt deciding principle for inputs having the pathological
self-reference error

Whenever input P has the pathological self-reference error such that a
simulating halt decider H must decide halting on an input that invokes
itself we define proxy input P2 copy of P such that the embedded
simulating halt decider is replaced with a simulator.

(a) Simulating halt decider H and simulator S are equivalent
computations for all inputs P that halt. This means that H correctly
decides halting on P if and only if P2 halts.

(b) Simulating halt decider H and simulator S are equivalent
computations for all inputs P that do not halt up to the point where H
stops simulating P. This means that H correctly decides not halting on P
if and only if P2 does not halt.

In other words: Halts correctly decides not halting on H_Hat because
H_Hat2 does not halt.

Peter Linz Ĥ applied to the Turing machine description of itself: [Ĥ]

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn

The above is adapted from (Linz:1990:319).
It shows that Turing machine Ĥ copies its input at (q0) and begins
executing an embedded copy of the original halt decider with this input
at (qx).

The (qy) state indicates that the halt decider has determined that its
input would halt. The ((qn)) state indicates the input would not halt.
The appended (qa) and (qb) states cause Ĥ to infinitely loop if the halt
decider decides that its input would halt.

Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.

The above definition specifies this execution trace:
It can be understood from the above specification that when the embedded
halt decider at Ĥ.qx bases its halting decision on simulating its input,
and it has ([Ĥ],[Ĥ]) as its input that:
Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with
this copy then
Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with
this copy then
Ĥ.q0 would copy its input and then Ĥ.qx would simulate its input with
this copy...
unless and until the halt decider at Ĥ.qx stops simulating its input.

When we apply the Generic halt deciding principle to the embedded
simulating halt decider at state Ĥ.qx to its input ([Ĥ],[Ĥ]) we find
that the simulation of this input must be aborted.

Because the necessity to abort the simulation of an input is equated
with this input specifying an infinite computation the simulating halt
decider Ĥ.qx correctly transitions to its final Ĥ.qn state deciding not
halting on its input.

The computation Ĥ([Ĥ]) only halts because it contains an otherwise
infinitely nested simulation that has been aborted at state Ĥ.qx.
Because an aspect of the Ĥ([Ĥ]) computation has been aborted to force
the computation to halt we cannot count that fact that Ĥ([Ĥ]) halts
evidence that it is a halting computation.

http://www.liarparadox.org/Halting_problem_undecidability_and_infinitely_nested_simulation.pdf

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor