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


Groups > comp.theory > #32175

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 01:58 +0100
Organization A noiseless patient Spider
Message-ID <878s55j1yx.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> <87k0oqhtmi.fsf@bsb.me.uk> <_lnhI.128762$ST2.106788@fx47.iad>

Show all headers | View raw


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

> On 4/25/21 6:44 PM, Ben Bacarisse wrote:
>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>> 
>>> 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.
>> 
>> You are missing the fact that the number of symbols -- distinct things
>> that can be stored in any one cell -- must be finite:
>> 
>>>> This is because the 'alphabet' of a Turing Machine Tape is Finite.
>> 
>> The symbols could be natural numbers, but there must be only a finite
>> number of them.
>> 
>> You can represent the natural numbers using digits:
>> 
>>  [1][,][2][,][3][,][4][,] ... [9][,][1][0][,][1][1][,][1][2][,][1][3] ...
>> 
>> but then another conventional restriction kicks in.  Initially, the tape
>> (or tapes in a multi-tape TM) must contain only a finite number of
>> non-blank symbol, so having all the natural numbers, even if encoded using
>> a finite alphabet, would be considered an extension to the usual
>> definition.
>> 
>> But extending and restricting the definition is part of the fun.  Define
>> your own model where the alphabet -- the distinct symbols that can
>> appear in any cell is, in fact, infinite.  What can you do with that?
>> Can you do anything with that without extending the definition to allow
>> infinite state transition tuples?  How would you specify these?
>> 
>> What about allowing uncountable infinite alphabets?  And what happens if
>> you permit the initial tape or tapes to have an infinite number of
>> non-blank symbols?  How do you specify your random initial data, and
>> what can the TM do with it?
>> 
>> But if you want a classical TM, you have to go with the usual
>> definition, though I find the usual presentation very fussy.  For
>> example, there must be a finite number states but they only need to be
>> distinct so they are often given meaningless labels like q0, q1, q2...
>> I think you might as well just say that the states /are/ natural
>> numbers.  Also, you don't really need final states nor accepting and
>> rejecting states.  The end result is you can have a TM defined as pretty
>> much nothing but a state transition function.
>> 
>> Wolfram goes this route and adds a very compact graphical notation that
>> makes enumerating TMs (something that is often done in the theory)
>> simpler.
>> 
>> I'll just add how nice it is to actually talk about comp.theory without
>> feeling as if one is standing in front of a fire-hose of errors and
>> misconceptions.
>> 
>
> Yes, the norm of a finite tape is a bit of an issue, but you could make
> the system use a UTM that WRITE this length tape counting the steps
> (perhaps for that we want the number stored little endian so it
> naturally extends to positive tape direction).

Not sure why you say UTM.  You may be jumping ahead a few steps!

I think its safe to say that any infinite tape that can be incrementally
written by a TM could be provided as an extra without altering the power
of the model.  The proof of this general claim would probably use a UTM
expanding a finite input interleaved with the execution of the main
machine.

Of course, oracle machines, (a least the interesting ones) have extra
tapes whose content can't be written by any TM.

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