Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| 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> |
"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
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