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


Groups > comp.theory > #32182

Re: Is this a legit TM?

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Is this a legit TM?
Date 2021-04-26 11:13 +0100
Organization A noiseless patient Spider
Message-ID <8735vdicaq.fsf@bsb.me.uk> (permalink)
References (1 earlier) <CBchI.151620$N_4.88620@fx36.iad> <s64oh1$1vbf$1@gioia.aioe.org> <tjnhI.128761$ST2.90519@fx47.iad> <s65ccn$81f$1@gioia.aioe.org> <181a8021-71f7-498c-80ac-78b1edf9844bn@googlegroups.com>

Show all headers | View raw


Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On Monday, 26 April 2021 at 04:34:50 UTC+1, Chris M. Thomasson wrote:
>> On 4/25/2021 4:55 PM, Richard Damon wrote: 
>> > On 4/25/21 5:55 PM, Chris M. Thomasson wrote: 
>> >> 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. 
>> > 
>> > THe prooble is when we get to 10, that would be 
>> > [9] -> [,] -> [1] -> [0] -> [,] 
>> > 
>> > You need a finite alphabet on the tape,
>> What about 256-ary? 0x00...0xFF? Each cell can be a byte, sound Kosher? 

Yes, any finite set will do.

> You'll find it easier to work with binary.

Is that because there are fewer symbols to deal with?  Very often, it's
even easier to deal with unary -- tally-stick -- numbers.

But I don't think any actual advice can be given until we know what CMT
is planning to do with this tape of numbers.  That's what will determine
the best way to represent it.

> Leading 1 is always present, ...

Why?  (The answer may come down to the answer to the next one.)

> ... and the tape looks like this
> 1<>10<>11<>100<>101<>110<>111<>1000 ...

Is <> your way to write a blank?

TMs are hardly "practical" but when playing with them to learn, it's
almost always best to try to arrange the tapes to have the pattern

 ... _ _ _ _ X X X X X X _ _ _ ....

i.e. to have just one contiguous sequence of non-blank symbols.

> I'm not sure how to write a function which takes a tape position index and 
> calulates the digit. It must be possible. Then you can implement an infinite
> tape of natural numbers.

I think you've moved for what such an extra tape looks like to how to
make the extra tape "virtual", yes?  Otherwise, I can't see why you'd
want an index to digit TM.

Unary makes that much easier, though it's a mark of how everything is so
fiddly with a TM that it's not trivial even then.

-- 
Ben.

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