Validating that the implementation meets the spec for TM transition function

[olcott]

A turing machine is a model of a computer. It has a finite number of
states, and it is capable of reading and modifying a tape. A turing
machine program consists of a list of 'quintuples', each one of which is
a five-symbol turing machine instruction. For example, the quintuple
'SCcsm' is executed by the machine if it is in state 'S' and is reading
the symbol 'C' on the tape. In that case, the instruction causes the
machine to make a transition to state 's' and to overwrite the symbol
'C' on the tape with the symbol 'c'. The last operation it performs
under this instruction is to move the tape reading head one symbol to
the left or right according to whether 'm' is 'l' or 'r'.
http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt

For example, the quintuple 'SCcsm' is executed by the machine:

If it is in state 'S' and is reading the symbol 'C' on the tape then
(a) make a transition to state 's'.
(b) overwrite the symbol 'C' on the tape with the symbol 'c'.
// Must do this before transition to state 's' or we lose 'c' from S.
(c) move the tape reading head one symbol to the left or right
according to whether 'm' is 'l' or 'r'.

struct Quintuple
{
u32 state;
u32 symbol;
u32 write_symbol;
u32 next_state;
u8 Tape_Head_Move;
};

class Quintuple_List
{
std::set<Quintuple> list;
NextState(int next_state, int current_input)
{
Quintuple QT(next_state, current_input);
return list.find(QT);
};
}

