Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | André G. Isaak <agisaak@gm.invalid> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Infinitely Recursive input on HP Proofs |
| Date | 2021-05-16 19:15 -0600 |
| Organization | Christians and Atheists United Against Creeping Agnosticism |
| Message-ID | <s7sg34$94t$1@dont-email.me> (permalink) |
| References | (3 earlier) <0sCdnWsgz4JPGjz9nZ2dnUU7-RvNnZ2d@giganews.com> <R%foI.542844$nn2.335922@fx48.iad> <-rednavQTY_BDTz9nZ2dnUU7-SXNnZ2d@giganews.com> <_yhoI.542847$nn2.449398@fx48.iad> <EsCdnduL051HNTz9nZ2dnUU7-d_NnZ2d@giganews.com> |
On 2021-05-16 17:21, olcott wrote: > On 5/16/2021 6:05 PM, Richard Damon wrote: >> On 5/16/21 5:37 PM, olcott wrote: >>> On 5/16/2021 4:19 PM, Richard Damon wrote: >>>> On 5/16/21 5:00 PM, olcott wrote: >>>>> On 5/16/2021 3:21 PM, Ben Bacarisse wrote: >>>>>> olcott <NoOne@NoWhere.com> writes: >>>>>> >>>>>>> Any genius knowing the theory of computation quite well can easily >>>>>>> confirm that Ĥ(Ĥ) specifies the non halting behavior pattern of >>>>>>> [infinitely_nested_simulation] to every simulating halt decider. >>>>>>> This equally applies to all of the halting problem instances. >>>>>>> >>>>>>> Ĥ(Ĥ) is short-hand for: >>>>>>> Now Ĥ is a Turing machine, so that it will have some description in >>>>>>> Σ*, >>>>>>> say ŵ. This string, in addition to being the description of Ĥ can >>>>>>> also be used >>>>>>> as input string. We can therefore legitimately ask what would happen >>>>>>> if Ĥ is >>>>>>> applied to ŵ. (Linz:1990:320) >>>>>>> >>>>>>> Linz, Peter 1990. An Introduction to Formal Languages and >>>>>>> Automata. Lexington/Toronto: D. C. Heath and Company. (315-320) >>>>>> >>>>>> Nonsense. H is the name given in Linz to a non-existent Turing >>>>>> machine. H^, derived from it, also does not exit. Anyone who has >>>>>> read >>>>>> that book should know that H^([H^]) specifies no behaviour at all. >>>>>> >>>>>> You have constructed a poor-man's partial decider that gets the "hat" >>>>>> case wrong, but you can't justify the wrong answer by appeal Linz. >>>>>> >>>>>> Your "infinitely nested simulation" explanation for your decider >>>>>> giving >>>>>> the wrong answer can be put on a more formal basis, but you can't >>>>>> do by >>>>>> re-using the names of nonexistent TM's from Linz. >>>>>> >>>>> >>>>> Well I won't say that you are not a genius or that you don't know the >>>>> theory of computation very well. >>>>> >>>>> The actual Ĥ(<Ĥ>) does specify [infinitely_nested_simulation] to every >>>>> simulating halt decider. This [infinitely_nested_simulation] is more >>>>> complex than the one that Halts recognizes. >>>>> >>>>> Ĥ.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 decides 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. >>>>> >>>>> It can be understood from the above specification that when the >>>>> embedded >>>>> halt decider @Ĥ.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 @Ĥ.qx stops simulating its input. >>>> >>>> BUT, since H is required to be finite in execution, the copy of H >>>> within >>>> H^ must have some alteration from a simple simulator to break the loop. >>>> >>>> If it does, then it WILL break the loop, and be finite in execution. >>>> >>>> If it doesn't then H(H^,H^) won't break the loop, and thus will not >>>> answer in finite time and thus fail to give an answer and not be a >>>> decider. >>>> >>> >>> That is why we need this truism to dislodge the pathological >>> self-reference: >>> >>> 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. >>> >>> Whether a computation is finite is more nuanced than it simply stops >>> running otherwise an infinite loop that had its simulation aborted >>> because its behavior matched the [infinite_loop] non-halting behavior >>> pattern would have to be classified as a halting computation. >>> >>> Unless the simulating halt decider stops simulating Ĥ(Ĥ) at some point >>> its simulation would be infinite ∴ meets the non-halting truism. >>> >> >> But you can't use a 'Falsism' to change the facts about the definition. >> >> And, as I have said, there IS no pathological self-reference in the >> problem. >> >> YOU create the self-reference by not implementing the required copy >> operation. In actuality the Linz proof has no real self-reference, just >> two copies of what just happens to be the same thing. >> > > I am referring to the complete Peter Linz version where a copy <is> made. > > Ĥ.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 decides 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. > > It can be understood from the above specification that when the embedded > halt decider @Ĥ.qx bases its halting decision on simulating its input, > and it has (Ĥ, Ĥ) as its input that: But Linz's specification doesn't make any mention of simulating the input, so there isn't anything intrinsincally recursive about Linz's specification. It's only *your* decision to employ simulation which leads to potentially infinite recursion. The actual specification involves no self-reference or recursion. André -- To email remove 'invalid' & replace 'gm' with well known Google mail service.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 14:09 -0500
Re: Infinitely Recursive input on HP Proofs Jeff Barnett <jbb@notatt.com> - 2021-05-16 13:46 -0600
Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 19:05 -0400
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 18:21 -0500
Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 21:11 -0400
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 21:01 -0500
Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 23:18 -0400
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 22:23 -0500
Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 07:11 -0400
Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 07:26 -0400
Re: Infinitely Recursive input on HP Proofs Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-05-17 05:45 -0700
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-17 10:23 -0500
Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 20:41 -0400
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-17 20:27 +0100
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-17 14:31 -0500
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-18 01:38 +0100
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-17 19:54 -0500
Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 21:21 -0400
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-20 12:57 +0100
Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-17 20:43 -0400
Re: Infinitely Recursive input on HP Proofs André G. Isaak <agisaak@gm.invalid> - 2021-05-16 19:15 -0600
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 20:34 -0500
Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 21:55 -0400
Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 15:56 -0400
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-16 21:21 +0100
Re: Infinitely Recursive input on HP Proofs Richard Damon <Richard@Damon-Family.org> - 2021-05-16 17:19 -0400
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 16:37 -0500
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-05-16 16:00 -0500
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-17 02:19 +0100
Re: Infinitely Recursive input on HP Proofs (Full Linz text) olcott <NoOne@NoWhere.com> - 2021-05-16 20:54 -0500
Re: Infinitely Recursive input on HP Proofs (Full Linz text) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-18 01:57 +0100
Re: Infinitely Recursive input on HP Proofs (eternally on this point) olcott <NoOne@NoWhere.com> - 2021-05-17 20:34 -0500
csiph-web