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

[olcott]

On 5/6/2022 4:29 PM, Mr Flibble wrote:
> On Fri, 6 May 2022 16:25:58 -0500
> olcott <polc...@gmail.com> wrote:
>
>> On 5/6/2022 4:08 PM, Mr Flibble wrote:

>>> If you are going to use C++ for this then at least create proper
>>> abstractions rather than a struct containing anonymous types. At the
>>
>> 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.
>
> 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
>

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;