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