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


Groups > comp.theory > #39984

Re: Infinitely Recursive input on HP Proofs

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Infinitely Recursive input on HP Proofs
Date 2021-09-27 21:19 +0100
Organization A noiseless patient Spider
Message-ID <8735ppu5yo.fsf@bsb.me.uk> (permalink)
References <918df253-d4f0-4370-8f73-88e6690380a1@googlegroups.com> <SdOdnfiimLmQkc_8nZ2dnUU7-S3NnZ2d@giganews.com>

Show all headers | View raw


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.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

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

csiph-web