Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #32135 > unrolled thread
| Started by | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| First post | 2021-04-24 23:46 -0700 |
| Last post | 2021-04-26 07:19 -0700 |
| Articles | 16 — 4 participants |
Back to article view | Back to comp.theory
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
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2021-04-24 23:46 -0700 |
| Subject | Is this a legit TM? |
| Message-ID | <s63382$1vqu$1@gioia.aioe.org> |
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 t2 is the main driver of this "TM". So, the "TM" starts reading and processing t2. For each move of the head, it moves the head one position to the right for both t0 and t1. So, if t2 halts, the current position of t0 will tell exactly how many moves the head made for processing t2, and t1 will show the random bit at halting. So, lets say t2 was a simple program that simply said move 2 positions to the right. So, initial setup: t0[0] = 0 t1[0] = say, 0, being random, flip a coin t3[0] = move 2 to the right Lets move two position to the right, one at a time: t0[1] = 1 t1[1] = flip coin, 0 t2[1] = in progress t0[2] = 2 t1[2] = flip coin, 1 t2[2] = halt t0[2] = 2 means it took two steps, and t1[2] = 1 is the current random bit, t2[2] = halt means we are finished. Has somebody created a physical TM that reads tapes with QR codes on them? lol. ;^)
[toc] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-04-25 07:43 -0400 |
| Message-ID | <CBchI.151620$N_4.88620@fx36.iad> |
| In reply to | #32135 |
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. This is because the 'alphabet' of a Turing Machine Tape is Finite. Also, while you define t1 as being set be a TRNG, by theory it is now an input and fixed for a given computation, so to repeat that computation you give it the exact same TRNG sequence, so it is no longer really 'random'. > t2 is the main driver of this "TM". > > So, the "TM" starts reading and processing t2. For each move of the > head, it moves the head one position to the right for both t0 and t1. > So, if t2 halts, the current position of t0 will tell exactly how many > moves the head made for processing t2, and t1 will show the random bit > at halting. So, lets say t2 was a simple program that simply said move 2 > positions to the right. > > So, initial setup: > > t0[0] = 0 > t1[0] = say, 0, being random, flip a coin > t3[0] = move 2 to the right > > Lets move two position to the right, one at a time: > > t0[1] = 1 > t1[1] = flip coin, 0 > t2[1] = in progress > > t0[2] = 2 > t1[2] = flip coin, 1 > t2[2] = halt > > > t0[2] = 2 means it took two steps, and t1[2] = 1 is the current random > bit, t2[2] = halt means we are finished. > > Has somebody created a physical TM that reads tapes with QR codes on > them? lol. ;^) > > >
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2021-04-25 14:55 -0700 |
| Message-ID | <s64oh1$1vbf$1@gioia.aioe.org> |
| In reply to | #32139 |
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. > > This is because the 'alphabet' of a Turing Machine Tape is Finite. > > Also, while you define t1 as being set be a TRNG, by theory it is now an > input and fixed for a given computation, so to repeat that computation > you give it the exact same TRNG sequence, so it is no longer really > 'random'. > >> t2 is the main driver of this "TM". >> >> So, the "TM" starts reading and processing t2. For each move of the >> head, it moves the head one position to the right for both t0 and t1. >> So, if t2 halts, the current position of t0 will tell exactly how many >> moves the head made for processing t2, and t1 will show the random bit >> at halting. So, lets say t2 was a simple program that simply said move 2 >> positions to the right. >> >> So, initial setup: >> >> t0[0] = 0 >> t1[0] = say, 0, being random, flip a coin >> t3[0] = move 2 to the right >> >> Lets move two position to the right, one at a time: >> >> t0[1] = 1 >> t1[1] = flip coin, 0 >> t2[1] = in progress >> >> t0[2] = 2 >> t1[2] = flip coin, 1 >> t2[2] = halt >> >> >> t0[2] = 2 means it took two steps, and t1[2] = 1 is the current random >> bit, t2[2] = halt means we are finished. >> >> Has somebody created a physical TM that reads tapes with QR codes on >> them? lol. ;^) >> >> >> >
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-04-25 23:44 +0100 |
| Message-ID | <87k0oqhtmi.fsf@bsb.me.uk> |
| In reply to | #32164 |
"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.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-04-25 19:57 -0400 |
| Message-ID | <_lnhI.128762$ST2.106788@fx47.iad> |
| In reply to | #32165 |
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).
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-04-26 01:58 +0100 |
| Message-ID | <878s55j1yx.fsf@bsb.me.uk> |
| In reply to | #32172 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-04-25 22:11 -0400 |
| Message-ID | <ejphI.138836$2A5.106782@fx45.iad> |
| In reply to | #32175 |
On 4/25/21 8:58 PM, Ben Bacarisse wrote: > 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. > Jumping to a UTM as having a TM do this sort of update on a tape as a 'single step' operation (like move the tape forward) is probably a bit much. Even move to next ',' is more than a traditional Turing Machine could do, but is a simple enough Turing Subroutine I wouldn't object to an extension to a Turing machine to define the Tape Operation to be a move in a given direction until the next symbol X.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-04-25 19:55 -0400 |
| Message-ID | <tjnhI.128761$ST2.90519@fx47.iad> |
| In reply to | #32164 |
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, > > >> >> This is because the 'alphabet' of a Turing Machine Tape is Finite. >> >> Also, while you define t1 as being set be a TRNG, by theory it is now an >> input and fixed for a given computation, so to repeat that computation >> you give it the exact same TRNG sequence, so it is no longer really >> 'random'. >> >>> t2 is the main driver of this "TM". >>> >>> So, the "TM" starts reading and processing t2. For each move of the >>> head, it moves the head one position to the right for both t0 and t1. >>> So, if t2 halts, the current position of t0 will tell exactly how many >>> moves the head made for processing t2, and t1 will show the random bit >>> at halting. So, lets say t2 was a simple program that simply said move 2 >>> positions to the right. >>> >>> So, initial setup: >>> >>> t0[0] = 0 >>> t1[0] = say, 0, being random, flip a coin >>> t3[0] = move 2 to the right >>> >>> Lets move two position to the right, one at a time: >>> >>> t0[1] = 1 >>> t1[1] = flip coin, 0 >>> t2[1] = in progress >>> >>> t0[2] = 2 >>> t1[2] = flip coin, 1 >>> t2[2] = halt >>> >>> >>> t0[2] = 2 means it took two steps, and t1[2] = 1 is the current random >>> bit, t2[2] = halt means we are finished. >>> >>> Has somebody created a physical TM that reads tapes with QR codes on >>> them? lol. ;^) >>> >>> >>> >> >
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2021-04-25 20:34 -0700 |
| Message-ID | <s65ccn$81f$1@gioia.aioe.org> |
| In reply to | #32171 |
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? 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 ;^)
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2021-04-26 01:35 -0700 |
| Message-ID | <181a8021-71f7-498c-80ac-78b1edf9844bn@googlegroups.com> |
| In reply to | #32178 |
On Monday, 26 April 2021 at 04:34:50 UTC+1, 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? > The symbols on the tape being finite remind me of mapping an alphabet to > roots of complex numbers: > You'll find it easier to work with binary. Leading 1 is always present, and the tape looks like this 1<>10<>11<>100<>101<>110<>111<>1000 ... I'm not sure how to write a function which takes a tape position index and calulates the digit. It must be possible. Then you can implement an infinite tape of natural numbers.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-04-26 11:13 +0100 |
| Message-ID | <8735vdicaq.fsf@bsb.me.uk> |
| In reply to | #32181 |
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > On Monday, 26 April 2021 at 04:34:50 UTC+1, 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? Yes, any finite set will do. > You'll find it easier to work with binary. Is that because there are fewer symbols to deal with? Very often, it's even easier to deal with unary -- tally-stick -- numbers. But I don't think any actual advice can be given until we know what CMT is planning to do with this tape of numbers. That's what will determine the best way to represent it. > Leading 1 is always present, ... Why? (The answer may come down to the answer to the next one.) > ... and the tape looks like this > 1<>10<>11<>100<>101<>110<>111<>1000 ... Is <> your way to write a blank? TMs are hardly "practical" but when playing with them to learn, it's almost always best to try to arrange the tapes to have the pattern ... _ _ _ _ X X X X X X _ _ _ .... i.e. to have just one contiguous sequence of non-blank symbols. > I'm not sure how to write a function which takes a tape position index and > calulates the digit. It must be possible. Then you can implement an infinite > tape of natural numbers. I think you've moved for what such an extra tape looks like to how to make the extra tape "virtual", yes? Otherwise, I can't see why you'd want an index to digit TM. Unary makes that much easier, though it's a mark of how everything is so fiddly with a TM that it's not trivial even then. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2021-04-26 03:35 -0700 |
| Message-ID | <646402de-a45b-435c-ab27-9573d91b705cn@googlegroups.com> |
| In reply to | #32182 |
On Monday, 26 April 2021 at 11:13:20 UTC+1, Ben Bacarisse wrote: > Malcolm McLean <malcolm.ar...@gmail.com> writes: > > > On Monday, 26 April 2021 at 04:34:50 UTC+1, 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? > Yes, any finite set will do. > > You'll find it easier to work with binary. > Is that because there are fewer symbols to deal with? Very often, it's > even easier to deal with unary -- tally-stick -- numbers. > > But I don't think any actual advice can be given until we know what CMT > is planning to do with this tape of numbers. That's what will determine > the best way to represent it. > > > Leading 1 is always present, ... > > Why? (The answer may come down to the answer to the next one.) > > > ... and the tape looks like this > > 1<>10<>11<>100<>101<>110<>111<>1000 ... > Is <> your way to write a blank? > Yes. > TMs are hardly "practical" but when playing with them to learn, it's > almost always best to try to arrange the tapes to have the pattern > > ... _ _ _ _ X X X X X X _ _ _ .... > > i.e. to have just one contiguous sequence of non-blank symbols. > > I'm not sure how to write a function which takes a tape position index and > > calulates the digit. It must be possible. Then you can implement an infinite > > tape of natural numbers. > I think you've moved for what such an extra tape looks like to how to > make the extra tape "virtual", yes? Otherwise, I can't see why you'd > want an index to digit TM. > Yes, the idea is that you have a function which takes an unbounded string representing a tape index, and returns the digit at that index, so you can make the "natural numbers" tape virtual instead of trying to manufacture it. > > Unary makes that much easier, though it's a mark of how everything is so > fiddly with a TM that it's not trivial even then. > Chris didn't say exactly what he wants the number list for, though it seems to be for some fractal calculation. However almost certainly going higher than binary is achieving nothing beyond saving tape (with the exception of the special case of denary, because that's human-readable). I don't know about unary, since the tape is infinite, maybe even binary doesn't have an real advantage.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-04-26 07:00 -0400 |
| Message-ID | <p3xhI.116120$Qf2.1317@fx38.iad> |
| In reply to | #32178 |
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? > 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.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-04-26 14:26 +0100 |
| Message-ID | <87lf95gorp.fsf@bsb.me.uk> |
| In reply to | #32187 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-04-26 09:35 -0400 |
| Message-ID | <tkzhI.24861$N%1.14677@fx28.iad> |
| In reply to | #32191 |
On 4/26/21 9:26 AM, Ben Bacarisse wrote: > 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. > If you are thinking about how to actually write a program that implements a computation using a Turing Machine Computation Model, it can make sense. After all, if you are going to actually try to run the Turing Machine, you need a way to get a real computer process it. Defining the tape as a sequence of bytes isn't a bad model (if your symbol set fits). You just need something in the program to handle the difference between the fixed finite allocation that to computer will have to some 'infinite' equivalent for the Turing Machine (maybe a file is good enough, maybe you need a sequence of files on memory sticks that it can ask for the next or previous stick as needed)
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2021-04-26 07:19 -0700 |
| Message-ID | <fd89ca42-e5fc-4742-bd55-798660a83c61n@googlegroups.com> |
| In reply to | #32192 |
On Monday, 26 April 2021 at 14:35:25 UTC+1, Richard Damon wrote: > On 4/26/21 9:26 AM, Ben Bacarisse wrote: > > Richard Damon <Ric...@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. > > > If you are thinking about how to actually write a program that > implements a computation using a Turing Machine Computation Model, it > can make sense. > > After all, if you are going to actually try to run the Turing Machine, > you need a way to get a real computer process it. Defining the tape as a > sequence of bytes isn't a bad model (if your symbol set fits). You just > need something in the program to handle the difference between the fixed > finite allocation that to computer will have to some 'infinite' > equivalent for the Turing Machine (maybe a file is good enough, maybe > you need a sequence of files on memory sticks that it can ask for the > next or previous stick as needed) > A memory area of a few kilobytes will surely be enough. The idea is to create a proof of concept, with the knowledge that we could scale up to very large problems using the same machine if required.
[toc] | [prev] | [standalone]
Back to top | Article view | comp.theory
csiph-web