Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #33708 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2021-05-16 14:09 -0500 |
| Last post | 2021-05-17 20:34 -0500 |
| Articles | 12 on this page of 32 — 6 participants |
Back to article view | Back to comp.theory
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
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
Page 2 of 2 — ← Prev page 1 [2]
| From | André G. Isaak <agisaak@gm.invalid> |
|---|---|
| Date | 2021-05-16 19:15 -0600 |
| Message-ID | <s7sg34$94t$1@dont-email.me> |
| In reply to | #33735 |
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.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-16 20:34 -0500 |
| Message-ID | <it-dnVe8wa5OWjz9nZ2dnUU7-emdnZ2d@giganews.com> |
| In reply to | #33741 |
On 5/16/2021 8:15 PM, André G. Isaak wrote: > 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é > Simulating halt decider H correctly decides non-halting on its input (Ĥ,Ĥ) on the basis of this truism: 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. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-05-16 21:55 -0400 |
| Message-ID | <52koI.84709$qy1.16481@fx26.iad> |
| In reply to | #33746 |
On 5/16/21 9:34 PM, olcott wrote: > On 5/16/2021 8:15 PM, André G. Isaak wrote: >> 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é >> > > Simulating halt decider H correctly decides non-halting on its input > (Ĥ,Ĥ) on the basis of this truism: > > 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. > > But not a correct halting decider if it makes a wrong decision based on this not quite truism.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-05-16 15:56 -0400 |
| Message-ID | <tNeoI.197819$sd3.1379@fx02.iad> |
| In reply to | #33708 |
On 5/16/21 3:09 PM, olcott wrote: > On 3/11/2017 3:13 PM, peteolcott wrote: >> http://LiarParadox.org/HP_Infinite_Recursion.pdf >> >> As this page 319 of An Introduction to Formal Languages and Automata >> by Peter Linz 1990 indicates >> >> From H' we construct another Turing machine H-Hat. This new machine >> takes as input Wm, copies it then behaves exactly like H'. >> q0 Wm |-* H-Hat q0 Wm Wm... >> >> Page 320 indicates that we apply H-Hat to itself as input. >> >> The problem is that every H-Hat needs a pair of inputs. >> >> H-Hat takes an H-Hat as input and copies it so that it >> can analyze how its input H-hat would analyze the copy >> of H-Hat that it just made. >> >> The input H-Hat would have to copy its own input H-Hat >> so that it can analyze what its own input H-Hat would >> do on its own input, on and on forever... >> >> Copyright 2016 and 2017 Pete Olcott. >> > > 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. Only if said genius is blind, and doesn't look at the actual behavior of H^(H^) which even YOU admit halts. That a simulation Halt Decider can't decide it doesn't make it non-halting, just that simulation can't handle that type of machine, which is the fault of the design of the desider. H^(H^) CAN'T be infinitely recursive, as H(P, I) is required to be halting for ALL possible inputs P and I, so must be for H^, H^. > > Ĥ(Ĥ) 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) > > http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf > > Yes, and since H is defined to be finite in execution for all inputs, H^ can not get locked into an infinite recursion. H^ CAN have infinite execution, but only if H says H(H^,H^) is a halting computation. The other possibility is if H fails to meet the requirement of being non-Halting, but in that case, H failed to qualify for the proof, so it doesn't need to be refuted. So, the only way you can say that H^(H^) has infinite recursion is to admit that H(H^, H^) also has infinite recursion and thus fails to qualify as a decider in the first place.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-05-16 21:21 +0100 |
| Message-ID | <87im3i5t12.fsf@bsb.me.uk> |
| In reply to | #33708 |
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. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-05-16 17:19 -0400 |
| Message-ID | <R%foI.542844$nn2.335922@fx48.iad> |
| In reply to | #33721 |
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. The ONLY way you can get one without the other is for H to NOT be a computation, and thus it can't be a Turing Machine, so your argument about working with true Turing Equivalents is false. PERIOD. You had to move out of Turing Machine because you can't do it as Turing Machines, which means that something you have claimed to be a 'Turing Equivalent' isn't. > > Linz, Peter 1990. An Introduction to Formal Languages and Automata. > Lexington/Toronto: D. C. Heath and Company. > > So it seems to be the same as it was more than four years ago you are so > biased against either me or my position (or both) that you simply won't > pay enough attention to see that I am right. > > The key evidence that I am right and you just don't see it is the lack > of any correct rebuttal. > > That the actual Ĥ(<Ĥ>) does specify [infinitely_nested_simulation] to > every simulating halt decider can't be refuted simply because <it is> > the case. > >
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-16 16:37 -0500 |
| Message-ID | <-rednavQTY_BDTz9nZ2dnUU7-SXNnZ2d@giganews.com> |
| In reply to | #33728 |
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. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-16 16:00 -0500 |
| Message-ID | <0sCdnWsgz4JPGjz9nZ2dnUU7-RvNnZ2d@giganews.com> |
| In reply to | #33721 |
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. Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. So it seems to be the same as it was more than four years ago you are so biased against either me or my position (or both) that you simply won't pay enough attention to see that I am right. The key evidence that I am right and you just don't see it is the lack of any correct rebuttal. That the actual Ĥ(<Ĥ>) does specify [infinitely_nested_simulation] to every simulating halt decider can't be refuted simply because <it is> the case. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-05-17 02:19 +0100 |
| Message-ID | <87bl9a40nr.fsf@bsb.me.uk> |
| In reply to | #33736 |
olcott <NoOne@NoWhere.com> writes: > 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. No. H and H^ specify no behaviour. These lines: > Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞ > Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn (with the text below) specify the behaviour of no Turing machine. > 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. The above is Linz (except for the altered specification). But this is all yours: > 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. > > Linz, Peter 1990. An Introduction to Formal Languages and > Automata. Lexington/Toronto: D. C. Heath and Company. You should not attribute your junk to Linz. Linz of course does not limit how a decider might be written because he wants to make general claims, not specific ones. And you want to pretend that the finite nested simulations you show can be called infinitely nested simulation and no one will notice! Sorry, I noticed the last time, and I'm pointing it out again. > So it seems to be the same as it was more than four years ago you are > so biased against either me or my position (or both) that you simply > won't pay enough attention to see that I am right. > > The key evidence that I am right and you just don't see it is the lack > of any correct rebuttal. Talk junk and I'll correct it -- stop talking junk and I won't have anything to correct. Stop saying that a nonexistent TM specifies any behaviour at all. Stop saying that Linz's H shows nested simulation when it's your badly conceived decider uses simulation. Stop saying that explicitly finite nested simulation is infinite nested simulation. Stop saying that whether a computation is finite is more nuanced than it simply stops running. Stop saying that the fact that a computation halts does not entail that it is a halting computation. Stop pretending that your silly-not-halting problem is the halting problem. We are up to our necks in garbage now. > That the actual Ĥ(<Ĥ>) does specify [infinitely_nested_simulation] to > every simulating halt decider can't be refuted simply because <it is> > the case. The nonexistent H^ based on the nonexistent H that does not necessarily simulate anything but which you show performing explicitly finite nested simulation? That's the "actual" H^(H^) you claim specifies infinite nested simulation? You have lost touch with reality. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-16 20:54 -0500 |
| Subject | Re: Infinitely Recursive input on HP Proofs (Full Linz text) |
| Message-ID | <KKidnYZUNMQlUTz9nZ2dnUU7-f_NnZ2d@giganews.com> |
| In reply to | #33743 |
On 5/16/2021 8:19 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> 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. > > No. H and H^ specify no behaviour. These lines: > >> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞ >> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn > > (with the text below) specify the behaviour of no Turing machine. > >> 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. > > The above is Linz (except for the altered specification). But this is > all yours: > >> 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. In other words you are saying that the following Linz text would not specify the above behavior to a simulating halt decider H? Proof: We assume the contrary, namely that there exists an algorithm, and consequently some Turing machine H, that solves the halting problem. The input to H will be the description (encoded in some form) of M, say wM, as well as the input w. The requirement is then that, given any (wM, w), the Turing machine H will halt with either a yes or no answer. We achieve this by asking that H halt in one of two corresponding final states, say, qy or qn. The situation can be visualized by a block diagram like Figure 12.1. The intent of this diagram is to indicate that, if M is started in state q0 with input (wM, w), it will eventually halt in state qy or qn. As required by Definition 12.1, we want H to operate according to the following rules: H.qx wM wM ⊢* H.qy if M applied to w halts, and H.qx wM wM ⊢* H.qn if M applied to w does not halt Next, we modify H to produce a Turing machine H' with the structure shown in Figure 12.2. With the added states in Figure 12.2 we want to convey that the transitions between state qy and the new states qa and qb are to be made, regardless of the tape symbol, in such a way that the tape remains unchanged. The way this is done is straightforward. Comparing H and H' we see that, in situations where H reaches qy and halts, the modified machine H' will enter an infinite loop. From H' we construct another Turing machine Ĥ. This new machine takes as input wM, copies it, and then behaves exactly like H'. Then the action of Ĥ is such that Ĥ.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 -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-05-18 01:57 +0100 |
| Subject | Re: Infinitely Recursive input on HP Proofs (Full Linz text) |
| Message-ID | <87r1i4270b.fsf@bsb.me.uk> |
| In reply to | #33747 |
olcott <NoOne@NoWhere.com> writes: > On 5/16/2021 8:19 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> 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. >> >> No. H and H^ specify no behaviour. These lines: >> >>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞ >>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn >> >> (with the text below) specify the behaviour of no Turing machine. >> >>> 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. >> >> The above is Linz (except for the altered specification). But this is >> all yours: >> >>> 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. > > In other words... Generally not a good start. You almost always don't understand what I'm saying (or you misrepresent it). > you are saying that the following Linz text would not specify the > above behavior to a simulating halt decider H? No, I am not saying that. But you've cut what I said about the above. If you want to try to understand what I said about the above, go find it and ask a few questions about it. <cut bits from Linz> -- Ben. "the fact that a computation halts does not entail that it is a halting computation" Peter Olcott, May 2021.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-17 20:34 -0500 |
| Subject | Re: Infinitely Recursive input on HP Proofs (eternally on this point) |
| Message-ID | <woOdnS4xSJ_phD79nZ2dnUU7-UfNnZ2d@giganews.com> |
| In reply to | #33820 |
On 5/17/2021 7:57 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 5/16/2021 8:19 PM, Ben Bacarisse wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> 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. >>> >>> No. H and H^ specify no behaviour. These lines: >>> >>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞ >>>> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn >>> >>> (with the text below) specify the behaviour of no Turing machine. >>> >>>> 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. >>> >>> The above is Linz (except for the altered specification). But this is >>> all yours: >>> >>>> 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. >> >> In other words... > > Generally not a good start. You almost always don't understand what I'm > saying (or you misrepresent it). > >> you are saying that the following Linz text would not specify the >> above behavior to a simulating halt decider H? > > No, I am not saying that. Ĥ.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 you understand and agree that the above sequence would be the sequence derived when the copy of H @Ĥ.qx is a simulating halt decider for this computation Ĥ(<Ĥ>) then you and I have to stay eternally on this point until we do have a mutual understanding. > But you've cut what I said about the above. > If you want to try to understand what I said about the above, go find it > and ask a few questions about it. > > <cut bits from Linz> > -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [standalone]
Page 2 of 2 — ← Prev page 1 [2]
Back to top | Article view | comp.theory
csiph-web