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

Groups > comp.theory > #36377 > unrolled thread

Halting Problem proofs appear to be bogus!

Back to article view | Back to comp.theory

Contents

  Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 14:24 +0100
    Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 14:34 +0100
      Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 14:39 +0100
        Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:36 -0500
          Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 15:39 +0100
            Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 08:38 -0700
              Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 11:04 -0500
                Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 09:25 -0700
                  Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 12:03 -0500
                    Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 19:50 +0100
          Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 15:46 +0100
        Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 15:40 +0100
          Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 15:42 +0100
            Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 01:06 +0100
              Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-17 10:52 -0500
        Re: Halting Problem proofs appear to be bogus! Andy Walker <anw@cuboid.co.uk> - 2021-07-16 16:12 +0100
          Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 10:52 -0500
            Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 09:11 -0700
              Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 11:15 -0500
      Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:13 -0500
        Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 08:32 -0700
        Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 01:03 +0100
          Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-17 10:46 -0500
            Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-18 02:32 +0100
              Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-19 10:10 -0500
                Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 01:35 +0100
                  Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-20 09:24 -0500
                    Re: Halting Problem proofs appear to be bogus! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-21 01:28 +0100
                Re: Halting Problem proofs appear to be bogus! Richard Damon <Richard@Damon-Family.org> - 2021-07-19 20:48 -0700
    Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 15:27 +0100
      Re: Halting Problem proofs appear to be bogus! Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 15:36 +0100
        Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 10:02 -0500
          Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:09 +0100
        Re: Halting Problem proofs appear to be bogus! wij <wyniijj@gmail.com> - 2021-07-16 08:46 -0700
        Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:07 +0100
          Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 16:20 -0500
            Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:25 +0100
              Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 16:32 -0500
                Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-17 11:48 +0100
      Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:44 -0500
        Re: Halting Problem proofs appear to be bogus! Peter <peterxpercival@hotmail.com> - 2021-07-16 22:10 +0100
    Re: Halting Problem proofs appear to be bogus! olcott <NoOne@NoWhere.com> - 2021-07-16 09:32 -0500

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#36396

On Friday, 16 July 2021 at 22:13:37 UTC+8, olcott wrote:
> On 7/16/2021 8:34 AM, Ben Bacarisse wrote: 
> > Mr Flibble <fli...@reddwarf.jmc> writes: 
> > 
> >> All extant halting problem proofs appear to be predicated on a 
> >> misunderstanding of the following contradiction: 
> > 
> > I don't think you've read any actual proofs, let along all of them. Why 
> > you would even say such a thing? 
> > 
> >> Suppose T[R] is a Boolean function taking a routine 
> >> (or program) R with no formal or free variables as its 
> >> argument and that for all R, T[R] — True if R terminates 
> >> if run and that T[R] = False if R does not terminate. Consider 
> >> the routine P defined as follows 
> >> 
> >> rec routine P 
> >> §L :if T[P] goto L 
> >> Return § 
> >> 
> >> If T[P] = True the routine P will loop, and it will 
> >> only terminate if T[P] = False. In each case T[P] has 
> >> exactly the wrong value, and this contradiction shows 
> >> that the function T cannot exist. 
> >> 
> >> [Strachey 1965] 
> >> 
> >> T is indeed unable to decide P but for the wrong reason: T[P] is 
> >> recursive 
> > 
> > T[P] is not recursive. Maybe you don't understand what the CPL means? 
> > 
> > Further, this argument must fail for any of the actual proofs that are 
> > based on Turing machine because TMs have not functions, not calls and no 
> > recursion. 
> >
> Peter Linz Ĥ applied to the Turing machine description of itself: ⟨Ĥ⟩ 
> 
> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞ 
> if M applied to wM halts, and 
> 
> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn 
> if M applied to wM does not halt 
> 
> When we hypothesize that the halt decider embedded in Ĥ is simply a UTM 
> then it seems that when the Peter Linz Ĥ is applied to its own Turing 
> machine description ⟨Ĥ⟩ this specifies a computation that never halts. 
> 
> Ĥ0.q0 copies its input ⟨Ĥ1⟩ to ⟨Ĥx⟩ then Ĥ0.qx simulates this input with 
> the copy then 
> Ĥ1.q0 copies its input ⟨Ĥ2⟩ to ⟨Ĥy⟩ then Ĥ1.qx simulates this input with 
> the copy then 
> Ĥ2.q0 copies its input ⟨Ĥ3⟩ to ⟨Ĥz⟩ then Ĥ2.qx simulates this input with 
> the copy then ... 
> 
> This is expressed in figure 12.4 as a cycle from qx to q0 to qx. 
> 
> Within the hypothesis that the internal halt decider embedded within Ĥ 
> simulates its input Ĥ applied to its own Turing machine description ⟨Ĥ⟩ 
> derives infinitely nested simulation, unless this simulation is aborted. 
> 
> Self-Evident-Truth (premise[1]) 
> When the pure simulation of a machine on its input never halts we know 
> that the execution of this machine on its input never halts. 

