Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Subject | Re: Is this a legit TM? |
|---|---|
| Newsgroups | comp.theory |
| 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> |
| From | Richard Damon <Richard@Damon-Family.org> |
| Message-ID | <_lnhI.128762$ST2.106788@fx47.iad> (permalink) |
| Organization | Forte - www.forteinc.com |
| Date | 2021-04-25 19:57 -0400 |
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).
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