On Fri, 6 May 2022 16:25:58 -0500
olcott <polcott2@gmail.com> wrote:
On 5/6/2022 4:08 PM, Mr Flibble wrote:
On Fri, 6 May 2022 15:53:58 -0500
olcott <polcott2@gmail.com> 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
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 297 |
Nodes: | 16 (0 / 16) |
Uptime: | 119:43:41 |
Calls: | 6,662 |
Files: | 12,210 |
Messages: | 5,334,369 |