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


Groups > comp.theory > #32165

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-25 23:44 +0100
Organization A noiseless patient Spider
Message-ID <87k0oqhtmi.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>

Show all headers | View raw


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

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