Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

It's hard to tune heavily tuned code. :-) -- Larry Wall in <199801141725.JAA07555@wall.org>


computers / comp.ai.philosophy / Re: Validating that the implementation meets the spec for TM transition function

SubjectAuthor
* Validating that the implementation meets the spec for TM transitionolcott
`- Re: Validating that the implementation meets the spec for TMolcott

1
Subject: Validating that the implementation meets the spec for TM transition function
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic
Followup: comp.theory
Organization: A noiseless patient Spider
Date: Fri, 6 May 2022 20:53 UTC
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic
Subject: Validating that the implementation meets the spec for TM transition
function
Followup-To: comp.theory
Date: Fri, 6 May 2022 15:53:58 -0500
Organization: A noiseless patient Spider
Lines: 63
Message-ID: <t541t8$upu$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 6 May 2022 20:54:00 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="fa499fb4eb95ee5c956e821cecab3aa5";
logging-data="31550"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX195NQbtfoADxZxkVAKXQtyD"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:kE86CkBn24S+o4QoKM915YaWYKs=
Content-Language: en-US
View all headers
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


Subject: Re: Validating that the implementation meets the spec for TM transition function
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic
Followup: comp.theory
Organization: A noiseless patient Spider
Date: Fri, 6 May 2022 22:08 UTC
References: 1 2 3 4
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Followup-To: comp.theory
Date: Fri, 6 May 2022 17:08:40 -0500
Organization: A noiseless patient Spider
Lines: 144
Message-ID: <t5469b$115$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<20220506222911.00000dd9@reddwarf.jmc>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 6 May 2022 22:08:43 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="fff6fcee31b0b14fc946e2a4134b630e";
logging-data="1061"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18V7jWrFGTz9DRJ8JOhXPxC"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:LV+Y3Jj0dIaX0dFQUkpGrcnf76M=
In-Reply-To: <20220506222911.00000dd9@reddwarf.jmc>
Content-Language: en-US
View all headers
On 5/6/2022 4:29 PM, Mr Flibble wrote:
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


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


1
rocksolid light 0.7.2
clearneti2ptor