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


Groups > comp.theory > #32191

Re: Is this a legit TM?

Path csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Is this a legit TM?
Date Mon, 26 Apr 2021 14:26:50 +0100
Organization A noiseless patient Spider
Lines 71
Message-ID <87lf95gorp.fsf@bsb.me.uk> (permalink)
References <s63382$1vqu$1@gioia.aioe.org> <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> <p3xhI.116120$Qf2.1317@fx38.iad>
Mime-Version 1.0
Content-Type text/plain
Injection-Info reader02.eternal-september.org; posting-host="26db97268589d0ee1907bfb3558c05e7"; logging-data="10270"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19I/ngEd4eFIrhS3wsV9/5vTn1w7TGEL8E="
Cancel-Lock sha1:8m2LSLtUv6kIsQ2iOAQjeDjqj0M= sha1:AER34vRV3j+xa72wBqUJalk0/wU=
X-BSB-Auth 1.86430dc4422c5c38acb9.20210426142651BST.87lf95gorp.fsf@bsb.me.uk
Xref csiph.com comp.theory:32191

Show key headers only | View raw


Richard Damon <Richard@Damon-Family.org> writes:

> On 4/25/21 11:34 PM, 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?

Sorry, I missed the word "byte".  No that is not Kosher.  TM's don't
have bytes.  I thought you meant 256-ary using 256 symbols which can be
numbers.  Talking about bytes is just weird in this context!

>> The symbols on the tape being finite remind me of mapping an alphabet to
>> roots of complex numbers:
>> 
>> https://groups.google.com/g/comp.lang.c++/c/bB1wA4wvoFc/m/OTccTiXLAgAJ
>> 
>> each symbol is unique. This is making me think of trying to implement a
>> L-system in a TM.
>> 
>> https://en.wikipedia.org/wiki/L-system
>> 
>> ;^)
>
> Yes, the tape could store the number in any base. Since we need the
> separator character, you may want to use base 255 instead of 256 so 0xFF
> can be that separator and still keep to a single byte.

You alerted me to the word byte, so thanks, but surely the right answer
is that bytes have nothing to do with it?  You can use 256 symbols and
still have another one for a separator.

And as I said in another reply, using the tape's blank symbol for a
separator is not usually a good idea, so if you wanted to limit the
symbols set to 256 (though I can't see why) you'd be better off with 253
digits, a separator and the tape's blank symbol.

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