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


Groups > comp.theory > #39978 > unrolled thread

Re: Infinitely Recursive input on HP Proofs

Started byolcott <NoOne@NoWhere.com>
First post2021-09-27 13:23 -0500
Last post2021-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.


Contents

  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

#39978 — Re: Infinitely Recursive input on HP Proofs

Fromolcott <NoOne@NoWhere.com>
Date2021-09-27 13:23 -0500
SubjectRe: 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]


#39984

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-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]


#39989

Fromolcott <NoOne@NoWhere.com>
Date2021-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]


#40002

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-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]


#40005

Fromolcott <NoOne@NoWhere.com>
Date2021-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