Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Halting Problem proofs appear to be bogus! |
| Date | 2021-07-17 01:03 +0100 |
| Organization | A noiseless patient Spider |
| Message-ID | <87sg0dolgt.fsf@bsb.me.uk> (permalink) |
| References | <20210716142416.00003996@reddwarf.jmc> <871r7ys7pd.fsf@bsb.me.uk> <INqdnZRsHJyUCWz9nZ2dnUU7-afNnZ2d@giganews.com> |
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.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web