Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #34360 > unrolled thread

People have given up attempted rebuttals because they know that I am correct

Started byolcott <NoOne@NoWhere.com>
First post2021-05-27 10:01 -0500
Last post2021-05-28 06:01 +0100
Articles 2 — 2 participants

Back to article view | Back to comp.theory


Contents

  People have given up attempted rebuttals because they know that I am correct olcott <NoOne@NoWhere.com> - 2021-05-27 10:01 -0500
    Re: People have given up attempted rebuttals because they know that I am correct Mr Flibble <flibble@reddwarf.jmc> - 2021-05-28 06:01 +0100

#34360 — People have given up attempted rebuttals because they know that I am correct

Fromolcott <NoOne@NoWhere.com>
Date2021-05-27 10:01 -0500
SubjectPeople have given up attempted rebuttals because they know that I am correct
Message-ID<E_-dndSfEuanKTL9nZ2dnUU7-a_NnZ2d@giganews.com>
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 neither return values: {0, 1} from Halts() to H_Hat() 
represent the actual halting behavior of H_Hat() in the computation: 
Halts((u32)H_Hat, (u32)H_Hat);

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: [Ĥ]
            Figure 12.3 Turing Machine Ĥ

Ĥ.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.

The above proof does correctly refute the halting theorem.

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

[toc] | [next] | [standalone]


#34365

FromMr Flibble <flibble@reddwarf.jmc>
Date2021-05-28 06:01 +0100
Message-ID<20210528060103.00002e39@reddwarf.jmc>
In reply to#34360
On Thu, 27 May 2021 10:01:13 -0500
olcott <NoOne@NoWhere.com> wrote:

[snip]

> The above proof does correctly refute the halting theorem.

Which halting theorem? You haven't refuted Turing until you address the
issue of branching logic predicated on arbitrary program input.

/Flibble

[toc] | [prev] | [standalone]


Back to top | Article view | comp.theory


csiph-web