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


Groups > comp.theory > #32135

Is this a legit TM?

From "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups comp.theory
Subject Is this a legit TM?
Date 2021-04-24 23:46 -0700
Organization Aioe.org NNTP Server
Message-ID <s63382$1vqu$1@gioia.aioe.org> (permalink)

Show all headers | View raw


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

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 — 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