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


Groups > comp.theory > #32135 > unrolled thread

Is this a legit TM?

Started by"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
First post2021-04-24 23:46 -0700
Last post2021-04-26 07:19 -0700
Articles 16 — 4 participants

Back to article view | Back to comp.theory


Contents

  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

#32135 — Is this a legit TM?

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-04-24 23:46 -0700
SubjectIs 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]


#32139

FromRichard Damon <Richard@Damon-Family.org>
Date2021-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]


#32164

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-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]


#32165

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-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]


#32172

FromRichard Damon <Richard@Damon-Family.org>
Date2021-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]


#32175

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-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]


#32176

FromRichard Damon <Richard@Damon-Family.org>
Date2021-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]


#32171

FromRichard Damon <Richard@Damon-Family.org>
Date2021-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]


#32178

From"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Date2021-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]


#32181

FromMalcolm McLean <malcolm.arthur.mclean@gmail.com>
Date2021-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]


#32182

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-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]


#32183

FromMalcolm McLean <malcolm.arthur.mclean@gmail.com>
Date2021-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]


#32187

FromRichard Damon <Richard@Damon-Family.org>
Date2021-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]


#32191

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-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]


#32192

FromRichard Damon <Richard@Damon-Family.org>
Date2021-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]


#32196

FromMalcolm McLean <malcolm.arthur.mclean@gmail.com>
Date2021-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