bool transition_function(std::set<Quintuple>::iterator& current_quintuple)
{
u32 next_state = current_quintuple->next_state;
u32 current_input = Tape[Tape_Head];
std::set<Quintuple>::iterator next_quintuple;

Tape[Tape_Head] = current_quintuple->write_symbol;
if (toupper(current_quintuple->tape_head_move) == “L”;
Tape_Head--; // Left
else
Tape_Head++; // Right

next_quintuple = NextState(next_state, current_input);
if ( next_quintuple == Quintuple_List.end())
return false;
current_quintuple = next_quintuple;
return true;
}


--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

[Mr Flibble]

If you are going to use C++ for this then at least create proper
abstractions rather than a struct containing anonymous types. At the
very least created named typedefs for things rather than the anonymous
'u32' etc.

/Flibble

[olcott]

It is not a struct containing anonymous types they are fixed width
unsigned integers. I could have just used int and unsigned char, I will
change it.

> very least created named typedefs for things rather than the anonymous
> 'u32' etc.
>
> /Flibble
>
>

It is all in a pair of C++ classes, I didn't want to show all of the
pages, (1) They are not done yet (2) The distract attention way from the
only function that I need reviewed.

[Mr Flibble]

On Fri, 6 May 2022 16:25:58 -0500

It is obvious that they are fixed width unsigned integers but that
doesn't tell us anything about what they actually are apart from being
represented as integers, 'state_t' is more meaningful than 'u32':

using state_t = std::uint32_t;

/Flibble

[Malcolm McLean]

ThIs looks along the right lines.
The quintuples need to be indexed by the current state and the current input,
and a set, properly specified, will achieve this.
You can probably get away with chars for the symbols. Few people work with Turing
machines with a large number of symbols.
Since the tape cannot in reality be infinite, you might consider throwing an exception
when it goes out of bounds.
I'd rename "Quintuple_List", "TuringMachine". Of course in your system, a Turing
machine is a quintuple list, so it's moot which name is better. But if you make the
list private, you can shift to another representation whilst keeping the interfaces the
same.

[olcott]

Ben didn't seem to understand this.

> You can probably get away with chars for the symbols. Few people work with Turing
> machines with a large number of symbols.

My initial vision was to use unsigned 8-bit integers and let the data be
quintuples be defined by ASCII chars, as it is in my model system.
All this cane be defined on the parse side, leaving int as the
underlying size.

> Since the tape cannot in reality be infinite, you might consider throwing an exception
> when it goes out of bounds.

Or put it in a std::vector and grow it as needed.
I think that the conventional TM has a tape with a beginning, thus a
tape_head move to before the beginning would be an error.

> I'd rename "Quintuple_List", "TuringMachine". Of course in your system, a Turing
> machine is a quintuple list, so it's moot which name is better. But if you make the
> list private, you can shift to another representation whilst keeping the interfaces the
> same.
>

I thought that States was a fine name.

[olcott]

We really only need to know that they are integers, the rest of the code
explains how everything fits together. I want to make my TM interpreter
as simple as possible.

The purpose of this thread is to simply confirm that the implementation
of meets the specs:

THESE ARE THE SPECS:

For example, the quintuple 'SCcsm' is executed by the machine:

If it is in state 'S' and is reading the symbol 'C' on the tape then
(a) make a transition to state 's'.
(b) overwrite the symbol 'C' on the tape with the symbol 'c'.
// Must do this before transition to state 's' or we lose 'c' from S.
(c) move the tape reading head one symbol to the left or right
according to whether 'm' is 'l' or 'r'.

THIS IS THE IMPLEMENTATION:
struct Quintuple
{
int state;
int symbol;
int write_symbol;
int next_state;
unsigned char Tape_Head_Move;

};

class Quintuple_List
{
std::set<Quintuple> list;
NextState(int next_state, int current_input)
{
Quintuple QT(next_state, current_input);
return list.find(QT);
};
}

bool transition_function(std::set<Quintuple>::iterator& current_quintuple)
{
u32 next_state = current_quintuple->next_state;
u32 current_input = Tape[Tape_Head];
std::set<Quintuple>::iterator next_quintuple;

Tape[Tape_Head] = current_quintuple->write_symbol;
if (toupper(current_quintuple->tape_head_move) == “L”;
Tape_Head--; // Left
else
Tape_Head++; // Right

next_quintuple = NextState(next_state, current_input);
if ( next_quintuple == Quintuple_List.end())
return false;
current_quintuple = next_quintuple;
return true;
}

[Malcolm McLean]

If you use chars for the symbols, you can make the tape human-readable. Which
might help.
But as you say, you can manipulate the symbols internally as 32 bit integers if
you want, even if in reality they are constrained to take the values "1", "0" and
"blank".

[olcott]

They are constrained to any value that unsigned int can hold.
The parse side will initially only be 7-bit ASCII to make it compatible
with the TM interpreter 7-bit TM code examples. The other {8,16,32} bit
parses will be all be in hexadecimal. (I may skip 8, and 16 bits).

[Mike Terry]

Well you must be confused by what a TM state is - the quintuples do not represent the TM states as
lots of people have said.

Look, check your favourite Linz book, figure 9.7 (in my edition; the figure for Example 9.10 "Design
a TM that copiess strings of 1's"). You see there are several CIRCLES joined by annotated ARROWS?

The TM states are THE LITTLE CIRCLES, with their state names q0, q1... written inside.

Your quintuples are the equivalent of THE *ARROWS* in the figure. So, not states at all. Someone
suggested "rules", which is what I might have chosen.

Your E TM will probably end up with around 5 circles and 6 arrows (if you go with your binary number
tape representation) so if you need an emulator to debug your E and check you've got it right that
doesn't say much for your problem solving skills! :)

Mike.

[olcott]

AKA directed graphs the abstract away key details of the actions
required by a state transitions. We can ignore these actions when we are
presenting a high level overview in directed graphs. The actual state
transitions require these actions and can't possibly work correctly
without them.

> Your quintuples are the equivalent of THE *ARROWS* in the figure.  So,
> not states at all.  Someone suggested "rules", which is what I might
> have chosen.
>

OK that makes perfect sense.

> Your E TM will probably end up with around 5 circles and 6 arrows (if
> you go with your binary number tape representation) so if you need an
> emulator to debug your E and check you've got it right that doesn't say
> much for your problem solving skills!  :)
>
> Mike.

So you didn't find any errors in my transition_function?
I got all the code to compile now. I can adapt the TM interpreter
examples: http://www.lns.mit.edu/~dsw/turing/examples/examples.html

[Ben]

Malcolm McLean <malcolm.ar...@gmail.com> writes:

> ThIs looks along the right lines.
> The quintuples need to be indexed by the current state and the current
> input, and a set, properly specified, will achieve this.

How? std::set is not the right container for this.

> You can probably get away with chars for the symbols. Few people work
> with Turing machines with a large number of symbols.

ACK. It's painful to write TMs with more than even a handful of
distinct symbols. There may be some value in using something like
wchar_t so that fancy symbols matching those seen in some of the papers
can be used, but that's a bit of a stretch.

--
Ben.

[olcott]

On 5/6/2022 7:22 PM, Ben wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>
>> ThIs looks along the right lines.
>> The quintuples need to be indexed by the current state and the current
>> input, and a set, properly specified, will achieve this.
>
> How? std::set is not the right container for this.

std::set::find()

std::set<Quintuple> States;
std::vector<unsigned char> Tape;
void insert(const Quintuple& QT){ States.insert(QT); };

std::set<Quintuple>::iterator
NextState(int current_input, int next_state)
{
Quintuple QT(current_input, next_state);
return States.find(QT);

}

>
>> You can probably get away with chars for the symbols. Few people work
>> with Turing machines with a large number of symbols.
>

The TM interpreter uses ASCII text as its tape elements.
For compatibility I will do the same, that way I can directly execute
all of his same filename.tm examples.

> ACK. It's painful to write TMs with more than even a handful of
> distinct symbols. There may be some value in using something like
> wchar_t so that fancy symbols matching those seen in some of the papers
> can be used, but that's a bit of a stretch.
>

One need to use more than one or two {'0', '1'} of the possible tape
elements.

[Ben]

olcott <polc...@gmail.com> writes:

> On 5/6/2022 4:41 PM, Malcolm McLean wrote:

>>>> olcott <polc...@gmail.com> wrote:

>>>>> struct Quintuple
>>>>> {
>>>>> u32 state;
>>>>> u32 symbol;
>>>>> u32 write_symbol;
>>>>> u32 next_state;
>>>>> u8 Tape_Head_Move;
>>>>> };
>>>>>
>>>>> class Quintuple_List
>>>>> {
>>>>> std::set<Quintuple> list;
>>>>> NextState(int next_state, int current_input)
>>>>> {
>>>>> Quintuple QT(next_state, current_input);
>>>>> return list.find(QT);
>>>>> };
>>>>> }

>> ThIs looks along the right lines.
>> The quintuples need to be indexed by the current state and the current input,
>> and a set, properly specified, will achieve this.
>
> Ben didn't seem to understand this.

Your code sketch just won't work as you have it now. Do you know how to
get it to work? The result will not be a natural use of a set.

--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

[Ben]

olcott <polc...@gmail.com> writes:

> On 5/6/2022 7:22 PM, Ben wrote:
>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>
>>> ThIs looks along the right lines.
>>> The quintuples need to be indexed by the current state and the current
>>> input, and a set, properly specified, will achieve this.
>> How? std::set is not the right container for this.
>
> std::set::find()
>
> std::set<Quintuple> States;
> std::vector<unsigned char> Tape;
> void insert(const Quintuple& QT){ States.insert(QT); };
>
> std::set<Quintuple>::iterator
> NextState(int current_input, int next_state)
> {
> Quintuple QT(current_input, next_state);
> return States.find(QT);
> }

No, this won't work. You can /make/ it work, but to do that you have to
play tricks with what's considered to be unique in the set. I think a
std::map is more natural.

And your names appear messed up again. NextState (with no declared
return type) returns a Quintuple, not a state. And it has "next_state"
as an argument which seems unlikely. Surely NextState needs the current
state and input symbol?

[Ben]

Ben <ben.u...@bsb.me.uk> writes:

> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>
>> ThIs looks along the right lines.
>> The quintuples need to be indexed by the current state and the current
>> input, and a set, properly specified, will achieve this.
>
> How? std::set is not the right container for this.

I can answer the how myself now, but I still don't think std::set is the
right choice as the reader is likely yo be confused by the look-up.

--
Ben.

[olcott]

On 5/6/2022 7:54 PM, Ben wrote:
> olcott <polc...@gmail.com> writes:
>
>> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
>
>>>>> olcott <polc...@gmail.com> wrote:
>
>>>>>> struct Quintuple
>>>>>> {
>>>>>> u32 state;
>>>>>> u32 symbol;
>>>>>> u32 write_symbol;
>>>>>> u32 next_state;
>>>>>> u8 Tape_Head_Move;
>>>>>> };
>>>>>>
>>>>>> class Quintuple_List
>>>>>> {
>>>>>> std::set<Quintuple> list;
>>>>>> NextState(int next_state, int current_input)
>>>>>> {
>>>>>> Quintuple QT(next_state, current_input);
>>>>>> return list.find(QT);
>>>>>> };
>>>>>> }
>
>>> ThIs looks along the right lines.
>>> The quintuples need to be indexed by the current state and the current input,
>>> and a set, properly specified, will achieve this.
>>
>> Ben didn't seem to understand this.
>
> Your code sketch just won't work as you have it now.

Not when you erase the most important part:

bool Quintuple_List::transition_function(std::set<Quintuple>::iterator&
current_quintuple)
{
unsigned int next_state = current_quintuple->next_state;
unsigned int current_input = Tape[Tape_Head];

std::set<Quintuple>::iterator next_quintuple;

Tape[Tape_Head] = current_quintuple->write_symbol;

if (toupper(current_quintuple->tape_head_move) == 'L')

Tape_Head--; // Left
else
Tape_Head++; // Right

next_quintuple = NextState(next_state, current_input);

if (next_quintuple == States.end())

return false;
current_quintuple = next_quintuple;
return true;
}

If you also assume that I got All the missing pieces correctly then it
should work just fine.

> Do you know how to
> get it to work? The result will not be a natural use of a set.
>

The natural use of a std::set it to look things up very quickly with no
need for a linear search.

I decided to make my system exactly compatible with these code samples:
http://www.lns.mit.edu/~dsw/turing/examples/examples.html

[olcott]

On 5/6/2022 8:01 PM, Ben wrote:
> olcott <polc...@gmail.com> writes:
>
>> On 5/6/2022 7:22 PM, Ben wrote:
>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>
>>>> ThIs looks along the right lines.
>>>> The quintuples need to be indexed by the current state and the current
>>>> input, and a set, properly specified, will achieve this.
>>> How? std::set is not the right container for this.
>>
>> std::set::find()
>>
>> std::set<Quintuple> States;
>> std::vector<unsigned char> Tape;
>> void insert(const Quintuple& QT){ States.insert(QT); };
>>
>> std::set<Quintuple>::iterator
>> NextState(int current_input, int next_state)
>> {
>> Quintuple QT(current_input, next_state);
>> return States.find(QT);
>> }
>
> No, this won't work. You can /make/ it work, but to do that you have to
> play tricks with what's considered to be unique in the set. I think a
> std::map is more natural.
>

I got dem tricks...
std::map has redundant data or splits the class data into two pieces.

> And your names appear messed up again. NextState (with no declared

It has a declared return type that doesn't fit well on the same line:
std::set<Quintuple>::iterator

> return type) returns a Quintuple, not a state. And it has "next_state"
> as an argument which seems unlikely. Surely NextState needs the current
> state and input symbol?
>

You missed this?
>> NextState(int current_input, int next_state)

[olcott]

I have done this for may years with std::map. std::set is the same yet
one must overload: bool Quintuple::operator<(const Quintuple& QT) const

[Mikko]

On 2022-05-06 20:53:58 +0000, olcott said:

> For example, the quintuple 'SCcsm' is executed by the machine:
>
> If it is in state 'S' and is reading the symbol 'C' on the tape then
> (a) make a transition to state 's'.
> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
> // Must do this before transition to state 's' or we lose 'c' from S.
> (c) move the tape reading head one symbol to the left or right
> according to whether 'm' is 'l' or 'r'.

The new state is irrelevant until (b) and (c) are performed, so
the action (a) should be last in the list.

> struct Quintuple
> {
> u32 state;
> u32 symbol;
> u32 write_symbol;
> u32 next_state;
> u8 Tape_Head_Move;
> };

If you want to print traces of the execution it is better to
give the type char* to state and next_state. As the only operations
with these values are assignment and equality test, char* is
as good as u32. But char* gives better trace if it points to the
name of the state as it is in the definition of the Turing machine.

Although not relevant to the current question, I still recommend
that Quintuple be renamed to Rule and Quintuple_List be renamed
to Rules.

> class Quintuple_List
> {
> std::set<Quintuple> list;
> NextState(int next_state, int current_input)

This function should be named getRule. Function names shoule start with
a lower case letter.

> {
> Quintuple QT(next_state, current_input);
> return list.find(QT);
> };
> }
>
> bool transition_function(std::set<Quintuple>::iterator& current_quintuple)
> {
> u32 next_state = current_quintuple->next_state;
> u32 current_input = Tape[Tape_Head];
> std::set<Quintuple>::iterator next_quintuple;
>
> Tape[Tape_Head] = current_quintuple->write_symbol;
> if (toupper(current_quintuple->tape_head_move) == “L”;

Instead of using toupper here you should ensure that only upper case
letters 'L' and 'R' are ever stored in any tape_head_move.

> Tape_Head--; // Left
> else
> Tape_Head++; // Right
>
> next_quintuple = NextState(next_state, current_input);
> if ( next_quintuple == Quintuple_List.end())
> return false;
> current_quintuple = next_quintuple;
> return true;
> }

Mikko

[Malcolm McLean]

A map or an unordered_map would be easier, I agree. But PO has chosen
a set, and that can be made to work.

[Mr Flibble]

On Fri, 6 May 2022 17:08:40 -0500

Using 'int' directly just makes matters worse as far as writing code
which is easy to understand is concerned. Create named typedefs whose
names describe what the type actually is.

using state_t = std::uint32_t.

Also if there are a finite number of states then consider using an
enum.

/Flibble

[olcott]

On 5/7/2022 3:06 AM, Mikko wrote:
> On 2022-05-06 20:53:58 +0000, olcott said:
>
>> For example, the quintuple 'SCcsm' is executed by the machine:
>>
>> If it is in state 'S' and is reading the symbol 'C' on the tape then
>> (a) make a transition to state 's'.
>> (b) overwrite the symbol 'C' on the tape with the symbol 'c'.
>>       // Must do this before transition to state 's' or we lose 'c'
>> from S.
>> (c) move the tape reading head one symbol to the left or right
>>       according to whether 'm' is 'l' or 'r'.
>
> The new state is irrelevant until (b) and (c) are performed, so
> the action (a) should be last in the list.
>

That is how I implemented it.

>> struct Quintuple
>> {
>>    u32 state;
>>    u32 symbol;
>>    u32 write_symbol;
>>    u32 next_state;
>>     u8 Tape_Head_Move;
>> };
>
> If you want to print traces of the execution it is better to
> give the type char* to state and next_state. As the only operations
> with these values are assignment and equality test, char* is
> as good as u32. But char* gives better trace if it points to the
> name of the state as it is in the definition of the Turing machine.
>

It also forces far fewer states.

> Although not relevant to the current question, I still recommend
> that Quintuple be renamed to Rule and Quintuple_List be renamed
> to Rules.
>

I want to either use the standard that David S. Woodruff use
http://www.lns.mit.edu/~dsw/turing/turing.html
Or find some common convention of computer science.

I am still thinking that State and States are good names and the opinion
that they are not good names is incorrect. A state must have all of its
transition information in itself.

>> class Quintuple_List
>> {
>>    std::set<Quintuple> list;
>>    NextState(int next_state, int current_input)
>
> This function should be named getRule. Function names shoule start with
> a lower case letter.
>

That would be inconsistent with the spec:

make a transition to state 's'.

>>    {
>>      Quintuple QT(next_state, current_input);
>>      return list.find(QT);
>>    };
>> }
>>
>> bool transition_function(std::set<Quintuple>::iterator&
>> current_quintuple)
>> {
>>    u32 next_state    = current_quintuple->next_state;
>>    u32 current_input = Tape[Tape_Head];
>>    std::set<Quintuple>::iterator next_quintuple;
>>
>>    Tape[Tape_Head]   = current_quintuple->write_symbol;
>>    if (toupper(current_quintuple->tape_head_move) == “L”;
>
> Instead of using toupper here you should ensure that only upper case
> letters 'L' and 'R' are ever stored in any tape_head_move.
>

I disagree.

>>      Tape_Head--;  // Left
>>    else
>>      Tape_Head++;  // Right
>>
>>    next_quintuple = NextState(next_state, current_input);
>>    if ( next_quintuple == Quintuple_List.end())
>>      return false;
>>    current_quintuple = next_quintuple;
>>    return true;
>> }
>
> Mikko
>
>

[Ben]

As written, it can't, for reasons I've pointed out before (summary:
assigned to local, uses the wrong symbol to pick the next rule).

But it still also uses bad names. It's a big help that you've fixed
some of the names, but NextState returns (an iterator to) a quintuple,
not a state, and the collection States is a collections of quintuples.

>> Do you know how to
>> get it to work? The result will not be a natural use of a set.
>
> The natural use of a std::set it to look things up very quickly with
> no need for a linear search.

That's not the point. You need to play a little trick or a set is the
just the wrong collection.

> I decided to make my system exactly compatible with these code samples:
> http://www.lns.mit.edu/~dsw/turing/examples/examples.html

Here's an interesting test case that's useful for timing and so on:

A_1RB
A11LC
B_1RC
B11RB
C_1RD
C1_LE
D_1LA
D11LD
E_1RH
E1_LA

You will need to add a '(' for DSW compatibility. Also, note that my
interpreter uses _ as the tape's blank symbol. Change all _s to an
actual spaces if that's what you use.

This is (as far as I know) the current BB(5) champion. It runs for more
that 47 million steps before halting.

[Ben]

olcott <polc...@gmail.com> writes:

> On 5/6/2022 8:01 PM, Ben wrote:
>> olcott <polc...@gmail.com> writes:
>>
>>> On 5/6/2022 7:22 PM, Ben wrote:
>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>
>>>>> ThIs looks along the right lines.
>>>>> The quintuples need to be indexed by the current state and the current
>>>>> input, and a set, properly specified, will achieve this.
>>>> How? std::set is not the right container for this.
>>>
>>> std::set::find()
>>>
>>> std::set<Quintuple> States;
>>> std::vector<unsigned char> Tape;
>>> void insert(const Quintuple& QT){ States.insert(QT); };
>>>
>>> std::set<Quintuple>::iterator
>>> NextState(int current_input, int next_state)
>>> {
>>> Quintuple QT(current_input, next_state);
>>> return States.find(QT);
>>> }
>> No, this won't work. You can /make/ it work, but to do that you have to
>> play tricks with what's considered to be unique in the set. I think a
>> std::map is more natural.
>>
>
> I got dem tricks...

Good. In some languages you would not be able to make a set work here
at all.

> std::map has redundant data or splits the class data into two pieces.

We should compare notes when you have it all coded. How long to go? I
just wrote a C++ TM interpreter so we can compare more accurately. (I
have an advantage here in that I've done this several times, so I can't
easily judge how long it might take the first time round.)

>> And your names appear messed up again. NextState (with no declared
>
> It has a declared return type that doesn't fit well on the same line:
> std::set<Quintuple>::iterator

Ah yes. Strange that it's called NextState then.

>> return type) returns a Quintuple, not a state. And it has "next_state"
>> as an argument which seems unlikely. Surely NextState needs the current
>> state and input symbol?
>
> You missed this?
>>> NextState(int current_input, int next_state)

No, I'm talking about the name. next_state does not sound like the
current state.

[Ben]

I wonder... Let's see. There no clear sign in the current sketches
that he can make it work.

--
Ben.

[olcott]

I got everything working besides:
bool Quintuple_List::transition_function(std::set<Quintuple>::iterator&
current_quintuple)

I knew this would be the hardest part. I also got the other TM
interpreter to work correctly. Setting the tape manually is trivial.
I am reviewing other sources for how state transitions work.

[Jeff Barnett]

Questions:

Was 47 million steps a measured or a theoretically computed measure?

How long would you estimate that a well-written TM interpreter on modern
hardware needs to interpret the above? A few seconds or minutes?
--
Jeff Barnett

[olcott]

The TM interpreter uses linear search, I hate that, it doesn't scale.

>> I decided to make my system exactly compatible with these code samples:
>> http://www.lns.mit.edu/~dsw/turing/examples/examples.html
>
> Here's an interesting test case that's useful for timing and so on:
>
> A_1RB
> A11LC
> B_1RC
> B11RB
> C_1RD
> C1_LE
> D_1LA
> D11LD
> E_1RH
> E1_LA
>
> You will need to add a '(' for DSW compatibility. Also, note that my
> interpreter uses _ as the tape's blank symbol. Change all _s to an
> actual spaces if that's what you use.
>
> This is (as far as I know) the current BB(5) champion. It runs for more
> that 47 million steps before halting.
>


--

[Mikko]

On 2022-05-07 16:14:50 +0000, olcott said:

> On 5/7/2022 3:06 AM, Mikko wrote:
>> On 2022-05-06 20:53:58 +0000, olcott said:

>>> class Quintuple_List
>>> {
>>>    std::set<Quintuple> list;
>>>    NextState(int next_state, int current_input)
>>
>> This function should be named getRule. Function names shoule start with
>> a lower case letter.
>>
>
> That would be inconsistent with the spec:
> make a transition to state 's'.

Where in the spec is the requirement that there be a function from
int and int to std::set<Quintuple>::iterator that is named NextState?

Mikko

[Malcolm McLean]

On Sunday, 8 May 2022 at 00:36:12 UTC+1, olcott wrote:
> On 5/7/2022 5:31 PM, Ben wrote:
> > Malcolm McLean <malcolm.ar...@gmail.com> writes:
> >
> >> On Saturday, 7 May 2022 at 02:04:42 UTC+1, Ben wrote:
> >>> Ben <ben.u...@bsb.me.uk> writes:
> >>>
> >>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
> >>>>
> >>>>> ThIs looks along the right lines.
> >>>>> The quintuples need to be indexed by the current state and the current
> >>>>> input, and a set, properly specified, will achieve this.
> >>>>
> >>>> How? std::set is not the right container for this.
> >>> I can answer the how myself now, but I still don't think std::set is the
> >>> right choice as the reader is likely yo be confused by the look-up.
> >>>
> >> A map or an unordered_map would be easier, I agree. But PO has chosen
> >> a set, and that can be made to work.
> >
> > I wonder... Let's see. There no clear sign in the current sketches
> > that he can make it work.
> >
> I got everything working besides:
> bool Quintuple_List::transition_function(std::set<Quintuple>::iterator&
> current_quintuple)
>
> I knew this would be the hardest part. I also got the other TM
> interpreter to work correctly. Setting the tape manually is trivial.
> I am reviewing other sources for how state transitions work.
>

The easiest way to make a set do what you want is to overload the '<' operator
for struct Quintuple.
Then you fill a blank Quintuple with the state and input symbol, and call
the "find" method on the set to retrive the full Quintuple.

It's a fairly horrid interface, but that's C++.

[Richard Damon]

That means it is using the wrong data structure.

I would probably just use an array for the rule storage, having an array
of structures of Next State, Replacement Charactrer, Tape Motion, and
index it on Current State and Current Tape Character.

Then the processing loop is just a tight loop like:

curr_char = tape[index]
next_state = rules[current_state][curr_char].next_state;
tape[index] = rules[current_state][curr_char].new_char;
index += rules[current_state][curr_char].tape_incr;
current_state = next_state;

Add an end test, trace logging, and something to read in the rules and
tape, and you are done.

[Richard Damon]

A well written TM interpreter on modern hardware should be able to do
many millions of steps a second (as I posted a main loop that can do
that), so we are in seconds.

IF we need to generate a trace that can be inspected by a human, we
likely get I/O bound generating that trace, and it may go to order of
minutes to maybe hours

[Malcolm McLean]

Whilst you might write a pure implementation of a Turing machine as a
first step, you're unlikely to use it much. People want to see the machine
buzz and whir away, as it performs its magic.
So that means some sort of graphical interface. Which is orders of
magnitude slower than a simple virtual machine.

[Ben]

Measured.

> How long would you estimate that a well-written TM interpreter on
> modern hardware needs to interpret the above? A few seconds or
> minutes?

$ time ./tm bb-5-2 ""
A B C D E H
1 1LC 1RB _LE 1LD _LA
_ 1RB 1RC 1RD 1LA 1RH

steps=47176874

real 0m0.237s
user 0m0.237s
sys 0m0.000s

This is a C++ interpreter I've just written so that I can compare
designs with anything PO produces. I've not worked on making it fast
though I compiler with -O3 for this test.

It uses a plain std::string for the tape, so I imagine the quality of
the C++ library is the key factor (I've not profiled it yet).

(That table at the start is just the sates transition table written in a
compact form.)

--
Ben.

[Ben]

olcott <No...@NoWhere.com> writes:

> The TM interpreter uses linear search, I hate that, it doesn't scale.

What do you use linear search for? I thought the key structure you used
was a std::set.

[Jeff Barnett]

Impressive. I'm going to conjecture from the rate of interpretation
47M/.237s ~ 200,000,000 states per second that TM definition, your code,
and used library code must have all snuggled into the machine cache. I'm
also assuming that the C++ code (because of the nature of the
computation) does not lend itself to using multiple cores which makes
the speed all that more impressive.

Other questions:

Did you directly set up a (state X character) -> (quintuple) lookup
rather than doing it in two steps? I don't think that wouldn't make a
big difference for this example but could for TM definitions with much
larger quintuple tables.

Do C++ character arrays (strings?) have provisions to grow if a char is
pushed passed the structure's end? I'm thinking of Lisp arrays with fill
pointers as an example. To ask the question a different way which of the
following did you do to set the initial size of the "tape": determine
empirically, start arbitrarily and let the C++ system run-time grow the
structure as needed, or start arbitrarily and use your own code to deal
with the issue?
--
Jeff Barnett

[Richard Damon]

Yes, if you want to watch the machine run, you are limiting your step
rate to Human speed.

If you can watch 1 step a second, the 47 million steps is on the order
of a year and a half at 24-7, but then the limiting factor isn't the
computer but the observer.

You could probably "checkpoint" the results every, say, 1000 steps to
some log, and then build a browser to let you pull up any of the 47,000
checkpoints to see the progress, and maybe do a step by step run from
the checkpoint if interested.

The key point is that the computer running the Turing Machine isn't the
limiting factor for this case, but the human observer.

[Ben]

Thanks, but there's no skill involved, other that not picking any part
of the design that looks like a certain loser.

> I'm going to conjecture from the rate of interpretation 47M/.237s ~
> 200,000,000 states per second that TM definition, your code, and used
> library code must have all snuggled into the machine cache.

Seems likely.

> I'm also
> assuming that the C++ code (because of the nature of the computation)
> does not lend itself to using multiple cores which makes the speed all
> that more impressive.

Yes, single core. My laptop is not an old banger (1.6Ghz i5-8256U), but
even so I was surprised.

> Other questions:
>
> Did you directly set up a (state X character) -> (quintuple) lookup
> rather than doing it in two steps?

There's only one lookup, but not that one. In my current design the
states are objects that hold a char to triple map, the triple being the
character to write, the tape movement, and a pointer to the next state).

The inner loop is therefore very tight. I could (probably) speed it up
a bit by using an array for that lookup, but I imagined I might like to
use fancy Unicode symbols at some stage and a map will work better for
that.

> I don't think that wouldn't make a big difference for this example but
> could for TM definitions with much larger quintuple tables.
>
> Do C++ character arrays (strings?) have provisions to grow if a char
> is pushed passed the structure's end?

push_back is amortised constant time whereas append and insert give no
guarantees. I think glibc goes to some effort to make appending and
growing at the front quote efficient.

> I'm thinking of Lisp arrays with
> fill pointers as an example. To ask the question a different way which
> of the following did you do to set the initial size of the "tape":
> determine empirically, start arbitrarily and let the C++ system
> run-time grow the structure as needed, or start arbitrarily and use
> your own code to deal with the issue?

My code is utterly trivial. The tape is a std::string to which I assign
the input. All that happens after that is that tape[head] is assigned
to, and the string is grown by one blank, either at the front or the
back, if the tape movement requires it.

I'll post the code when the time comes if case anyone cares to see it.

I plan to do a Haskell version too. I used to have one, but that got
lost in retirement.

--
Ben.

[Ben]

You don't really need much. A simple print of the tape (centred on the
head) give the feel for what's happening. Throw in a \r and a delay and
will look like an animation even in a plain tty.

With tracing turned on, my simple implementation shows this for the
BB(4) champion:

$ ./simple-tm bb-4-2 ""
A B C D H
1 1LB _LC 1LD _RA
_ 1RB 1LA 1RH 1RD
________________________________[A|_]_________________________________
________________________________[B|_]_________________________________
________________________________[A|_]_________________________________
_______________________________1[B|_]_________________________________
________________________________[A|1]1________________________________
________________________________[B|_]11_______________________________
________________________________[A|_]111______________________________
_______________________________1[B|1]11_______________________________
________________________________[C|1]_11______________________________
________________________________[D|_]1_11_____________________________
_______________________________1[D|1]_11______________________________
______________________________1_[A|_]11_______________________________
_____________________________1_1[B|1]1________________________________
______________________________1_[C|1]_1_______________________________
_______________________________1[D|_]1_1______________________________
______________________________11[D|1]_1_______________________________
_____________________________11_[A|_]1________________________________
____________________________11_1[B|1]_________________________________
_____________________________11_[C|1]_________________________________
______________________________11[D|_]1________________________________
_____________________________111[D|1]_________________________________
____________________________111_[A|_]_________________________________
___________________________111_1[B|_]_________________________________
____________________________111_[A|1]1________________________________
_____________________________111[B|_]11_______________________________
______________________________11[A|1]111______________________________
_______________________________1[B|1]1111_____________________________
________________________________[C|1]_1111____________________________
________________________________[D|_]1_1111___________________________
_______________________________1[D|1]_1111____________________________
______________________________1_[A|_]1111_____________________________
_____________________________1_1[B|1]111______________________________
______________________________1_[C|1]_111_____________________________
_______________________________1[D|_]1_111____________________________
______________________________11[D|1]_111_____________________________
_____________________________11_[A|_]111______________________________
____________________________11_1[B|1]11_______________________________
_____________________________11_[C|1]_11______________________________
______________________________11[D|_]1_11_____________________________
_____________________________111[D|1]_11______________________________
____________________________111_[A|_]11_______________________________
___________________________111_1[B|1]1________________________________
____________________________111_[C|1]_1_______________________________
_____________________________111[D|_]1_1______________________________
____________________________1111[D|1]_1_______________________________
___________________________1111_[A|_]1________________________________
__________________________1111_1[B|1]_________________________________
___________________________1111_[C|1]_________________________________
____________________________1111[D|_]1________________________________
___________________________11111[D|1]_________________________________
__________________________11111_[A|_]_________________________________
_________________________11111_1[B|_]_________________________________
__________________________11111_[A|1]1________________________________
___________________________11111[B|_]11_______________________________
____________________________1111[A|1]111______________________________
_____________________________111[B|1]1111_____________________________
______________________________11[C|1]_1111____________________________
_______________________________1[D|1]1_1111___________________________
______________________________1_[A|1]_1111____________________________
_______________________________1[B|_]1_1111___________________________
________________________________[A|1]11_1111__________________________
________________________________[B|_]111_1111_________________________
________________________________[A|_]1111_1111________________________
_______________________________1[B|1]111_1111_________________________
________________________________[C|1]_111_1111________________________
________________________________[D|_]1_111_1111_______________________
_______________________________1[D|1]_111_1111________________________
______________________________1_[A|_]111_1111_________________________
_____________________________1_1[B|1]11_1111__________________________
______________________________1_[C|1]_11_1111_________________________
_______________________________1[D|_]1_11_1111________________________
______________________________11[D|1]_11_1111_________________________
_____________________________11_[A|_]11_1111__________________________
____________________________11_1[B|1]1_1111___________________________
_____________________________11_[C|1]_1_1111__________________________
______________________________11[D|_]1_1_1111_________________________
_____________________________111[D|1]_1_1111__________________________
____________________________111_[A|_]1_1111___________________________
___________________________111_1[B|1]_1111____________________________
____________________________111_[C|1]__1111___________________________
_____________________________111[D|_]1__1111__________________________
____________________________1111[D|1]__1111___________________________
___________________________1111_[A|_]_1111____________________________
__________________________1111_1[B|_]1111_____________________________
___________________________1111_[A|1]11111____________________________
____________________________1111[B|_]111111___________________________
_____________________________111[A|1]1111111__________________________
______________________________11[B|1]11111111_________________________
_______________________________1[C|1]_11111111________________________
________________________________[D|1]1_11111111_______________________
________________________________[A|1]_11111111________________________
________________________________[B|_]1_11111111_______________________
________________________________[A|_]11_11111111______________________
_______________________________1[B|1]1_11111111_______________________
________________________________[C|1]_1_11111111______________________
________________________________[D|_]1_1_11111111_____________________
_______________________________1[D|1]_1_11111111______________________
______________________________1_[A|_]1_11111111_______________________
_____________________________1_1[B|1]_11111111________________________
______________________________1_[C|1]__11111111_______________________
_______________________________1[D|_]1__11111111______________________
______________________________11[D|1]__11111111_______________________
_____________________________11_[A|_]_11111111________________________
____________________________11_1[B|_]11111111_________________________
_____________________________11_[A|1]111111111________________________
______________________________11[B|_]1111111111_______________________
_______________________________1[A|1]11111111111______________________
________________________________[B|1]111111111111_____________________
________________________________[C|_]_111111111111____________________
_______________________________1[H|_]111111111111_____________________
steps=109

--
Ben.

[Richard Damon]

My thinking is that there are only two things that have the ability to
"cost" time. One is tape management, but using an object that acts like
an array which is indexed in makes this fast except when we need to
expand it, but that will generally amortize to a small value. (Letting
the string class do that isn't a bad option).

The second "costly" operation is looking up the rule based on current
state / tape symbol. For speed this really needs to be O(1) (at least
amortized). If we reduce our state and input symbols to an internal
numbering of 0-n an array works great. If we limit our states to 'ascii
characters' then the 256 x 256 array isn't outlandish in space
requirements for modern machines.

If you want full Unicode characters, then either you need the conversion
to a simple 0-n enumeration, or going to a hash table to store the
rules. The question becomes which cost more the input/output conversion
to use 0-n values, or hashing (and handling the possible collisions).

My thought is that in the 0-n enumeration, the table is "dense" in the
sense that all non-terminal state will be fully filled out. (And
terminal states don't actually need an entry, just a value recognized as
terminal).

[Mr Flibble]

Have you considered std::deque? Might be worth trying if the tape
sequence isn't small.

/Flibble

[Jeff Barnett]

Why not just "compile" the tuples into a graph? Take all the tuples
defined by one state and sort them on current character and look up by
binary search. If you have a truly large character set and many states
have lots of out-branches, then organize the nodes using hash tables as
you suggest.

It's interesting to note that many Common Lisp make such representation
decisions under the table especially for sorting and hashing. For
example sorting chooses from n^2 complexity sorting for short sequences
to n*log(n) varieties as the input is longer. Hashing starts with just a
linear list and linear time searching for small tables and switches
representations to arrays when the number of elements increase. Many of
these strategies use strategies depending on the comparison predicate.
All of these morphs are swept under the rug by using its object system
and dynamic ability to morph structures, dynamically, to different types.

>
>>
>>> I don't think that wouldn't make a big difference for this example but
>>> could for TM definitions with much larger quintuple tables.
>>>
>>> Do C++ character arrays (strings?) have provisions to grow if a char
>>> is pushed passed the structure's end?
>>
>> push_back is amortised constant time whereas append and insert give no
>> guarantees.  I think glibc goes to some effort to make appending and
>> growing at the front quote efficient.
>>
>>> I'm thinking of Lisp arrays with
>>> fill pointers as an example. To ask the question a different way which
>>> of the following did you do to set the initial size of the "tape":
>>> determine empirically, start arbitrarily and let the C++ system
>>> run-time grow the structure as needed, or start arbitrarily and use
>>> your own code to deal with the issue?
>>
>> My code is utterly trivial.  The tape is a std::string to which I assign
>> the input.  All that happens after that is that tape[head] is assigned
>> to, and the string is grown by one blank, either at the front or the
>> back, if the tape movement requires it.
>>
>> I'll post the code when the time comes if case anyone cares to see it.
>>
>> I plan to do a Haskell version too.  I used to have one, but that got

>> lost in retirement.--
Jeff Barnett

[olcott]

Yes that is the way that I did it.
David S. Woodruff simply does a linear search.

When I am refraining from doing work on Sunday, responding to your posts
has a higher priority than responding to anyone else's posts because you
are my only reviewer that has been consistently honest.

All of my other reviewers have at least a very strong bias for rebuttal
thus causing an honest dialogue to have much less priority.

[Ben]

Ben <ben.u...@bsb.me.uk> writes:

> With tracing turned on, my simple implementation shows this for the
> BB(4) champion:
>
> $ ./simple-tm bb-4-2 ""
> A B C D H
> 1 1LB _LC 1LD _RA
> _ 1RB 1LA 1RH 1RD
> ________________________________[A|_]_________________________________
> ________________________________[B|_]_________________________________

There was a bug (now fixed) so that when the initial tape is empty there
would be a couple of false transitions.

--
Ben.

[olcott]

Mine is almost working.
I got David S. Woodruff's TM.exe to show me the trace
that I am supposed to get on his paren.tm program.

My TM.cpp does the first four steps of this correctly.

[Ben]

olcott <No...@NoWhere.com> writes:

> On 5/8/2022 9:14 PM, Ben wrote:
>> Ben <ben.u...@bsb.me.uk> writes:
>>
>>> With tracing turned on, my simple implementation shows this for the
>>> BB(4) champion:
>>>
>>> $ ./simple-tm bb-4-2 ""
>>> A B C D H
>>> 1 1LB _LC 1LD _RA
>>> _ 1RB 1LA 1RH 1RD
>>> ________________________________[A|_]_________________________________
>>> ________________________________[B|_]_________________________________
>> There was a bug (now fixed) so that when the initial tape is empty there
>> would be a couple of false transitions.
>
> Mine is almost working.
> I got David S. Woodruff's TM.exe to show me the trace
> that I am supposed to get on his paren.tm program.

If you want, I can provide traces for testing. My interpreter takes a
trace format argument so there's a reasonable chance I can make traces
similar to yours.

> My TM.cpp does the first four steps of this correctly.

A reasonable test would be if you get the same number of steps for BB(4)
and BB(5). BB(4) is (as above)

A B C D H
1 1LB _LC 1LD _RA
_ 1RB 1LA 1RH 1RD

and BB(5) is

A B C D E H
1 1LC 1RB _LE 1LD _LA
_ 1RB 1RC 1RD 1LA 1RH

BB(4) halts after 107 steps. B(5) halts after 47176870 steps.
Obviously the output could also be compared.

[olcott]

Conventionally tapes have an actual beginning, yet no fixed end.

> I'll post the code when the time comes if case anyone cares to see it.
>
> I plan to do a Haskell version too. I used to have one, but that got
> lost in retirement.
>


--

[olcott]

On 5/8/2022 8:46 AM, Ben wrote:
> olcott <No...@NoWhere.com> writes:
>
>> The TM interpreter uses linear search, I hate that, it doesn't scale.
>
> What do you use linear search for? I thought the key structure you used
> was a std::set.
>

David S. Woodruff's TM interpretor uses linear search.

[olcott]

For example, the quintuple 'SCcsm' is executed by the machine:
If it is in state 'S' and is reading the symbol 'C' on the tape then
(a) make a transition to state 's'.
(b) overwrite the symbol 'C' on the tape with the symbol 'c'.
// Must do this before transition to state 's' or we lose 'c' from S.
(c) move the tape reading head one symbol to the left or right
according to whether 'm' is 'l' or 'r'.
http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt

[olcott]

The classic TM is not allowed to move before its beginning thus a
std::vector is best for the tape.

[Ben]

olcott <No...@NoWhere.com> writes:

> The classic TM is not allowed to move before its beginning thus a
> std::vector is best for the tape.

In the usual definition the tape has no beginning so I can't make out
what you are saying here. Something about it is wrong but I tell
exactly what.

[Ben]

No.

[olcott]

On 5/9/2022 5:08 PM, Ben wrote:
> olcott <No...@NoWhere.com> writes:
>
>> The classic TM is not allowed to move before its beginning thus a
>> std::vector is best for the tape.
>
> In the usual definition the tape has no beginning so I can't make out
> what you are saying here. Something about it is wrong but I tell
> exactly what.
>

Linz agrees with you, Kozen agrees with me and I can't find where Sipser
specifies this.

[olcott]

On 5/9/2022 5:14 PM, Ben wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 5/8/2022 1:27 PM, Ben wrote:
>
>>> My code is utterly trivial. The tape is a std::string to which I assign
>>> the input. All that happens after that is that tape[head] is assigned
>>> to, and the string is grown by one blank, either at the front or the
>>> back, if the tape movement requires it.
>>
>> Conventionally tapes have an actual beginning, yet no fixed end.
>
> No.
>

Sipser and Kozen agree with me, Linz agrees with you.

[Ben]

olcott <No...@NoWhere.com> writes:

> On 5/9/2022 5:14 PM, Ben wrote:
>> olcott <No...@NoWhere.com> writes:
>>
>>> On 5/8/2022 1:27 PM, Ben wrote:
>>
>>>> My code is utterly trivial. The tape is a std::string to which I assign
>>>> the input. All that happens after that is that tape[head] is assigned
>>>> to, and the string is grown by one blank, either at the front or the
>>>> back, if the tape movement requires it.
>>>
>>> Conventionally tapes have an actual beginning, yet no fixed end.
>>
>> No.
>
> Sipser and Kozen agree with me, Linz agrees with you.

None of these authors say what is "conventional". What is certain is
that if there were a convention, an author not using that convention
should say as much. You'll find, however, that that is not the case.

[Richard Damon]

On 5/9/22 6:32 PM, olcott wrote:
> On 5/9/2022 5:08 PM, Ben wrote:
>> olcott <No...@NoWhere.com> writes:
>>
>>> The classic TM is not allowed to move before its beginning thus a
>>> std::vector is best for the tape.
>>
>> In the usual definition the tape has no beginning so I can't make out
>> what you are saying here.  Something about it is wrong but I tell
>> exactly what.
>>
> Linz agrees with you, Kozen agrees with me and I can't find where Sipser
> specifies this.
>

The truth is that this is one area where different models of Turing
Machines define the tape differently.

Just like some allow for multiple tapes (and thus multiple "tape op"
fields in the instruction, and multiple tape symbols in the rule lookup.)

It can be shown that all the variations are computationally equivalent,
it just changes how complicated some operations are.

For a tape with a fixed beginning spot, if you wanted to extend it in
that dirrection, you just need a short program to go to the other end
and move ever cell out one cell to make room.

Since the tape is finite, this is by definition doable in a finite
number of steps.

[Ben]

olcott <No...@NoWhere.com> writes:

> On 5/9/2022 5:08 PM, Ben wrote:
>> olcott <No...@NoWhere.com> writes:
>>
>>> The classic TM is not allowed to move before its beginning thus a
>>> std::vector is best for the tape.
>> In the usual definition the tape has no beginning so I can't make out
>> what you are saying here. Something about it is wrong but I tell
>> exactly what.
>>
> Linz agrees with you, Kozen agrees with me and I can't find where
> Sipser specifies this.

The definition is simpler if the tape in unbounded at both ends. If you
are going to use any of the BB candidates as tests, you need a tape open
at both ends.

Given that you've gone for a one-ended tape, what rule do you apply when
the transition function specifies going left from the left-most cell?

I've modified my implementation to do either, just in case we end up
comparing traces.

[olcott]

On 5/9/2022 7:13 PM, Ben wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 5/9/2022 5:14 PM, Ben wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>
>>>>> My code is utterly trivial. The tape is a std::string to which I assign
>>>>> the input. All that happens after that is that tape[head] is assigned
>>>>> to, and the string is grown by one blank, either at the front or the
>>>>> back, if the tape movement requires it.
>>>>
>>>> Conventionally tapes have an actual beginning, yet no fixed end.
>>>
>>> No.
>>
>> Sipser and Kozen agree with me, Linz agrees with you.
>
> None of these authors say what is "conventional". What is certain is
> that if there were a convention, an author not using that convention
> should say as much. You'll find, however, that that is not the case.
>

How would you define conventional?
The most typical use is one way unlimited, right?

[olcott]

On 5/9/2022 7:37 PM, Ben wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 5/9/2022 5:08 PM, Ben wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> The classic TM is not allowed to move before its beginning thus a
>>>> std::vector is best for the tape.
>>> In the usual definition the tape has no beginning so I can't make out
>>> what you are saying here. Something about it is wrong but I tell
>>> exactly what.
>>>
>> Linz agrees with you, Kozen agrees with me and I can't find where
>> Sipser specifies this.
>
> The definition is simpler if the tape in unbounded at both ends. If you
> are going to use any of the BB candidates as tests, you need a tape open
> at both ends.
>
> Given that you've gone for a one-ended tape, what rule do you apply when
> the transition function specifies going left from the left-most cell?
>

(a) Abnormal termination error index out-of-bounds.
(b) Extend the std::vector.

> I've modified my implementation to do either, just in case we end up
> comparing traces.
>


--

[Richard Damon]

On 5/9/22 9:28 PM, olcott wrote:
> On 5/9/2022 7:13 PM, Ben wrote:
>> olcott <No...@NoWhere.com> writes:
>>
>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>> olcott <No...@NoWhere.com> writes:
>>>>
>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>
>>>>>> My code is utterly trivial.  The tape is a std::string to which I
>>>>>> assign
>>>>>> the input.  All that happens after that is that tape[head] is
>>>>>> assigned
>>>>>> to, and the string is grown by one blank, either at the front or the
>>>>>> back, if the tape movement requires it.
>>>>>
>>>>> Conventionally tapes have an actual beginning, yet no fixed end.
>>>>
>>>> No.
>>>
>>> Sipser and Kozen agree with me, Linz agrees with you.
>>
>> None of these authors say what is "conventional".  What is certain is
>> that if there were a convention, an author not using that convention
>> should say as much.  You'll find, however, that that is not the case.
>>
>
> How would you define conventional?
> The most typical use is one way unlimited, right?
>

Actually, I see unlimited in both directions as more normal, otherwise
you get the odd case of what happens if the system tries to move past
the end of the tape. It basically says you need a special character for
that end of the tape, which just adds an asymmetry to the system.

As I mentioned, it is just a small bit of code to implement an expand
the tape one cell in that direction that just needs to be added to every
case to handle running into the beginning of tape symbol, so there is no
difference in what can be computed, just how much work you need to do
that computation.

The one-directional tape may be easier on the simulator, but that is
just a small advantage, and the impact on the Turing Machine is an
uglification and asymmetry so it seems common to just make the tape
double ended.

Maybe very simple examples for teaching might seem simpler with a single
ended, since you don't need to think as much about where you need to
leave space on your page that you are keeping track of your tape on, and
many of the simple problems only need to extend in one direction, but
that is only a small benifit, and again, you need to add a dedicated
'Beginning of tape' symbol to let the machine know that is the edge (you
might be able to make it double as an end of tape that is allowed to be
overwritten in the other direction.

[Malcolm McLean]

As a mathematical model, a tape which is open at both ends is simpler.

If you are engineering a physical machine, a tape which extends arbitrarily
in only one direction may well be easier to implement. As you say, it's easier
to draw the tape, for example.

[Ben]

olcott <No...@NoWhere.com> writes:

> On 5/9/2022 7:13 PM, Ben wrote:
>> olcott <No...@NoWhere.com> writes:
>>
>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>> olcott <No...@NoWhere.com> writes:
>>>>
>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>
>>>>>> My code is utterly trivial. The tape is a std::string to which I assign
>>>>>> the input. All that happens after that is that tape[head] is assigned
>>>>>> to, and the string is grown by one blank, either at the front or the
>>>>>> back, if the tape movement requires it.
>>>>>
>>>>> Conventionally tapes have an actual beginning, yet no fixed end.
>>>>
>>>> No.
>>>
>>> Sipser and Kozen agree with me, Linz agrees with you.
>>
>> None of these authors say what is "conventional". What is certain is
>> that if there were a convention, an author not using that convention
>> should say as much. You'll find, however, that that is not the case.
>
> How would you define conventional?

"the accepted or traditional method of doing something"

> The most typical use is one way unlimited, right?

I don't know. I know it's not a widely agreed convention, but what it
"typical" is hard to assess. I think double-open is more commonly used in
modern presentations, but the only real way to know would be to do a
survey and I don't think the topic merits that.

From a technical point of view, double-open is clearly preferable as it
removes a special case with no technical down-side.

[Ben]

olcott <No...@NoWhere.com> writes:

> On 5/9/2022 7:37 PM, Ben wrote:
>> olcott <No...@NoWhere.com> writes:
>>
>>> On 5/9/2022 5:08 PM, Ben wrote:
>>>> olcott <No...@NoWhere.com> writes:
>>>>
>>>>> The classic TM is not allowed to move before its beginning thus a
>>>>> std::vector is best for the tape.
>>>> In the usual definition the tape has no beginning so I can't make out
>>>> what you are saying here. Something about it is wrong but I tell
>>>> exactly what.
>>>>
>>> Linz agrees with you, Kozen agrees with me and I can't find where
>>> Sipser specifies this.
>>
>> The definition is simpler if the tape in unbounded at both ends. If you
>> are going to use any of the BB candidates as tests, you need a tape open
>> at both ends.
>>
>> Given that you've gone for a one-ended tape, what rule do you apply when
>> the transition function specifies going left from the left-most cell?
>>
> (a) Abnormal termination error index out-of-bounds.

There is no such concept for a Turing machine. The TM can be defined to
halt in this situation (though I don't know any authors who specify it
like that) but halting is halting no matter the reason.

> (b) Extend the std::vector.

Why extend the vector if you've terminated?

>> I've modified my implementation to do either, just in case we end up
>> comparing traces.

Anywhere closer to writing E and specifying P?

[Malcolm McLean]

There's a technical downside if you implement the tape in the obvious way,
as a dynamic buffer. Most languages make it quite fast to append characters
to the buffer's end. There's usually spare memory there in the system, so
the push_back() operation is just a case of incrementing a size field.
push_front(), however, generally requires a push_back, followed by a move
for the entire buffer.

There are ways round this, of course, but you have to know what you are doing,
and it's not as easy to write. ,

[Ben]

I meant for the theory of such machines. It's the theory and the
theorems that will dictate which style an authors chooses and there's no
down-side in that context.

> There's usually spare memory there in the system, so
> the push_back() operation is just a case of incrementing a size field.

If you do the resizing right, the same is true of push_front().

> push_front(), however, generally requires a push_back, followed by a move
> for the entire buffer.

Every now and then, your realloc will need an extra move, but that's a
cost that will be amortised if you do the usual exponential resizing.

> There are ways round this, of course, but you have to know what you
> are doing, and it's not as easy to write.

Gosh, you have a low opinion of what's generally understood! Maybe I
have too high an opinion, but growing a buffer at one or other or even
both ends seems to me to be utterly trivial.

--
Ben.

[olcott]

https://en.cppreference.com/w/cpp/container/deque
push_back adds an element to the end
push_front inserts an element to the beginning

[olcott]

https://en.cppreference.com/w/cpp/container/deque
push_back adds an element to the end
push_front inserts an element to the beginning

[Richard Damon]

Yes, but they are arguing about what works efficiently.

deque is designed for this, so both are likely reasonably efficient,
though all extentions that need a realloc to the front will need a move,
while some realloction to the end won't.

Note, I think some people are still thinking about string, which
generally doesn't preallocate extra space to the front of the string
(because push_front isn't a common operation) which deque almost
certainly does (would need to see if required by complexity specifications).

[Ben]

I think everyone here knows that.

Using std::deque was suggested before (by Jeff I think), but at nearly
200 million steps a second, I didn't think there was much room for a
speed-up.

I've just tried it, and using std::deque rather than std::string slows
my implementation down to 106 million steps a second, and it doesn't
simplify the logic at all. In fact, the few places where you really
want a string get a bit more fiddly.

Mind you, the speed is almost irrelevant unless you are hunting for BB
champions.

[Jeff Barnett]

One possibility is to use a linked list where each node contains a
character, a pointer to the following node, and a pointer to the
previous node. Since the TM can only move one tape square per state
transition, the cache will do a good job of speeding things up. Of
course storage per character is more and that will slow things down.

Another way to make tape storage almost all characters is to allocate a
block (page sized) at a time with one block initially. A block is
allocated each time you are about to go off either the front or back end
and is linked. The cache hit ratio is extremely good and only a tiny
fraction less then using a big array. It wins, however, when growing an
array would cause you to move it.
--
Jeff Barnett

[Mr Flibble]

std::string (or std::vector) will likely win for small N and std::deque
for large N as far as push_front is concerned.

/Flibble

[dklei...@gmail.com]

If you are not actually implementing a machine replacing the tape by a pair of
stacks is attractive. Actually you replace the tape by three things - two stacks
(called for example left and right) and a single focus cell.

But none of this is really needed. We don't really need TM's for anything
practical.

[Ben]

I'm sure that's true. std::string /could/ be made fast for inserts at
position 0 (there is no push_front for a string) but I doubt that case
has been optimised.

But very long tapes will be rare though. And for them to occur there
has to be quite of lots going back and forth as well so I'm not sure if
the tape growth cost will ever dominate.

My test case (BB(5)) ends up with a resulting tape of 12,289 characters,
and all but 45 of those were added at the front. Of course, 12,289 is
not really a long string, and the vast majority of moves happened away
form the "ends".

--
Ben.

[olcott]

This is the best idea yet. I spent all day researching this
on my cell phone during chemotherapy infusion.

I am implemented this idea in code and will post it as another
reply to your message.

[olcott]

On 5/9/2022 7:37 PM, Ben wrote:
> olcott <No...@NoWhere.com> writes:
>
>> On 5/9/2022 5:08 PM, Ben wrote:
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> The classic TM is not allowed to move before its beginning thus a
>>>> std::vector is best for the tape.
>>> In the usual definition the tape has no beginning so I can't make out
>>> what you are saying here. Something about it is wrong but I tell
>>> exactly what.
>>>
>> Linz agrees with you, Kozen agrees with me and I can't find where
>> Sipser specifies this.
>
> The definition is simpler if the tape in unbounded at both ends. If you
> are going to use any of the BB candidates as tests, you need a tape open
> at both ends.
>

You have convinced me that this is the best way I am going to implement
this using David kleinecke's solution. It is a much more efficient and
simpler way to implement push_back() and push_front() than std::deque
that also has none of the pitfalls such as:

https://www.cplusplus.com/reference/deque/deque/push_front/
All iterators related to this container are invalidated.

> Given that you've gone for a one-ended tape, what rule do you apply when
> the transition function specifies going left from the left-most cell?
>
> I've modified my implementation to do either, just in case we end up
> comparing traces.
>


--

[olcott]

David kleinecke's solution is a much more efficient and simpler way to

implement push_back() and push_front() than std::deque that also has
none of the pitfalls such as:

https://www.cplusplus.com/reference/deque/deque/push_front/
All iterators related to this container are invalidated.

[Ben]

I've tried both (two stacks and two stacks and a cell) and I think the
extra cell just makes it a bit fussy.

If you have an array of two stacks:

stack<symbol> tape[2];

and 'dir' is the move direction as 0 or 1, then

tape[dir].push(tape[!dir].pop())

is the move operation. Reading the tape cell is done just once per
step, so tape[0].top() is not going to be expensive.

>> But none of this is really needed. We don't really need TM's for anything
>> practical.
>
> This is the best idea yet. I spent all day researching this
> on my cell phone during chemotherapy infusion.
>
> I am implemented this idea in code and will post it as another
> reply to your message.

My Haskell TM interpreter did it this way with a pair of strings
(Haskell strings are essentially stacks). But I've lost the code. I
might have time to re-create it.

[olcott]

David kleinecke's solution is a much more efficient and simpler way to
implement push_back() and push_front() than std::deque that also has
none of the pitfalls such as:

https://www.cplusplus.com/reference/deque/deque/push_front/
All iterators related to this container are invalidated.

I consider it an optimal solution and the one that I am implementing.

[olcott]

std::vector <is> essentially a stack.

struct Tape
{
unsigned int Tape_Head;
std::vector<unsigned char> Left;
std::vector<unsigned char> Right;
unsigned int move_left();
unsigned int move_right();
};

Tape_Head is mapped to its location in Left or Right.
I am still working out the details of this part.

[Mike Terry]

I think you've misunderstood DK's and Ben's approaches. I think what you're suggesting is that Left
handles all the "negative" tape head positions, and Right all the "positive" ones, while Tape_Head
contains the tape head index (positive or negative) which changes by 1 each time the head moves?

DK and Ben propose two stacks, and with this approach the tape head is effectively always in a fixed
place "in between the two stacks", or (with Ben's) at the top of [say] the left stack. So there is
no Tape_Head index to track.

But what you suggest is quite workable...

I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a
comfortably large chosen page size. (But efficiency really isn't an issue for this task!)


Mike.

[olcott]

On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:

std::vector essentially <is> a stack.

I consider your solution optimal. Here is the first part of its
implementation:

struct Tape
{
unsigned int Tape_Head;
std::vector<unsigned char> Left;
std::vector<unsigned char> Right;
unsigned int move_left();
unsigned int move_right();
};

Tape_Head is mapped to its location in Left or Right.

[olcott]

Not in the least little bit. Please wait until you see my full
implementation before passing judgement. David's solution is optimal.

> DK and Ben propose two stacks, and with this approach the tape head is
> effectively always in a fixed place "in between the two stacks", or
> (with Ben's) at the top of [say] the left stack.  So there is no
> Tape_Head index to track.
>
> But what you suggest is quite workable...
>
> I think if I were interested in ultimate efficiency, I might go with
> Jeff's "chained blocks" with a comfortably large chosen page size.  (But
> efficiency really isn't an issue for this task!)
>
>
> Mike.
>

My implementation of David's solution essentially redefines the whole
notion of std::deque with std:vector's (memory and speed) efficiency and
none of std::deque's limitations: (such as invalidating iterators).

[Jeff Barnett]

I'm not sure what any of what you said has to do with what I wrote. All
I assume from the runtime is a way of occasionally allocating some multi
page-sized blocks. That and a few lines (a dozen or so) of code will
handle the allocation and usage: fairly trivial and quick stuff.
--
Jeff Barnett

[Ben]

You can certainly use a std::vector as a stack but I'd derive my own
stack from a vector so as to make it infinitely "popable" with the pop
operation returning the tape's blank symbol.

> struct Tape
> {
> unsigned int Tape_Head;
> std::vector<unsigned char> Left;
> std::vector<unsigned char> Right;
> unsigned int move_left();
> unsigned int move_right();
> };
>
> Tape_Head is mapped to its location in Left or Right.
> I am still working out the details of this part.

This looks odd. If you use the two stacks approach, you don't need
Tape_Head. The current cell is never indexed but is always the top of
the Right stack.

[olcott]

The current Tape_Head maps to elements of Left or Right
or to an element before Left or after Right.

[Malcolm McLean]

On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>
> But what you suggest is quite workable...
>
> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a
> comfortably large chosen page size. (But efficiency really isn't an issue for this task!)
>

The tape is unbounded. And even some very simple machines will fill it up to infinity.
If you stop the machine when the process runs out of memory, which is a reasonable
strategy, you don't want O(N) tape write operations.

Chained blocks are probably the best model. They don't scale up, so a machine that was written
for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know
the approximate szie of your tape, however, then blocks are a good solution.

[Ben]

Even talking about code you won't address the points made -- you just
assert something equally wrong. I won't repeat what I said. Address it
if you like or not.

[olcott]

I prefer the exponential memory allocation of std:vector.
It seems to be the optimal balance between speed and memory use.

My implementation of David Kleinecke's double stack based std::deque
will allow std::deque::push_front() to work exactly the same way as
std:vector::push_back().

It doesn't invalidate iterators or integer subscripts or have any of the
extra (memory or time) overhead of std:deque. It seems to me to simply
be a much better way to implement the same functionality as std::deque.

[olcott]

No need for the pop operation.

>> struct Tape
>> {
>> unsigned int Tape_Head;
>> std::vector<unsigned char> Left;
>> std::vector<unsigned char> Right;
>> unsigned int move_left();
>> unsigned int move_right();
>> };
>>
>> Tape_Head is mapped to its location in Left or Right.
>> I am still working out the details of this part.
>
> This looks odd. If you use the two stacks approach, you don't need
> Tape_Head. The current cell is never indexed but is always the top of
> the Right stack.
>

That is simply factually incorrect with my implementation of David
Kleinecke's double stack based std::deque applied to a doubled ended TM
tape.

[Mike Terry]

Then you've not understood DK and Ben's approach, like I said. Your replies are typical of you not
reading what people write, or simply not understanding what they've written. Do you know what a
stack is?

So, tell us what how Tape_Head changes as the TM runs? Is it not the case Tape_Head will go up by 1
for each R tape movement and down for a L tape movement? (I.e. exactly like I suggested in my
earlier post, when you replied "not in the least little bit"?) THAT IS NOT DK/BEN'S TWO STACK DESIGN.

Mike.

[Mike Terry]

I don't get why you say a chained block approach doesn't scale up. Such a design works well until
the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine with
page files etc.. When the tape gets very large, only a small portion of it needs to be in the
working set for the process to avoid paging.

The only design I can think of that might scale up better would be one using an output device larger
than the logical address space limit. Maybe you were just saying that a hard-coded small block size
(for a ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you
would use a chained block approach on such a tiny machine! Perhaps you meant to say the design
doesn't scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at
run time if we like.)

Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory around
when the vector/string is extended, so perhaps you meant to say that /those/ designs don't scale up,
but the chained blocks scale up?


Mike.

[olcott]

The specified Tape_Head increments/decrements for move_right/move_left.
The tricky part of this is mapping this to integer subscripts of
Left/Right when both Left/Right can dynamically grow in size.

> (I.e. exactly like I suggested in my earlier post, when
> you replied "not in the least little bit"?)    THAT IS NOT DK/BEN'S TWO
> STACK DESIGN.
>
> Mike.

[olcott]

On 5/11/2022 10:27 AM, Mike Terry wrote:
> On 11/05/2022 10:19, Malcolm McLean wrote:
>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>>>
>>> But what you suggest is quite workable...
>>>
>>> I think if I were interested in ultimate efficiency, I might go with
>>> Jeff's "chained blocks" with a
>>> comfortably large chosen page size. (But efficiency really isn't an
>>> issue for this task!)
>>>
>> The tape is unbounded. And even some very simple machines will fill it
>> up to infinity.
>> If you stop the machine when the process runs out of memory, which is
>> a reasonable
>> strategy, you don't want O(N) tape write operations.
>>
>> Chained blocks are probably the best model. They don't scale up, so a
>> machine that was written
>> for a 16K ZX81 might struggle when ported to a 16GB typical modern
>> desktop. If you know
>> the approximate szie of your tape, however, then blocks are a good
>> solution.
>>
>
> I don't get why you say a chained block approach doesn't scale up.  Such
> a design works well until the logical (user) address space is filled,
> which is absolutely huge on a modern 64-bit machine with page files
> etc..  When the tape gets very large, only a small portion of it needs
> to be in the working set for the process to avoid paging.
>

The exponential growth rate factor of std::vector seems to be a more
efficient tradeoff of space versus time and does not have the extra
(space/time) overhead of multiple levels of reference.

> The only design I can think of that might scale up better would be one
> using an output device larger than the logical address space limit.
> Maybe you were just saying that a hard-coded small block size (for a

The fastest output devices are still enormously slower than RAM.

> ZX81?) is not as efficient as big blocks if you've got lots of memory?
> I don't see that you would use a chained block approach on such a tiny
> machine!  Perhaps you meant to say the design doesn't scale /down/
> rather than up?  (And the size of chained blocks can be dynamically
> decided at run time if we like.)
>
> Other designs, e.g. using vector or strings will involve copying ever
> larger blocks of memory around when the vector/string is extended, so
> perhaps you meant to say that /those/ designs don't scale up, but the
> chained blocks scale up?
>
>
> Mike.

Empirical testing seems to prove that std::vector is faster than other
methods because it greatly reduces the number of allocations required.

[Mike Terry]

So you don't understand DK/Ben's two stack approach, and you don't understand the chained blocks
approach. I could ask "what empirical testing?" but that would just be a waste of time, so I won't...

Anyway, none of that matters - just concentrate on finishing your coding! (I did say that your two
vector approach was ok, so I was never suggesting you're incapable of finishing it, or that it can't
work or anything...)

Mike.

[Ben]

You still don't understand the two stack method. Here is a sketch of
how it's done. The reason it's efficient (in so far as it is) is that
the tape move is simply:

if (go_right) left.push(right.pop());
else right.push(left.pop());

---------- code -------
#include <iostream>
#include <vector>
#include <string>

struct infinite_stack : public std::vector<char> {
char top() const { return empty() ? '_' : back(); }
char pop() { char c = top(); if (!empty()) pop_back(); return c; }
void push(char c) { push_back(c); }
};

struct tape {
tape(std::string s);
infinite_stack left, right;
void move(bool go_right) {
if (go_right) left.push(right.pop());
else right.push(left.pop());
}
friend std::ostream &operator<<(std::ostream &os, const tape &t);
};

tape::tape(std::string s)
{
for (auto i = s.size(); i-- > 0;) right.push(s[i]);
}

std::ostream &operator<<(std::ostream &os, const tape &t)
{
for (char c : t.left) os.put(c);
os << '[' << t.right.top() << ']';
for (auto i = t.right.size() - 1; i-- > 0;) os.put(t.right[i]);
return os;
}

int main()
{
tape test("abcdef");
std::cout << test << "\n";
test.move(0); std::cout << test << "\n";
test.move(0); std::cout << test << "\n";
test.move(1); std::cout << test << "\n";
test.move(1); std::cout << test << "\n";
test.move(1); std::cout << test << "\n";

[olcott]

I think that my way is more efficient.
I will post it as soon as it is done.

[Malcolm McLean]

I was thinking that the chained block degenerates into effectively a linked list when block size becomes
small in relation to tape length. However that isn't really a problem - it still works more effectively
than a contiguous model.

[olcott]

The actual run-time cost issue is not copying data, this is fairly
cheap. A linear growth factor has far many more very expensive operating
system memory allocation calls than an exponential growth factor.

[Ben]

olcott <No...@NoWhere.com> writes:

> On 5/11/2022 2:35 PM, Ben wrote:
>> olcott <No...@NoWhere.com> writes:
>>
>>> On 5/10/2022 10:02 PM, Ben wrote:
>>
>>>> You can certainly use a std::vector as a stack but I'd derive my own
>>>> stack from a vector so as to make it infinitely "popable" with the pop
>>>> operation returning the tape's blank symbol.
>>>
>>> No need for the pop operation.

That may well be the case. But your way is not the "two stacks" way if
there is no need for pop.