Premise 1 is made by presuming pure_simulation_machine(input) is decidable.
By GUA, pure_simulation_machine(P) tries to predict the property of P, 
therefor pure_simulation_machine(P)  is itself undecidable.
Thus, the reset are unsound.

> Self-Evident-Truth (premise[2]) 
> The ⟨Ĥ⟩ ⟨Ĥ⟩ input to the embedded simulating halt decider at Ĥ.qx is 
> pure simulation that never halts. 
> 
> ∴ Sound Deductive Conclusion 
> The embedded simulating halt decider at Ĥ.qx correctly decides its 
> input: ⟨Ĥ⟩ ⟨Ĥ⟩ is a computation that never halts. 
> 
> Ĥ.q0 ⟨Ĥ⟩ specifies an infinite chain of invocations that is terminated 
> at its third invocation. The first invocation of Ĥ.qx ⟨Ĥ⟩, ⟨Ĥ⟩ is the 
> first element of an infinite chain of invocations. 
> 
> It is common knowledge that when any invocation of an infinite chain of 
> invocations is terminated that the whole chain terminates. That the 
> first element of this infinite chain terminates after its third element 
> has been terminated does not entail that this first element is an actual 
> terminating computation. 
> 
> The above is more clear when you can see the cycle in the state 
> transition diagram of Ĥ(⟨Ĥ⟩) provided in this paper: 
> 
> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation 
> 
> 
> -- 
> Copyright 2021 Pete Olcott 
> 
> "Great spirits have always encountered violent opposition from mediocre 
> minds." Einstein

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

#36481

olcott <NoOne@NoWhere.com> writes:

> On 7/16/2021 8:34 AM, Ben Bacarisse wrote:
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>> 
>>> All extant halting problem proofs appear to be predicated on a
>>> misunderstanding of the following contradiction:
>> I don't think you've read any actual proofs, let along all of them.  Why
>> you would even say such a thing?
>> 
>>> 	Suppose T[R] is a Boolean function taking a routine
>>> 	(or program) R with no formal or free variables as its
>>> 	argument and that for all R, T[R] — True if R terminates
>>> 	if run and that T[R] = False if R does not terminate. Consider
>>> 	the routine P defined as follows
>>>
>>> 		rec routine P
>>> 			§L :if T[P] goto L
>>> 		Return §
>>>
>>> 	If T[P] = True the routine P will loop, and it will
>>> 	only terminate if T[P] = False. In each case T[P] has
>>> 	exactly the wrong value, and this contradiction shows
>>> 	that the function T cannot exist.
>>>
>>> 	[Strachey 1965]
>>>
>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>> recursive
>> T[P] is not recursive.  Maybe you don't understand what the CPL means?
>> Further, this argument must fail for any of the actual proofs that are
>> based on Turing machine because TMs have not functions, not calls and no
>> recursion.
>> 
> Peter Linz Ĥ applied to the Turing machine description of itself: ⟨Ĥ⟩
>
> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
> if M applied to wM halts, and
>
> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
> if M applied to wM does not halt

Why did you not show what you said you'd show?  Were afraid that the
contradiction would be too clear if really did apply Ĥ to ⟨Ĥ⟩?  What you
get is this:

 Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩⊢* Ĥ.qy ∞
 if Ĥ applied to ⟨Ĥ⟩ halts, and

 Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
 if Ĥ applied to ⟨Ĥ⟩ does not halt

!!!

The first two lines say that "Ĥ applied ⟨Ĥ⟩ does not halt if Ĥ applied
to ⟨Ĥ⟩ halts".  The second two say "Ĥ applied ⟨Ĥ⟩ halts if Ĥ applied to
⟨Ĥ⟩ does not halt".

> When we hypothesize that the halt decider embedded in Ĥ is simply a
> UTM then it seems that when the Peter Linz Ĥ is applied to its own
> Turing machine description ⟨Ĥ⟩ this specifies a computation that never
> halts.

Then you enter a fantasy world because a UTM is can't be a halt decider.
But that's not really what you mean.  Don't call it "the Peter Linz Ĥ"
with "the halt decider embedded in Ĥ ... a UTM".  Call it what it is --
the Linz "hat" construction applied to a UTM.  There's a simple notation
for that: UTM^.

The fact that UTM^([UTM^]) is a computation that never halts is
obvious.  You don't need to keep going over stuff that is not in
dispute.

> Within the hypothesis that the internal halt decider embedded within Ĥ
> simulates its input Ĥ applied to its own Turing machine description
> ⟨Ĥ⟩ derives infinitely nested simulation, unless this simulation is
> aborted.

This no parse.

> Self-Evident-Truth (premise[1])
> When the pure simulation of a machine on its input never halts we know
> that the execution of this machine on its input never halts.

