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


Groups > comp.theory > #32164

Re: Is this a legit TM?

From "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups comp.theory
Subject Re: Is this a legit TM?
Date 2021-04-25 14:55 -0700
Organization Aioe.org NNTP Server
Message-ID <s64oh1$1vbf$1@gioia.aioe.org> (permalink)
References <s63382$1vqu$1@gioia.aioe.org> <CBchI.151620$N_4.88620@fx36.iad>

Show all headers | View raw


On 4/25/2021 4:43 AM, Richard Damon wrote:
> On 4/25/21 2:46 AM, Chris M. Thomasson wrote:
>> Think of a TM with three tapes, [t0...t2], where:
>>
>> t0 = the natural numbers starting at zero
>> t1 = an infinite tape of random bits generated by a TRNG, 0 or 1.
>> t2 = a program
>>
> 
> No. Not if you are implying that each natural number on t0 is a single
> cell on the tape. It could be a tape with each of the natural numbers
> encoded on the tape, and you move it by one 'Number' each step. Maybe it
> is encoded with the digits 0-9 plus comma, with a comma between each
> number, and you move to the next comma.

Okay. I was thinking of each "cell" being a natural number. Adding in 
commas would work fine. So, the cells of the tape could be:

[0]->[,]->[1]->[,]->[2]->[,]...

Is that better? Or, are the commas actually "necessary"?

[0]->[1]->[2]->[3]->...

So, moving one cell per step to the right should do it. Am I still 
missing something? Thanks Richard.


> 
> This is because the 'alphabet' of a Turing Machine Tape is Finite.
> 
> Also, while you define t1 as being set be a TRNG, by theory it is now an
> input and fixed for a given computation, so to repeat that computation
> you give it the exact same TRNG sequence, so it is no longer really
> 'random'.
> 
>> t2 is the main driver of this "TM".
>>
>> So, the "TM" starts reading and processing t2. For each move of the
>> head, it moves the head one position to the right for both t0 and t1.
>> So, if t2 halts, the current position of t0 will tell exactly how many
>> moves the head made for processing t2, and t1 will show the random bit
>> at halting. So, lets say t2 was a simple program that simply said move 2
>> positions to the right.
>>
>> So, initial setup:
>>
>> t0[0] = 0
>> t1[0] = say, 0, being random, flip a coin
>> t3[0] = move 2 to the right
>>
>> Lets move two position to the right, one at a time:
>>
>> t0[1] = 1
>> t1[1] = flip coin, 0
>> t2[1] = in progress
>>
>> t0[2] = 2
>> t1[2] = flip coin, 1
>> t2[2] = halt
>>
>>
>> t0[2] = 2 means it took two steps, and t1[2] = 1 is the current random
>> bit, t2[2] = halt means we are finished.
>>
>> Has somebody created a physical TM that reads tapes with QR codes on
>> them? lol. ;^)
>>
>>
>>
> 

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


Thread

Is this a legit TM? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-24 23:46 -0700
  Re: Is this a legit TM? Richard Damon <Richard@Damon-Family.org> - 2021-04-25 07:43 -0400
    Re: Is this a legit TM? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-25 14:55 -0700
      Re: Is this a legit TM? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-25 23:44 +0100
        Re: Is this a legit TM? Richard Damon <Richard@Damon-Family.org> - 2021-04-25 19:57 -0400
          Re: Is this a legit TM? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-26 01:58 +0100
            Re: Is this a legit TM? Richard Damon <Richard@Damon-Family.org> - 2021-04-25 22:11 -0400
      Re: Is this a legit TM? Richard Damon <Richard@Damon-Family.org> - 2021-04-25 19:55 -0400
        Re: Is this a legit TM? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-25 20:34 -0700
          Re: Is this a legit TM? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-04-26 01:35 -0700
            Re: Is this a legit TM? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-26 11:13 +0100
              Re: Is this a legit TM? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-04-26 03:35 -0700
          Re: Is this a legit TM? Richard Damon <Richard@Damon-Family.org> - 2021-04-26 07:00 -0400
            Re: Is this a legit TM? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-04-26 14:26 +0100
              Re: Is this a legit TM? Richard Damon <Richard@Damon-Family.org> - 2021-04-26 09:35 -0400
                Re: Is this a legit TM? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-04-26 07:19 -0700

csiph-web