Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #39978 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2021-09-27 13:23 -0500 |
| Last post | 2021-09-27 21:23 -0500 |
| Articles | 5 — 2 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-09-27 13:23 -0500
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-27 21:19 +0100
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-09-27 15:59 -0500
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-09-28 02:53 +0100
Re: Infinitely Recursive input on HP Proofs olcott <NoOne@NoWhere.com> - 2021-09-27 21:23 -0500
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-09-27 13:23 -0500 |
| Subject | Re: Infinitely Recursive input on HP Proofs |
| Message-ID | <SdOdnfiimLmQkc_8nZ2dnUU7-S3NnZ2d@giganews.com> |
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.
>
This post is my earliest USENET post regarding this key insight:
The halting theorem counter-examples present infinitely nested
simulation (non-halting) behavior to every simulating halt decider.
Here is the original published reference (August 2016) to this same idea:
It looks like the original specification provided
in the Linz text may be infinitely recursive in that
each TM requires its own input. We fix this by providing
simple input that definitely halts.
https://www.researchgate.net/publication/307509556_Self_Modifying_Turing_Machine_SMTM_Solution_to_the_Halting_Problem_concrete_example
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-09-27 21:19 +0100 |
| Message-ID | <8735ppu5yo.fsf@bsb.me.uk> |
| In reply to | #39978 |
olcott <NoOne@NoWhere.com> writes: > 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. > > This post is my earliest USENET post regarding this key insight: > > The halting theorem counter-examples present infinitely nested > simulation (non-halting) behavior to every simulating halt decider. It staggering that you don't even understand what you wrote in 2017. Your incorrect analysis applies to any "hat" TM constructed as per Linz. It has nothing to do with simulation, but to do with your not understanding Linz. (To be fair, there is an error in the notation -- corrected in the words of the book -- that could lead you this incorrect notion.) What's remarkable is that you don't remember this as one of the few times you were right and I agreed with you. The double use of q0 (only clarified in the text) was a poor choice by Linz. You are, however, correct that if we made a partial decider from a UTM (let's call it U), then U(<U^>, <U^>) is non-halting. You are wrong about most of the details (you still won't accept that there is no "loop" back to state U.q0) but you will get endless virtual nested simulations. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-09-27 15:59 -0500 |
| Message-ID | <ANydnQy8efM6rc_8nZ2dnUU7-afNnZ2d@giganews.com> |
| In reply to | #39984 |
On 9/27/2021 3:19 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> 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. >> >> This post is my earliest USENET post regarding this key insight: >> >> The halting theorem counter-examples present infinitely nested >> simulation (non-halting) behavior to every simulating halt decider. > > It staggering that you don't even understand what you wrote in 2017. > Your incorrect analysis applies to any "hat" TM constructed as per Linz. > It has nothing to do with simulation, but to do with your not > understanding Linz. (To be fair, there is an error in the notation -- > corrected in the words of the book -- that could lead you this incorrect > notion.) > > What's remarkable is that you don't remember this as one of the few > times you were right and I agreed with you. The double use of q0 (only > clarified in the text) was a poor choice by Linz. > > You are, however, correct that if we made a partial decider from a UTM > (let's call it U), then U(<U^>, <U^>) is non-halting. You are wrong > about most of the details (you still won't accept that there is no > "loop" back to state U.q0) but you will get endless virtual nested > simulations. > So then that is a key very significant step of my technical progress and a key element in the progress of our dialogue. I will be able to encode the actual Linz proof that does copy its input and the simulating halt decider will be a pure function. -- 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-09-28 02:53 +0100 |
| Message-ID | <87y27hqxch.fsf@bsb.me.uk> |
| In reply to | #39989 |
olcott <NoOne@NoWhere.com> writes: > On 9/27/2021 3:19 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> 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. >>> >>> This post is my earliest USENET post regarding this key insight: >>> >>> The halting theorem counter-examples present infinitely nested >>> simulation (non-halting) behavior to every simulating halt decider. >> >> It staggering that you don't even understand what you wrote in 2017. >> Your incorrect analysis applies to any "hat" TM constructed as per Linz. >> It has nothing to do with simulation, but to do with your not >> understanding Linz. (To be fair, there is an error in the notation -- >> corrected in the words of the book -- that could lead you this incorrect >> notion.) >> >> What's remarkable is that you don't remember this as one of the few >> times you were right and I agreed with you. The double use of q0 (only >> clarified in the text) was a poor choice by Linz. >> >> You are, however, correct that if we made a partial decider from a UTM >> (let's call it U), then U(<U^>, <U^>) is non-halting. You are wrong >> about most of the details (you still won't accept that there is no >> "loop" back to state U.q0) but you will get endless virtual nested >> simulations. > > So then that is a key very significant step of my technical progress > and a key element in the progress of our dialogue. Again? How often do you want to take this step? > I will be able to encode the actual Linz proof that does copy its > input and the simulating halt decider will be a pure function. All TM computations are pure functions. Do you plant to learn anything about them in the near future? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-09-27 21:23 -0500 |
| Message-ID | <9oGdnWi1t-EH4c_8nZ2dnUU7-f_NnZ2d@giganews.com> |
| In reply to | #40002 |
On 9/27/2021 8:53 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 9/27/2021 3:19 PM, Ben Bacarisse wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> 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. >>>> >>>> This post is my earliest USENET post regarding this key insight: >>>> >>>> The halting theorem counter-examples present infinitely nested >>>> simulation (non-halting) behavior to every simulating halt decider. >>> >>> It staggering that you don't even understand what you wrote in 2017. >>> Your incorrect analysis applies to any "hat" TM constructed as per Linz. >>> It has nothing to do with simulation, but to do with your not >>> understanding Linz. (To be fair, there is an error in the notation -- >>> corrected in the words of the book -- that could lead you this incorrect >>> notion.) >>> >>> What's remarkable is that you don't remember this as one of the few >>> times you were right and I agreed with you. The double use of q0 (only >>> clarified in the text) was a poor choice by Linz. >>> >>> You are, however, correct that if we made a partial decider from a UTM >>> (let's call it U), then U(<U^>, <U^>) is non-halting. You are wrong >>> about most of the details (you still won't accept that there is no >>> "loop" back to state U.q0) but you will get endless virtual nested >>> simulations. >> >> So then that is a key very significant step of my technical progress >> and a key element in the progress of our dialogue. > > Again? How often do you want to take this step? > >> I will be able to encode the actual Linz proof that does copy its >> input and the simulating halt decider will be a pure function. > > All TM computations are pure functions. Do you plant to learn anything > about them in the near future? > Because I had to make sure that my C code mapped to a TM computation I really dug into this aspect of it. Pure functions turn out to be the key. (1) The function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams). (2) The function application has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or input/output streams). https://en.wikipedia.org/wiki/Pure_function It turns out the the easiest way to transform my algorithm into a pure function was to implement the copying the input aspect of Linz. Because of the way that pure functions work my proof was made very much simpler. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [standalone]
Back to top | Article view | comp.theory
csiph-web