Again, never in doubt.  A computation and the simulation of a
computation have the same halting status.  But this is just window
dressing to prime the pump for your garbled "adapted" definition of
halting.

> Self-Evident-Truth (premise[2])
> The ⟨Ĥ⟩ ⟨Ĥ⟩ input to the embedded simulating halt decider at Ĥ.qx is
> pure simulation that never halts.

Not according to you.  Your H (not Linz's non-existent H) is not a pure
simulator.

> ∴ Sound Deductive Conclusion
> The embedded simulating halt decider at Ĥ.qx correctly decides its
> input: ⟨Ĥ⟩ ⟨Ĥ⟩ is a computation that never halts.

We know, from before you realised that being clear was a mistake, that
you claim to have a TM (equivalent), H that rejects <[H^],[H^]> despite
the fact that H^([H^]) is a finite (halting) computation.  Your desire
to reference Linz means I must assume you know that this is the wrong
answer.  H is not a halt decider because is gets at least this one case
wrong.

> Ĥ.q0 ⟨Ĥ⟩ specifies an infinite chain of invocations that is terminated
> at its third invocation.

Apparently so, but you are keeping H hidden, just in case.  The
statement here, along a previous confirmation and an explicit trace you
once mistakenly provided, all go to show that you know that H^([H^]) is
a finite computation.  If you still want to be talking about the halting
problem, that means that H should accept the string <[H^],[H^]>.  But
you tell is it does not.

17 years and you have nothing but a TM that is wrong.  No doubt if I say
that you yourself are telling us it's wrong you'll call me a liar, but
with all these quotes of Linz, and so many references to the accepting
and rejecting states, how could you not know that H should accept
strings that denote halting computations are reject the others?  It's
the very corner stone of what you claim to have been "working" on for 17
years.

-- 
Ben.

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

#36543

On 7/16/2021 7:03 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 7/16/2021 8:34 AM, Ben Bacarisse wrote:
>>> Mr Flibble <flibble@reddwarf.jmc> writes:
>>>
>>>> All extant halting problem proofs appear to be predicated on a
>>>> misunderstanding of the following contradiction:
>>> I don't think you've read any actual proofs, let along all of them.  Why
>>> you would even say such a thing?
>>>
>>>> 	Suppose T[R] is a Boolean function taking a routine
>>>> 	(or program) R with no formal or free variables as its
>>>> 	argument and that for all R, T[R] — True if R terminates
>>>> 	if run and that T[R] = False if R does not terminate. Consider
>>>> 	the routine P defined as follows
>>>>
>>>> 		rec routine P
>>>> 			§L :if T[P] goto L
>>>> 		Return §
>>>>
>>>> 	If T[P] = True the routine P will loop, and it will
>>>> 	only terminate if T[P] = False. In each case T[P] has
>>>> 	exactly the wrong value, and this contradiction shows
>>>> 	that the function T cannot exist.
>>>>
>>>> 	[Strachey 1965]
>>>>
>>>> T is indeed unable to decide P but for the wrong reason: T[P] is
>>>> recursive
>>> T[P] is not recursive.  Maybe you don't understand what the CPL means?
>>> Further, this argument must fail for any of the actual proofs that are
>>> based on Turing machine because TMs have not functions, not calls and no
>>> recursion.
>>>
>> Peter Linz Ĥ applied to the Turing machine description of itself: ⟨Ĥ⟩
>>
>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
>> if M applied to wM halts, and
>>
>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
>> if M applied to wM does not halt
> 
> Why did you not show what you said you'd show?  Were afraid that the
> contradiction would be too clear if really did apply Ĥ to ⟨Ĥ⟩?  What you
> get is this:
> 
>   Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩⊢* Ĥ.qy ∞
>   if Ĥ applied to ⟨Ĥ⟩ halts, and
> 
>   Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
>   if Ĥ applied to ⟨Ĥ⟩ does not halt
> 
> !!!
> 
> The first two lines say that "Ĥ applied ⟨Ĥ⟩ does not halt if Ĥ applied
> to ⟨Ĥ⟩ halts".  The second two say "Ĥ applied ⟨Ĥ⟩ halts if Ĥ applied to
> ⟨Ĥ⟩ does not halt".
> 
>> When we hypothesize that the halt decider embedded in Ĥ is simply a
>> UTM then it seems that when the Peter Linz Ĥ is applied to its own
>> Turing machine description ⟨Ĥ⟩ this specifies a computation that never
>> halts.
> 
> Then you enter a fantasy world because a UTM is can't be a halt decider.
> But that's not really what you mean.  Don't call it "the Peter Linz Ĥ"
> with "the halt decider embedded in Ĥ ... a UTM".  Call it what it is --
> the Linz "hat" construction applied to a UTM.  There's a simple notation
> for that: UTM^.
> 
> The fact that UTM^([UTM^]) is a computation that never halts is
> obvious.  You don't need to keep going over stuff that is not in
> dispute.
> 
>> Within the hypothesis that the internal halt decider embedded within Ĥ
>> simulates its input Ĥ applied to its own Turing machine description
>> ⟨Ĥ⟩ derives infinitely nested simulation, unless this simulation is
>> aborted.
> 
> This no parse.
> 
>> Self-Evident-Truth (premise[1])
>> When the pure simulation of a machine on its input never halts we know
>> that the execution of this machine on its input never halts.
> 
> Again, never in doubt.  A computation and the simulation of a
> computation have the same halting status.  But this is just window
> dressing to prime the pump for your garbled "adapted" definition of
> halting.
> 
>> Self-Evident-Truth (premise[2])
>> The ⟨Ĥ⟩ ⟨Ĥ⟩ input to the embedded simulating halt decider at Ĥ.qx is
>> pure simulation that never halts.
> 
> Not according to you.  Your H (not Linz's non-existent H) is not a pure
> simulator.
> 
>> ∴ Sound Deductive Conclusion
>> The embedded simulating halt decider at Ĥ.qx correctly decides its
>> input: ⟨Ĥ⟩ ⟨Ĥ⟩ is a computation that never halts.
> 
> We know, from before you realised that being clear was a mistake, that
> you claim to have a TM (equivalent), H that rejects <[H^],[H^]> despite
> the fact that H^([H^]) is a finite (halting) computation.  Your desire
> to reference Linz means I must assume you know that this is the wrong
> answer.  H is not a halt decider because is gets at least this one case
> wrong.
> 
>> Ĥ.q0 ⟨Ĥ⟩ specifies an infinite chain of invocations that is terminated
>> at its third invocation.
> 
> Apparently so, but you are keeping H hidden, just in case.  The
> statement here, along a previous confirmation and an explicit trace you
> once mistakenly provided, all go to show that you know that H^([H^]) is
> a finite computation.  If you still want to be talking about the halting
> problem, that means that H should accept the string <[H^],[H^]>.  But
> you tell is it does not.
> 
> 17 years and you have nothing but a TM that is wrong.  No doubt if I say
> that you yourself are telling us it's wrong you'll call me a liar, but
> with all these quotes of Linz, and so many references to the accepting
> and rejecting states, how could you not know that H should accept
> strings that denote halting computations are reject the others?  It's
> the very corner stone of what you claim to have been "working" on for 17
> years.
> 

I only skimmed the above, I skipped most of the words.
int main() { P(P); } is computationally equivalent to Ĥ(⟨Ĥ⟩).

The key difference is that in the latter case almost all of the details 
of the definitions of the TMs must be excluded as impossible to provide.
whereas in the former case a line-by-line complete execution trace of 
the halt status decision is provided.

Any honest person knowing the x86 language has no need to see the 
internals of how H is defined. Simply examining the four execution 
traces and the description of H provides all of the relevant details.

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

-- 
Copyright 2021 Pete Olcott

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

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

#36573

olcott <NoOne@NoWhere.com> writes:
...
> I only skimmed the above, I skipped most of the words.

Good plan.  You really don't want to know what I said!  I've cut it
since you don't care about details.  Let's stick with the big picture.

> int main() { P(P); } is computationally equivalent to Ĥ(⟨Ĥ⟩).

Yes.  P(P) halts (according to you).  H(P,P) == 0 (according to you).
That is wrong (according to everyone but you).

-- 
Ben.

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

#36647

On 7/17/2021 8:32 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> ...
>> I only skimmed the above, I skipped most of the words.
> 
> Good plan.  You really don't want to know what I said!  I've cut it
> since you don't care about details.  Let's stick with the big picture.
> 
>> int main() { P(P); } is computationally equivalent to Ĥ(⟨Ĥ⟩).
> 
> Yes.  P(P) halts (according to you).  H(P,P) == 0 (according to you).
> That is wrong (according to everyone but you).
> 

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt

Unless the simulating halt decider embedded at state Ĥ.qx aborts the 
simulation of its input at some point its input never halts thus proving 
beyond all possible doubt that the input that was aborted is correctly 
decided as never halting.

When a computation only stops running because its simulation was aborted 
this counts as a computation that never halts.


-- 
Copyright 2021 Pete Olcott

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

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

#36673

olcott <NoOne@NoWhere.com> writes:

> When a computation only stops running because its simulation was
> aborted this counts as a computation that never halts.

Me: Every computation that halts, for whatever reason, is a halting
    computation.

You: OK

P(P) halts (according to you).  H(P,P) == 0 (according to you).
That is wrong -- even according to you.

-- 
Ben.

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

#36703

On 7/19/2021 7:35 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> When a computation only stops running because its simulation was
>> aborted this counts as a computation that never halts.
> 
> Me: Every computation that halts, for whatever reason, is a halting
>      computation.
> 
> You: OK
> 

A computation having its simulation aborted never halts even though it 
stops running. Only computation that stop running without having their 
simulation aborted are halting computations.

> P(P) halts (according to you).  H(P,P) == 0 (according to you).
> That is wrong -- even according to you.
> 


-- 
Copyright 2021 Pete Olcott

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

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

#36744

olcott <NoOne@NoWhere.com> writes:

> On 7/19/2021 7:35 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> 
>>> When a computation only stops running because its simulation was
>>> aborted this counts as a computation that never halts.
>> Me: Every computation that halts, for whatever reason, is a halting
>>      computation.
>> You: OK
>
> A computation having its simulation aborted never halts even though it
> stops running. Only computation that stop running without having their
> simulation aborted are halting computations.

P(P) halts.  Stop trying to hide that fact in waffle.  I know you've
realised that it was a mistake to be clear, but you can't obscure a fact
you were once clear about.

>> P(P) halts (according to you).  H(P,P) == 0 (according to you).
>> That is wrong -- even according to you.

-- 
Ben.

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

#36683

On 7/19/21 8:10 AM, olcott wrote:
> On 7/17/2021 8:32 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>> ...
>>> I only skimmed the above, I skipped most of the words.
>>
>> Good plan.  You really don't want to know what I said!  I've cut it
>> since you don't care about details.  Let's stick with the big picture.
>>
>>> int main() { P(P); } is computationally equivalent to Ĥ(⟨Ĥ⟩).
>>
>> Yes.  P(P) halts (according to you).  H(P,P) == 0 (according to you).
>> That is wrong (according to everyone but you).
>>
> 
> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
> if M applied to wM halts, and
> 
> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
> if M applied to wM does not halt
> 
> Unless the simulating halt decider embedded at state Ĥ.qx aborts the
> simulation of its input at some point its input never halts thus proving
> beyond all possible doubt that the input that was aborted is correctly
> decided as never halting.
> 
> When a computation only stops running because its simulation was aborted
> this counts as a computation that never halts.
> 
> 

WRONG. The 'top' H^ was never aborted, but reached its terminal Halting
state and thus shows itself to be a Halting Computation.

It was a COPY of this machine that H aborted, not the original one.

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

#36382

Mr Flibble wrote:
> Hi!
> 
> All extant halting problem proofs appear to be predicated on a

Since you haven't read them all, you are in no position to make such a 
claim.

> misunderstanding of the following contradiction:
> 
> 	Suppose T[R] is a Boolean function taking a routine
> 	(or program) R with no formal or free variables as its
> 	argument and that for all R, T[R] — True if R terminates
> 	if run and that T[R] = False if R does not terminate. Consider
> 	the routine P defined as follows
> 
> 		rec routine P
> 			§L :if T[P] goto L
> 		Return §
> 
> 	If T[P] = True the routine P will loop, and it will
> 	only terminate if T[P] = False. In each case T[P] has
> 	exactly the wrong value, and this contradiction shows
> 	that the function T cannot exist.
> 
> 	[Strachey 1965]
> 
> T is indeed unable to decide P but for the wrong reason: T[P] is
> recursive which means T can never decide if P halts because T never
> halts itself; this mistake appears to have been missed by Strachey as
> the §L <- L loop can't ever loop due to the recursion.
> 
> HOWEVER
> 
> Even if we ignore the error of recursion it does NOT follow that for
> T[Q], T cannot decide if Q halts where Q is a program that does not
> reference T.
> 
> [Strachey 1965] shows us that a decider cannot be part of or called by
> that which is being decided (a pathological program) and given this it
> seems to be unproven that a decider for programs that don't exhibit
> this pathology cannot exist.
> 
> /Flibble
> 
> 


-- 
The world will little note, nor long remember what we say here
Abraham Lincoln at Gettysburg

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

#36386

On Fri, 16 Jul 2021 15:27:53 +0100
Peter <peterxpercival@hotmail.com> wrote:

> Mr Flibble wrote:
> > Hi!
> > 
> > All extant halting problem proofs appear to be predicated on a  
> 
> Since you haven't read them all, you are in no position to make such
> a claim.

Whether or not I am in a position to make such a claim has no bearing
on whether the claim is true or false.  Feel free to refute my claim,
dear.

/Flibble

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

#36394

On 7/16/2021 9:36 AM, Mr Flibble wrote:
> On Fri, 16 Jul 2021 15:27:53 +0100
> Peter <peterxpercival@hotmail.com> wrote:
> 
>> Mr Flibble wrote:
>>> Hi!
>>>
>>> All extant halting problem proofs appear to be predicated on a
>>
>> Since you haven't read them all, you are in no position to make such
>> a claim.
> 
> Whether or not I am in a position to make such a claim has no bearing
> on whether the claim is true or false.  Feel free to refute my claim,
> dear.
> 
> /Flibble
> 
> 

On Saturday, July 10, 2021 at 12:00:56 PM UTC-5, Mr Flibble wrote:
 > I agree with Olcott that a halt decider can NOT be part of that which
  > is being decided (see [Strachey 1965]) which, if Olcott is correct,
  > falsifies a collection of proofs (which I don't have the time to
  > examine) which rely on that mistake.
  >
  > /Flibble

Our claim is that the refutation applies to all cases where the behavior 
of the halt decider is a part of that which is being decided. I named 
this the Pathological self-reference error in 2004.

Now the ball is in Percival's court to dig up some very obscure paper 
that does not depend on the PSR error. The last time that he did this he 
referenced a paper that uses Gödel numbers to hide the PSR error behind 
75 pages of nested formulas.

Sipser, Linz and Kozen proofs as well as all the informal pseudo-code 
proofs utterly depend on the PSR error as their only basis.

-- 
Copyright 2021 Pete Olcott

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

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

#36452

olcott wrote:
> On 7/16/2021 9:36 AM, Mr Flibble wrote:
>> On Fri, 16 Jul 2021 15:27:53 +0100
>> Peter <peterxpercival@hotmail.com> wrote:
>>
>>> Mr Flibble wrote:
>>>> Hi!
>>>>
>>>> All extant halting problem proofs appear to be predicated on a
>>>
>>> Since you haven't read them all, you are in no position to make such
>>> a claim.
>>
>> Whether or not I am in a position to make such a claim has no bearing
>> on whether the claim is true or false.  Feel free to refute my claim,
>> dear.
>>
>> /Flibble
>>
>>
> 
> On Saturday, July 10, 2021 at 12:00:56 PM UTC-5, Mr Flibble wrote:
>  > I agree with Olcott that a halt decider can NOT be part of that which
>   > is being decided (see [Strachey 1965]) which, if Olcott is correct,
>   > falsifies a collection of proofs (which I don't have the time to
>   > examine) which rely on that mistake.
>   >
>   > /Flibble
> 
> Our claim is that the refutation applies to all cases where the behavior 
> of the halt decider is a part of that which is being decided. I named 
> this the Pathological self-reference error in 2004.
> 
> Now the ball is in Percival's court to dig up some very obscure paper 

Why do you want an obscure paper?  Surely a well-known textbook would be 
more convenient, and a reference to a well-known textbook is what I 
recently gave.

> that does not depend on the PSR error. The last time that he did this he 
> referenced a paper that uses Gödel numbers to hide the PSR error behind 
> 75 pages of nested formulas.
> 
> Sipser, Linz and Kozen proofs as well as all the informal pseudo-code 
> proofs utterly depend on the PSR error as their only basis.
> 


-- 
The world will little note, nor long remember what we say here
Abraham Lincoln at Gettysburg

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

#36398

On Friday, 16 July 2021 at 22:36:38 UTC+8, Mr Flibble wrote:
> On Fri, 16 Jul 2021 15:27:53 +0100 
> Peter <peterxp...@hotmail.com> wrote: 
> 
> > Mr Flibble wrote: 
> > > Hi! 
> > > 
> > > All extant halting problem proofs appear to be predicated on a 
> > 
> > Since you haven't read them all, you are in no position to make such 
> > a claim.
> Whether or not I am in a position to make such a claim has no bearing 
> on whether the claim is true or false. Feel free to refute my claim, 
> dear. 
> 
> /Flibble

It sound like you are no longer responsible to your words.

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

#36450

Mr Flibble wrote:
> On Fri, 16 Jul 2021 15:27:53 +0100
> Peter <peterxpercival@hotmail.com> wrote:
> 
>> Mr Flibble wrote:
>>> Hi!
>>>
>>> All extant halting problem proofs appear to be predicated on a
>>
>> Since you haven't read them all, you are in no position to make such
>> a claim.
> 
> Whether or not I am in a position to make such a claim has no bearing
> on whether the claim is true or false.  Feel free to refute my claim,
> dear.
> 
> /Flibble
> 
> 
Ahem... the onus is on you to prove your--utterly implausible--claim.

-- 
The world will little note, nor long remember what we say here
Abraham Lincoln at Gettysburg

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

#36455

On 7/16/2021 4:07 PM, Peter wrote:
> Mr Flibble wrote:
>> On Fri, 16 Jul 2021 15:27:53 +0100
>> Peter <peterxpercival@hotmail.com> wrote:
>>
>>> Mr Flibble wrote:
>>>> Hi!
>>>>
>>>> All extant halting problem proofs appear to be predicated on a
>>>
>>> Since you haven't read them all, you are in no position to make such
>>> a claim.
>>
>> Whether or not I am in a position to make such a claim has no bearing
>> on whether the claim is true or false.  Feel free to refute my claim,
>> dear.
>>
>> /Flibble
>>
>>
> Ahem... the onus is on you to prove your--utterly implausible--claim.
> 

He has already proved that any requirement for a program/TM to return a 
halt status value to an input to does the opposite of whatever the halt 
decider returns is bogus. The meaning of these words proves that such a 
case has the exactly same bogus pattern as the liar paradox.

Generically this can be understood as the scientific principle that the 
dependent variable of a scientific investigation is not allowed to 
interfere with the independent variable.

When P interferes with H this scientific principle is violated. Flibble 
spotted this error and thus has a correct basis for his claim.

On Saturday, July 10, 2021 at 12:00:56 PM UTC-5, Mr Flibble wrote:
  > I agree with Olcott that a halt decider can NOT be part of that which
  > is being decided (see [Strachey 1965]) which, if Olcott is correct,
  > falsifies a collection of proofs (which I don't have the time to
  > examine) which rely on that mistake.
  >
  > /Flibble

-- 
Copyright 2021 Pete Olcott

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

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

#36457

olcott wrote:
> On 7/16/2021 4:07 PM, Peter wrote:
>> Mr Flibble wrote:
>>> On Fri, 16 Jul 2021 15:27:53 +0100
>>> Peter <peterxpercival@hotmail.com> wrote:
>>>
>>>> Mr Flibble wrote:
>>>>> Hi!
>>>>>
>>>>> All extant halting problem proofs appear to be predicated on a
>>>>
>>>> Since you haven't read them all, you are in no position to make such
>>>> a claim.
>>>
>>> Whether or not I am in a position to make such a claim has no bearing
>>> on whether the claim is true or false.  Feel free to refute my claim,
>>> dear.
>>>
>>> /Flibble
>>>
>>>
>> Ahem... the onus is on you to prove your--utterly implausible--claim.
>>
> 
> He has already proved that any requirement for a program/TM to return a 

The claim that I was referring to is that he is in a position to comment 
on _all_ halting problem proofs.

> halt status value to an input to does the opposite of whatever the halt 
> decider returns is bogus. The meaning of these words proves that such a 
> case has the exactly same bogus pattern as the liar paradox.
> 
> Generically this can be understood as the scientific principle that the 
> dependent variable of a scientific investigation is not allowed to 
> interfere with the independent variable.
> 
> When P interferes with H this scientific principle is violated. Flibble 
> spotted this error and thus has a correct basis for his claim.
> 
> On Saturday, July 10, 2021 at 12:00:56 PM UTC-5, Mr Flibble wrote:
>   > I agree with Olcott that a halt decider can NOT be part of that which
>   > is being decided (see [Strachey 1965]) which, if Olcott is correct,
>   > falsifies a collection of proofs (which I don't have the time to
>   > examine) which rely on that mistake.
>   >
>   > /Flibble
> 


-- 
The world will little note, nor long remember what we say here
Abraham Lincoln at Gettysburg

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

#36460

On 7/16/2021 4:25 PM, Peter wrote:
> olcott wrote:
>> On 7/16/2021 4:07 PM, Peter wrote:
>>> Mr Flibble wrote:
>>>> On Fri, 16 Jul 2021 15:27:53 +0100
>>>> Peter <peterxpercival@hotmail.com> wrote:
>>>>
>>>>> Mr Flibble wrote:
>>>>>> Hi!
>>>>>>
>>>>>> All extant halting problem proofs appear to be predicated on a
>>>>>
>>>>> Since you haven't read them all, you are in no position to make such
>>>>> a claim.
>>>>
>>>> Whether or not I am in a position to make such a claim has no bearing
>>>> on whether the claim is true or false.  Feel free to refute my claim,
>>>> dear.
>>>>
>>>> /Flibble
>>>>
>>>>
>>> Ahem... the onus is on you to prove your--utterly implausible--claim.
>>>
>>
>> He has already proved that any requirement for a program/TM to return a 
> 
> The claim that I was referring to is that he is in a position to comment 
> on _all_ halting problem proofs.
> 

Apparently all the other proofs are mutually reducible to/form the 
refuted ones.

>> halt status value to an input to does the opposite of whatever the 
>> halt decider returns is bogus. The meaning of these words proves that 
>> such a case has the exactly same bogus pattern as the liar paradox.
>>
>> Generically this can be understood as the scientific principle that 
>> the dependent variable of a scientific investigation is not allowed to 
>> interfere with the independent variable.
>>
>> When P interferes with H this scientific principle is violated. 
>> Flibble spotted this error and thus has a correct basis for his claim.
>>
>> On Saturday, July 10, 2021 at 12:00:56 PM UTC-5, Mr Flibble wrote:
>>   > I agree with Olcott that a halt decider can NOT be part of that which
>>   > is being decided (see [Strachey 1965]) which, if Olcott is correct,
>>   > falsifies a collection of proofs (which I don't have the time to
>>   > examine) which rely on that mistake.
>>   >
>>   > /Flibble
>>
> 
> 


-- 
Copyright 2021 Pete Olcott

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

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

#36502

olcott wrote:
> On 7/16/2021 4:25 PM, Peter wrote:
>> olcott wrote:
>>> On 7/16/2021 4:07 PM, Peter wrote:
>>>> Mr Flibble wrote:
>>>>> On Fri, 16 Jul 2021 15:27:53 +0100
>>>>> Peter <peterxpercival@hotmail.com> wrote:
>>>>>
>>>>>> Mr Flibble wrote:
>>>>>>> Hi!
>>>>>>>
>>>>>>> All extant halting problem proofs appear to be predicated on a
>>>>>>
>>>>>> Since you haven't read them all, you are in no position to make such
>>>>>> a claim.
>>>>>
>>>>> Whether or not I am in a position to make such a claim has no bearing
>>>>> on whether the claim is true or false.  Feel free to refute my claim,
>>>>> dear.
>>>>>
>>>>> /Flibble
>>>>>
>>>>>
>>>> Ahem... the onus is on you to prove your--utterly implausible--claim.
>>>>
>>>
>>> He has already proved that any requirement for a program/TM to return a 
>>
>> The claim that I was referring to is that he is in a position to 
>> comment on _all_ halting problem proofs.
>>
> 
> Apparently all the other proofs are mutually reducible to/form the 
> refuted ones.

Why is it apparent?  To whom is it apparent?
> 
>>> halt status value to an input to does the opposite of whatever the 
>>> halt decider returns is bogus. The meaning of these words proves that 
>>> such a case has the exactly same bogus pattern as the liar paradox.
>>>
>>> Generically this can be understood as the scientific principle that 
>>> the dependent variable of a scientific investigation is not allowed 
>>> to interfere with the independent variable.
>>>
>>> When P interferes with H this scientific principle is violated. 
>>> Flibble spotted this error and thus has a correct basis for his claim.
>>>
>>> On Saturday, July 10, 2021 at 12:00:56 PM UTC-5, Mr Flibble wrote:
>>>   > I agree with Olcott that a halt decider can NOT be part of that 
>>> which
>>>   > is being decided (see [Strachey 1965]) which, if Olcott is correct,
>>>   > falsifies a collection of proofs (which I don't have the time to
>>>   > examine) which rely on that mistake.
>>>   >
>>>   > /Flibble
>>>
>>
>>
> 
> 


-- 
The world will little note, nor long remember what we say here
Abraham Lincoln at Gettysburg

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

#36391

On 7/16/2021 9:27 AM, Peter wrote:
> Mr Flibble wrote:
>> Hi!
>>
>> All extant halting problem proofs appear to be predicated on a
> 
> Since you haven't read them all, you are in no position to make such a 
> claim.
> 

He is objecting to all the proofs having the pathological 
self-reference(Olcott 2004) error where the input D does the opposite of 
whatever the halt decider H decides. **

This includes all the informal pseudo-code proofs, Sipser, Kozen and 
Linz. I am not aware of any proofs that it excludes.

** Now we construct a new Turing machine D with H as a subroutine. This 
new TM calls H to determine what M does when the input to M is its own 
description ⟨M⟩. Once D has determined this information, it does the 
opposite. http://www.liarparadox.org/Sipser_165_167.pdf


>> misunderstanding of the following contradiction:
>>
>>     Suppose T[R] is a Boolean function taking a routine
>>     (or program) R with no formal or free variables as its
>>     argument and that for all R, T[R] — True if R terminates
>>     if run and that T[R] = False if R does not terminate. Consider
>>     the routine P defined as follows
>>
>>         rec routine P
>>             §L :if T[P] goto L
>>         Return §
>>
>>     If T[P] = True the routine P will loop, and it will
>>     only terminate if T[P] = False. In each case T[P] has
>>     exactly the wrong value, and this contradiction shows
>>     that the function T cannot exist.
>>
>>     [Strachey 1965]
>>
>> T is indeed unable to decide P but for the wrong reason: T[P] is
>> recursive which means T can never decide if P halts because T never
>> halts itself; this mistake appears to have been missed by Strachey as
>> the §L <- L loop can't ever loop due to the recursion.
>>
>> HOWEVER
>>
>> Even if we ignore the error of recursion it does NOT follow that for
>> T[Q], T cannot decide if Q halts where Q is a program that does not
>> reference T.
>>
>> [Strachey 1965] shows us that a decider cannot be part of or called by
>> that which is being decided (a pathological program) and given this it
>> seems to be unproven that a decider for programs that don't exhibit
>> this pathology cannot exist.
>>
>> /Flibble
>>
>>
> 
> 


-- 
Copyright 2021 Pete Olcott

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

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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.theory

csiph-web