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


Groups > comp.software-eng > #2763 > 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 4 — 2 participants

Back to article view | Back to comp.software-eng


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 olcott <NoOne@NoWhere.com> - 2021-05-27 10:52 -0500
    Re: People have given up attempted rebuttals because they know that I am correct olcott <NoOne@NoWhere.com> - 2021-05-27 16:33 -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

#2763 — 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]


#2764

Fromolcott <NoOne@NoWhere.com>
Date2021-05-27 10:52 -0500
Message-ID<tt-dnW0Dj4iiXTL9nZ2dnUU7-cXNnZ2d@giganews.com>
In reply to#2763
On 5/27/2021 10:31 AM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> Halting problem undecidability and infinitely nested simulation
> 
> Some recent remarks from Peter Olcott that give a good flavour of his
> approach:
> 
>    "What I don't know is what an instance of the halting problem is."
> 
>    "Whether a computation is finite is more nuanced than it simply stops
>    running"
> 
>    "the fact that a computation halts does not entail that it is a halting
>    computation"
> 
>    "To limit the scope of a halt decider to only report whether or not
>    its input actually halts is to artificially constrain an otherwise
>    correct halt decider."
> 

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

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

[toc] | [prev] | [next] | [standalone]


#2766

Fromolcott <NoOne@NoWhere.com>
Date2021-05-27 16:33 -0500
Message-ID<mtydnY9MEbaijS39nZ2dnUU7-bHNnZ2d@giganews.com>
In reply to#2763
On 5/27/2021 3:24 PM, André G. Isaak wrote:
> On 2021-05-27 12:38, olcott wrote:
>> On 5/27/2021 10:31 AM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> Halting problem undecidability and infinitely nested simulation
>>>
>>> Some recent remarks from Peter Olcott that give a good flavour of his
>>> approach:
>>>
>>>    "What I don't know is what an instance of the halting problem is."
>>>
>>>    "Whether a computation is finite is more nuanced than it simply stops
>>>    running"
>>>
>> As proven by (A) and (B)
>>
>>
>>>    "the fact that a computation halts does not entail that it is a 
>>> halting
>>>    computation"
>>>
>> As proven by (A) and (B)
>>
>>
>>>    "To limit the scope of a halt decider to only report whether or not
>>>    its input actually halts is to artificially constrain an otherwise
>>>    correct halt decider."
>>>
>>
>> If we are very precise in the meaning of those words then this means 
>> that we cannot report that a computation will never halt until we 
>> first wait forever and find that "its input actually halts"
> 
> There's nothing in the definition of a halt decider that requires one to 
> run (or simulate) the computation. 

Thanks for responding.

Of course there isn't and it is quite silly that this point keeps 
getting repeated. The proof categorically claims that no type of halt 
decider correctly decides all inputs on the basis of inputs that do the 
opposite of whatever its paired decider decides.

If there exists any type of decider that does correctly decide paired 
inputs that do the opposite of whatever this decider decides then the 
categorical claim of the proof is proven to be incorrect.

It turns out that a halt decider based on simulating its input is such a 
decider that refutes the categorical claim of the proofs.

> It was your decision to do things 
> this way. If that decision creates problems, you can't blame those 
> problems on the way the halting problem is formulated.
> 
> We can easily determine that many computations don't halt without 
> waiting forever. You only have to wait forever if you're stupid enough 
> to try to establish that they don't halt by running/simulating them.
> 
>> On the other hand when the behavior of the simulation of an input 
>> matches a non-halting behavior pattern, then we need not wait forever 
>> to see if: "its input actually halts".
>>
>> void Infinite_Loop()
>> {
>>    HERE: goto HERE;
>> }
>>
>> _Infinite_Loop()
>> [00000aaf](01)  55                      push ebp
>> [00000ab0](02)  8bec                    mov ebp,esp
>> [00000ab2](02)  ebfe                    jmp 00000ab2
>> [00000ab4](01)  5d                      pop ebp
>> [00000ab5](01)  c3                      ret
>> Size in bytes:(0007) [00000ab5]
>>
>> [infinite_loop] non-halting behavior pattern
>> (a) The instruction is a JMP instruction.
>> (b) It is jumping upward or to its own address.
>> (c) There are no conditional branch instructions in-between.
>> (d) There are no other JMP instructions in-between (André G. Isaak)
>>
>> When the [infinite_loop] non-halting behavior pattern of the 
>> simulation of _Infinite_Loop() is matched by the behavior of 
>> _Infinite_Loop() the simulating halt decider correctly decides 
>> not-halting on this input.
>>
>> Begin Local Halt Decider Simulation at Machine Address:aaf
>> ...[00000aaf][002115e2][002115e6](01)  55                      push ebp
>> ...[00000ab0][002115e2][002115e6](02)  8bec                    mov 
>> ebp,esp
>> ...[00000ab2][002115e2][002115e6](02)  ebfe                    jmp 
>> 00000ab2
>> ...[00000ab2][002115e2][002115e6](02)  ebfe                    jmp 
>> 00000ab2
>> Local Halt Decider: Infinite Loop Detected Simulation Stopped
>>
>> Ben has a very hard time with my words because he generally does not 
>> pay very close attention to what I am actually saying. Ben focuses 
>> most of his attention on spouting off some contrived rebuttal or another.
>>
>> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qy  ∞
>> Ĥ.q0  wM  ⊢*  Ĥ.qx  wM  wM  ⊢*  Ĥ.qn
>>
>> 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.
>>
>> (A) 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.
>>
>> (B) 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.
> 
> If something 'only halts because of X' it still halts.
> 

Not the way that I am defining my terms:

Everyone knows that infinite loops are finite strings that specify 
infinite computations.

This same reasoning equally applies to infinite recursion and infinitely 
nested simulation.

On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
 > olcott <NoOne@NoWhere.com> writes:
 >
 >> Truism:
 >> Every simulation that would never stop unless Halts() stops
 >> it at some point specifies infinite execution.
 >
 > Any algorithm that implements this truism is, of course, a halting
 > decider.

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

The input to the computation Ĥ.qx(<Ĥ><Ĥ>) exactly matches the above 
criteria.

> It's no different from claiming that an airplane only flies because its 
> wings generate lift. Would you argue that an airplane doesn't *actually* 
> fly based on that 'only...because' clause?
> 
> André
> 


-- 
Copyright 2021 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#2768

FromMr Flibble <flibble@reddwarf.jmc>
Date2021-05-28 06:01 +0100
Message-ID<20210528060103.00002e39@reddwarf.jmc>
In reply to#2763
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.software-eng


csiph-web