XPost: comp.theory, sci.logic
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
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)