XPost: comp.theory, sci.logic

On 5/6/2022 4:29 PM, Mr Flibble wrote:

On Fri, 6 May 2022 16:25:58 -0500
olcott <[email protected]> wrote:

On 5/6/2022 4:08 PM, Mr Flibble wrote:

On Fri, 6 May 2022 15:53:58 -0500
olcott <[email protected]> wrote:

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;
}

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;
};

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)