Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"And remember: Evil will always prevail, because Good is dumb." -- Spaceballs


devel / comp.theory / Re: Validating that the implementation meets the spec for TM transition function

SubjectAuthor
* Validating that the implementation meets the spec for TM transitionolcott
+* Validating that the implementation meets the spec for TMMr Flibble
|`* Validating that the implementation meets the spec for TMolcott
| +* Validating that the implementation meets the spec for TM transition functionMr Flibble
| |`* Validating that the implementation meets the spec for TMolcott
| | `- Validating that the implementation meets the spec for TMMr Flibble
| `* Validating that the implementation meets the spec for TMMalcolm McLean
|  +* Validating that the implementation meets the spec for TMolcott
|  |+* Validating that the implementation meets the spec for TMMalcolm McLean
|  ||`- Validating that the implementation meets the spec for TMolcott
|  |+* Validating that the implementation meets the spec for TMMike Terry
|  ||`- Validating that the implementation meets the spec for TMolcott
|  |`* Validating that the implementation meets the spec for TM transition functionBen
|  | `* Validating that the implementation meets the spec for TMolcott
|  |  `* Validating that the implementation meets the spec for TM transition functionBen
|  |   +* Validating that the implementation meets the spec for TMJeff Barnett
|  |   |+* Validating that the implementation meets the spec for TM transition functionRichard Damon
|  |   ||`* Validating that the implementation meets the spec for TMMalcolm McLean
|  |   || +- Validating that the implementation meets the spec for TMRichard Damon
|  |   || `* Validating that the implementation meets the spec for TM transition functionBen
|  |   ||  `* Validating that the implementation meets the spec for TM transition functionBen
|  |   ||   `* Validating that the implementation meets the spec for TMolcott
|  |   ||    `- Validating that the implementation meets the spec for TM transition functionBen
|  |   |`* Validating that the implementation meets the spec for TM transition functionBen
|  |   | `* Validating that the implementation meets the spec for TMJeff Barnett
|  |   |  `* Validating that the implementation meets the spec for TM transition functionBen
|  |   |   +* Validating that the implementation meets the spec for TM transition functionRichard Damon
|  |   |   |+* Validating that the implementation meets the spec for TM transition functionMr Flibble
|  |   |   ||`* Validating that the implementation meets the spec for TMolcott
|  |   |   || `* Validating that the implementation meets the spec for TM transition functionBen
|  |   |   ||  `* Validating that the implementation meets the spec for TMolcott
|  |   |   ||   +- Validating that the implementation meets the spec for TMRichard Damon
|  |   |   ||   `* Validating that the implementation meets the spec for TM transition functionBen
|  |   |   ||    +* Validating that the implementation meets the spec for TMolcott
|  |   |   ||    |`- Validating that the implementation meets the spec for TM transition functionBen
|  |   |   ||    `- Validating that the implementation meets the spec for TMolcott
|  |   |   |`- Validating that the implementation meets the spec for TMJeff Barnett
|  |   |   `* Validating that the implementation meets the spec for TMolcott
|  |   |    `* Validating that the implementation meets the spec for TM transition functionBen
|  |   |     `* Validating that the implementation meets the spec for TMolcott
|  |   |      `* Validating that the implementation meets the spec for TM transition functionBen
|  |   |       `* Validating that the implementation meets the spec for TMolcott
|  |   |        +* Validating that the implementation meets the spec for TM transition functionRichard Damon
|  |   |        |`- Validating that the implementation meets the spec for TMMalcolm McLean
|  |   |        `* Validating that the implementation meets the spec for TM transition functionBen
|  |   |         `* Validating that the implementation meets the spec for TMMalcolm McLean
|  |   |          +* Validating that the implementation meets the spec for TM transition functionBen
|  |   |          |`* Validating that the implementation meets the spec for TMolcott
|  |   |          | +- Validating that the implementation meets the spec for TMRichard Damon
|  |   |          | `* Validating that the implementation meets the spec for TM transition functionBen
|  |   |          |  +* Validating that the implementation meets the spec for TMJeff Barnett
|  |   |          |  |`* Validating that the implementation meets the spec for TMolcott
|  |   |          |  | `- Validating that the implementation meets the spec for TMJeff Barnett
|  |   |          |  `* Validating that the implementation meets the spec for TM transition functionMr Flibble
|  |   |          |   +* Validating that the implementation meets the spec for TMdklei...@gmail.com
|  |   |          |   |+* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||`* Validating that the implementation meets the spec for TM transition functionBen
|  |   |          |   || `* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||  +* Validating that the implementation meets the spec for TMMike Terry
|  |   |          |   ||  |+- Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||  |`* Validating that the implementation meets the spec for TMMalcolm McLean
|  |   |          |   ||  | +- Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||  | `* Validating that the implementation meets the spec for TMMike Terry
|  |   |          |   ||  |  +* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||  |  |`- Validating that the implementation meets the spec for TMMike Terry
|  |   |          |   ||  |  `* Validating that the implementation meets the spec for TMMalcolm McLean
|  |   |          |   ||  |   +- Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||  |   +* Validating that the implementation meets the spec for TMMike Terry
|  |   |          |   ||  |   |`* Validating that the implementation meets the spec for TM transition function [ bolcott
|  |   |          |   ||  |   | `* Validating that the implementation meets the spec for TMMike Terry
|  |   |          |   ||  |   |  +- Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||  |   |  +- Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||  |   |  `* Validating that the implementation meets the spec for TM transition function [ bBen
|  |   |          |   ||  |   |   `* Validating that the implementation meets the spec for TMMike Terry
|  |   |          |   ||  |   |    `* Validating that the implementation meets the spec for TM transition function [ bBen
|  |   |          |   ||  |   |     +- Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||  |   |     +- Validating that the implementation meets the spec for TMRichard Damon
|  |   |          |   ||  |   |     `- Validating that the implementation meets the spec for TMMike Terry
|  |   |          |   ||  |   `* Validating that the implementation meets the spec for TMJeff Barnett
|  |   |          |   ||  |    `- Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||  `* Validating that the implementation meets the spec for TM transition function [ bBen
|  |   |          |   ||   +* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||   |`- Validating that the implementation meets the spec for TM transition function [ bBen
|  |   |          |   ||   `* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||    +* Validating that the implementation meets the spec for TMMike Terry
|  |   |          |   ||    |`- Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||    `* Validating that the implementation meets the spec for TM transition function [ bBen
|  |   |          |   ||     `* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||      `* Validating that the implementation meets the spec for TM transition function [ bBen
|  |   |          |   ||       `* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||        `* Validating that the implementation meets the spec for TM transition function [ bBen
|  |   |          |   ||         `* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||          +* Validating that the implementation meets the spec for TM transition function [ bBen
|  |   |          |   ||          |`* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||          | `* Validating that the implementation meets the spec for TM transition function [ bBen
|  |   |          |   ||          |  `* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||          |   `* Validating that the implementation meets the spec for TM transition function [ bBen
|  |   |          |   ||          |    `* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||          |     +* Validating that the implementation meets the spec for TMMr Flibble
|  |   |          |   ||          |     |`* Validating that the implementation meets the spec for TMolcott
|  |   |          |   ||          |     | `- Validating that the implementation meets the spec for TMMr Flibble
|  |   |          |   ||          |     `* Validating that the implementation meets the spec for TM transition function [ bBen
|  |   |          |   ||          `- Validating that the implementation meets the spec for TMRichard Damon
|  |   |          |   |`- Validating that the implementation meets the spec for TMolcott
|  |   |          |   +- Validating that the implementation meets the spec for TM transition functionBen
|  |   |          |   `- Validating that the implementation meets the spec for TMolcott
|  |   |          `- Validating that the implementation meets the spec for TMolcott
|  |   `* Validating that the implementation meets the spec for TMolcott
|  `* Validating that the implementation meets the spec for TM transition functionBen
`* Validating that the implementation meets the spec for TM transition functionMikko

Pages:12345678
Validating that the implementation meets the spec for TM transition function

<t541t8$upu$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31805&group=comp.theory#31805

 copy link   Newsgroups: comp.theory comp.ai.philosophy sci.logic
Followup: comp.theory
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
 by: olcott - Fri, 6 May 2022 20:53 UTC

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

Re: Validating that the implementation meets the spec for TM transition function

<20220506220822.000061d0@reddwarf.jmc>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31807&group=comp.theory#31807

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!news.uzoreto.com!feeder1.feed.usenet.farm!feed.usenet.farm!news-out.netnews.com!news.alt.net!fdc2.netnews.com!peer03.ams1!peer.ams1.xlned.com!news.xlned.com!peer03.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx12.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Message-ID: <20220506220822.000061d0@reddwarf.jmc>
References: <t541t8$upu$1@dont-email.me>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Lines: 71
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 06 May 2022 21:08:21 UTC
Date: Fri, 6 May 2022 22:08:22 +0100
X-Received-Bytes: 3328
 by: Mr Flibble - Fri, 6 May 2022 21:08 UTC

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
very least created named typedefs for things rather than the anonymous
'u32' etc.

/Flibble

Re: Validating that the implementation meets the spec for TM transition function

<t543p9$d1h$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31808&group=comp.theory#31808

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Fri, 6 May 2022 16:25:58 -0500
Organization: A noiseless patient Spider
Lines: 84
Message-ID: <t543p9$d1h$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@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 21:26:01 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="fa499fb4eb95ee5c956e821cecab3aa5";
logging-data="13361"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18NiWLdO7WhTy5N9wsiz+b9"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:6FODVU3bmrYcJxMFJXRXqw45Zhg=
In-Reply-To: <20220506220822.000061d0@reddwarf.jmc>
Content-Language: en-US
 by: olcott - Fri, 6 May 2022 21:25 UTC

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.

> very least created named typedefs for things rather than the anonymous
> 'u32' etc.
>
> /Flibble
>
>

It is all in a pair of C++ classes, I didn't want to show all of the
pages, (1) They are not done yet (2) The distract attention way from the
only function that I need reviewed.

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

Re: Validating that the implementation meets the spec for TM transition function

<20220506222911.00000dd9@reddwarf.jmc>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31809&group=comp.theory#31809

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!feeder.usenetexpress.com!tr2.eu1.usenetexpress.com!81.171.65.13.MISMATCH!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx12.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function
Message-ID: <20220506222911.00000dd9@reddwarf.jmc>
References: <t541t8$upu$1@dont-email.me> <20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Lines: 83
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 06 May 2022 21:29:10 UTC
Date: Fri, 6 May 2022 22:29:11 +0100
X-Received-Bytes: 3951
 by: Mr Flibble - Fri, 6 May 2022 21:29 UTC

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

Re: Validating that the implementation meets the spec for TM transition function

<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31811&group=comp.theory#31811

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:6214:400e:b0:45a:ebbc:73 with SMTP id kd14-20020a056214400e00b0045aebbc0073mr3041829qvb.7.1651873314609;
Fri, 06 May 2022 14:41:54 -0700 (PDT)
X-Received: by 2002:a0d:cb41:0:b0:2f7:d205:9c99 with SMTP id
n62-20020a0dcb41000000b002f7d2059c99mr4509309ywd.417.1651873314367; Fri, 06
May 2022 14:41:54 -0700 (PDT)
Path: i2pn2.org!i2pn.org!aioe.org!news.mixmin.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Fri, 6 May 2022 14:41:54 -0700 (PDT)
In-Reply-To: <t543p9$d1h$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:481f:a8e3:8e9d:cc1c;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:481f:a8e3:8e9d:cc1c
References: <t541t8$upu$1@dont-email.me> <20220506220822.000061d0@reddwarf.jmc>
<t543p9$d1h$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
Subject: Re: Validating that the implementation meets the spec for TM
transition function
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Fri, 06 May 2022 21:41:54 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
 by: Malcolm McLean - Fri, 6 May 2022 21:41 UTC

On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
> On 5/6/2022 4:08 PM, Mr Flibble wrote:
> > On Fri, 6 May 2022 15:53:58 -0500
> > olcott <polc...@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.
> > very least created named typedefs for things rather than the anonymous
> > 'u32' etc.
> >
> > /Flibble
> >
> >
> It is all in a pair of C++ classes, I didn't want to show all of the
> pages, (1) They are not done yet (2) The distract attention way from the
> only function that I need reviewed.
>
ThIs looks along the right lines.
The quintuples need to be indexed by the current state and the current input,
and a set, properly specified, will achieve this.
You can probably get away with chars for the symbols. Few people work with Turing
machines with a large number of symbols.
Since the tape cannot in reality be infinite, you might consider throwing an exception
when it goes out of bounds.
I'd rename "Quintuple_List", "TuringMachine". Of course in your system, a Turing
machine is a quintuple list, so it's moot which name is better. But if you make the
list private, you can shift to another representation whilst keeping the interfaces the
same.

Re: Validating that the implementation meets the spec for TM transition function

<t545tm$u69$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31813&group=comp.theory#31813

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Fri, 6 May 2022 17:02:27 -0500
Organization: A noiseless patient Spider
Lines: 113
Message-ID: <t545tm$u69$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 6 May 2022 22:02:30 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="fff6fcee31b0b14fc946e2a4134b630e";
logging-data="30921"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/4ilEUnCZfANPHN7tw2U4t"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:lT5KOtR2TshMaGJr3ZSsCq61Cpw=
In-Reply-To: <0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
Content-Language: en-US
 by: olcott - Fri, 6 May 2022 22:02 UTC

On 5/6/2022 4:41 PM, Malcolm McLean wrote:
> On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
>> On 5/6/2022 4:08 PM, Mr Flibble wrote:
>>> On Fri, 6 May 2022 15:53:58 -0500
>>> olcott <polc...@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.
>>> very least created named typedefs for things rather than the anonymous
>>> 'u32' etc.
>>>
>>> /Flibble
>>>
>>>
>> It is all in a pair of C++ classes, I didn't want to show all of the
>> pages, (1) They are not done yet (2) The distract attention way from the
>> only function that I need reviewed.
>>
> ThIs looks along the right lines.
> The quintuples need to be indexed by the current state and the current input,
> and a set, properly specified, will achieve this.

Ben didn't seem to understand this.

> You can probably get away with chars for the symbols. Few people work with Turing
> machines with a large number of symbols.

My initial vision was to use unsigned 8-bit integers and let the data be
quintuples be defined by ASCII chars, as it is in my model system.
All this cane be defined on the parse side, leaving int as the
underlying size.

> Since the tape cannot in reality be infinite, you might consider throwing an exception
> when it goes out of bounds.

Or put it in a std::vector and grow it as needed.
I think that the conventional TM has a tape with a beginning, thus a
tape_head move to before the beginning would be an error.

> I'd rename "Quintuple_List", "TuringMachine". Of course in your system, a Turing
> machine is a quintuple list, so it's moot which name is better. But if you make the
> list private, you can shift to another representation whilst keeping the interfaces the
> same.
>

I thought that States was a fine name.

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

Re: Validating that the implementation meets the spec for TM transition function

<t5469b$115$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31814&group=comp.theory#31814

 copy link   Newsgroups: comp.theory comp.ai.philosophy sci.logic
Followup: comp.theory
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
 by: olcott - Fri, 6 May 2022 22:08 UTC

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

Re: Validating that the implementation meets the spec for TM transition function

<bdfe868a-80d1-4eaf-a86a-f5bd25e2d842n@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31815&group=comp.theory#31815

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:622a:18a:b0:2f3:bdc9:31f4 with SMTP id s10-20020a05622a018a00b002f3bdc931f4mr4978421qtw.285.1651876612108;
Fri, 06 May 2022 15:36:52 -0700 (PDT)
X-Received: by 2002:a81:ff06:0:b0:2e6:d7bc:c812 with SMTP id
k6-20020a81ff06000000b002e6d7bcc812mr4616837ywn.122.1651876611885; Fri, 06
May 2022 15:36:51 -0700 (PDT)
Path: i2pn2.org!i2pn.org!aioe.org!news.mixmin.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Fri, 6 May 2022 15:36:51 -0700 (PDT)
In-Reply-To: <t545tm$u69$1@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:f948:36d3:8baf:f428;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:f948:36d3:8baf:f428
References: <t541t8$upu$1@dont-email.me> <20220506220822.000061d0@reddwarf.jmc>
<t543p9$d1h$1@dont-email.me> <0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <bdfe868a-80d1-4eaf-a86a-f5bd25e2d842n@googlegroups.com>
Subject: Re: Validating that the implementation meets the spec for TM
transition function
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Fri, 06 May 2022 22:36:52 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
 by: Malcolm McLean - Fri, 6 May 2022 22:36 UTC

On Friday, 6 May 2022 at 23:02:33 UTC+1, olcott wrote:
> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
> > On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
> >> On 5/6/2022 4:08 PM, Mr Flibble wrote:
> >>> On Fri, 6 May 2022 15:53:58 -0500
> >>> olcott <polc...@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.
> >>> very least created named typedefs for things rather than the anonymous
> >>> 'u32' etc.
> >>>
> >>> /Flibble
> >>>
> >>>
> >> It is all in a pair of C++ classes, I didn't want to show all of the
> >> pages, (1) They are not done yet (2) The distract attention way from the
> >> only function that I need reviewed.
> >>
> > ThIs looks along the right lines.
> > The quintuples need to be indexed by the current state and the current input,
> > and a set, properly specified, will achieve this.
> Ben didn't seem to understand this.
> > You can probably get away with chars for the symbols. Few people work with Turing
> > machines with a large number of symbols.
> My initial vision was to use unsigned 8-bit integers and let the data be
> quintuples be defined by ASCII chars, as it is in my model system.
> All this cane be defined on the parse side, leaving int as the
> underlying size.
>
If you use chars for the symbols, you can make the tape human-readable. Which
might help.
But as you say, you can manipulate the symbols internally as 32 bit integers if
you want, even if in reality they are constrained to take the values "1", "0" and
"blank".

Re: Validating that the implementation meets the spec for TM transition function

<t548uc$hh4$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31816&group=comp.theory#31816

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Fri, 6 May 2022 17:54:01 -0500
Organization: A noiseless patient Spider
Lines: 108
Message-ID: <t548uc$hh4$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me>
<bdfe868a-80d1-4eaf-a86a-f5bd25e2d842n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 6 May 2022 22:54:04 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="fff6fcee31b0b14fc946e2a4134b630e";
logging-data="17956"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/UpOhAvOzBtSJrrPTQpvXf"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:O/dVtEQDuW5RAt3Zt4NT55v/X/Y=
In-Reply-To: <bdfe868a-80d1-4eaf-a86a-f5bd25e2d842n@googlegroups.com>
Content-Language: en-US
 by: olcott - Fri, 6 May 2022 22:54 UTC

On 5/6/2022 5:36 PM, Malcolm McLean wrote:
> On Friday, 6 May 2022 at 23:02:33 UTC+1, olcott wrote:
>> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
>>> On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
>>>> On 5/6/2022 4:08 PM, Mr Flibble wrote:
>>>>> On Fri, 6 May 2022 15:53:58 -0500
>>>>> olcott <polc...@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.
>>>>> very least created named typedefs for things rather than the anonymous
>>>>> 'u32' etc.
>>>>>
>>>>> /Flibble
>>>>>
>>>>>
>>>> It is all in a pair of C++ classes, I didn't want to show all of the
>>>> pages, (1) They are not done yet (2) The distract attention way from the
>>>> only function that I need reviewed.
>>>>
>>> ThIs looks along the right lines.
>>> The quintuples need to be indexed by the current state and the current input,
>>> and a set, properly specified, will achieve this.
>> Ben didn't seem to understand this.
>>> You can probably get away with chars for the symbols. Few people work with Turing
>>> machines with a large number of symbols.
>> My initial vision was to use unsigned 8-bit integers and let the data be
>> quintuples be defined by ASCII chars, as it is in my model system.
>> All this cane be defined on the parse side, leaving int as the
>> underlying size.
>>
> If you use chars for the symbols, you can make the tape human-readable. Which
> might help.
> But as you say, you can manipulate the symbols internally as 32 bit integers if
> you want, even if in reality they are constrained to take the values "1", "0" and
> "blank".
>

They are constrained to any value that unsigned int can hold.
The parse side will initially only be 7-bit ASCII to make it compatible
with the TM interpreter 7-bit TM code examples. The other {8,16,32} bit
parses will be all be in hexadecimal. (I may skip 8, and 16 bits).

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

Re: Validating that the implementation meets the spec for TM transition function

<t54bkf$g23$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31817&group=comp.theory#31817

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!CC3uK9WYEoa7s1kzH7komw.user.46.165.242.75.POSTED!not-for-mail
From: news.dea...@darjeeling.plus.com (Mike Terry)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Sat, 7 May 2022 00:39:59 +0100
Organization: Aioe.org NNTP Server
Message-ID: <t54bkf$g23$1@gioia.aioe.org>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: gioia.aioe.org; logging-data="16451"; posting-host="CC3uK9WYEoa7s1kzH7komw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.7.1
X-Notice: Filtered by postfilter v. 0.9.2
 by: Mike Terry - Fri, 6 May 2022 23:39 UTC

On 06/05/2022 23:02, olcott wrote:
> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
>> On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
>>> On 5/6/2022 4:08 PM, Mr Flibble wrote:
>>>> On Fri, 6 May 2022 15:53:58 -0500
>>>> olcott <polc...@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.
>>>> very least created named typedefs for things rather than the anonymous
>>>> 'u32' etc.
>>>>
>>>> /Flibble
>>>>
>>>>
>>> It is all in a pair of C++ classes, I didn't want to show all of the
>>> pages, (1) They are not done yet (2) The distract attention way from the
>>> only function that I need reviewed.
>>>
>> ThIs looks along the right lines.
>> The quintuples need to be indexed by the current state and the current input,
>> and a set, properly specified, will achieve this.
>
> Ben didn't seem to understand this.
>
>> You can probably get away with chars for the symbols. Few people work with Turing
>> machines with a large number of symbols.
>
> My initial vision was to use unsigned 8-bit integers and let the data be quintuples be defined by
> ASCII chars, as it is in my model system.
> All this cane be defined on the parse side, leaving int as the underlying size.
>
>> Since the tape cannot in reality be infinite, you might consider throwing an exception
>> when it goes out of bounds.
>
> Or put it in a std::vector and grow it as needed.
> I think that the conventional TM has a tape with a beginning, thus a tape_head move to before the
> beginning would be an error.
>
>> I'd rename "Quintuple_List", "TuringMachine".  Of course in your system, a Turing
>> machine is a quintuple list, so it's moot which name is better. But if you make the
>> list private, you can shift to another representation whilst keeping the interfaces the
>> same.
>>
>
> I thought that States was a fine name.

Well you must be confused by what a TM state is - the quintuples do not represent the TM states as
lots of people have said.

Look, check your favourite Linz book, figure 9.7 (in my edition; the figure for Example 9.10 "Design
a TM that copiess strings of 1's"). You see there are several CIRCLES joined by annotated ARROWS?

The TM states are THE LITTLE CIRCLES, with their state names q0, q1... written inside.

Your quintuples are the equivalent of THE *ARROWS* in the figure. So, not states at all. Someone
suggested "rules", which is what I might have chosen.

Your E TM will probably end up with around 5 circles and 6 arrows (if you go with your binary number
tape representation) so if you need an emulator to debug your E and check you've got it right that
doesn't say much for your problem solving skills! :)

Mike.

Re: Validating that the implementation meets the spec for TM transition function

<t54cfo$7gm$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31820&group=comp.theory#31820

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Fri, 6 May 2022 18:54:29 -0500
Organization: A noiseless patient Spider
Lines: 157
Message-ID: <t54cfo$7gm$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <t54bkf$g23$1@gioia.aioe.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 6 May 2022 23:54:32 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="fff6fcee31b0b14fc946e2a4134b630e";
logging-data="7702"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19da/sfhQfS/vd+Ka25Ta9z"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:Pn4PWzi40h+OL3kaWqYAOgs+VaU=
In-Reply-To: <t54bkf$g23$1@gioia.aioe.org>
Content-Language: en-US
 by: olcott - Fri, 6 May 2022 23:54 UTC

On 5/6/2022 6:39 PM, Mike Terry wrote:
> On 06/05/2022 23:02, olcott wrote:
>> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
>>> On Friday, 6 May 2022 at 22:26:03 UTC+1, olcott wrote:
>>>> On 5/6/2022 4:08 PM, Mr Flibble wrote:
>>>>> On Fri, 6 May 2022 15:53:58 -0500
>>>>> olcott <polc...@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.
>>>>> very least created named typedefs for things rather than the anonymous
>>>>> 'u32' etc.
>>>>>
>>>>> /Flibble
>>>>>
>>>>>
>>>> It is all in a pair of C++ classes, I didn't want to show all of the
>>>> pages, (1) They are not done yet (2) The distract attention way from
>>>> the
>>>> only function that I need reviewed.
>>>>
>>> ThIs looks along the right lines.
>>> The quintuples need to be indexed by the current state and the
>>> current input,
>>> and a set, properly specified, will achieve this.
>>
>> Ben didn't seem to understand this.
>>
>>> You can probably get away with chars for the symbols. Few people work
>>> with Turing
>>> machines with a large number of symbols.
>>
>> My initial vision was to use unsigned 8-bit integers and let the data
>> be quintuples be defined by ASCII chars, as it is in my model system.
>> All this cane be defined on the parse side, leaving int as the
>> underlying size.
>>
>>> Since the tape cannot in reality be infinite, you might consider
>>> throwing an exception
>>> when it goes out of bounds.
>>
>> Or put it in a std::vector and grow it as needed.
>> I think that the conventional TM has a tape with a beginning, thus a
>> tape_head move to before the beginning would be an error.
>>
>>> I'd rename "Quintuple_List", "TuringMachine".  Of course in your
>>> system, a Turing
>>> machine is a quintuple list, so it's moot which name is better. But
>>> if you make the
>>> list private, you can shift to another representation whilst keeping
>>> the interfaces the
>>> same.
>>>
>>
>> I thought that States was a fine name.
>
> Well you must be confused by what a TM state is - the quintuples do not
> represent the TM states as lots of people have said.
>
> Look, check your favourite Linz book, figure 9.7 (in my edition; the
> figure for Example 9.10 "Design a TM that copiess strings of 1's").  You
> see there are several CIRCLES joined by annotated ARROWS?
>
> The TM states are THE LITTLE CIRCLES, with their state names q0, q1...
> written inside.
>

AKA directed graphs the abstract away key details of the actions
required by a state transitions. We can ignore these actions when we are
presenting a high level overview in directed graphs. The actual state
transitions require these actions and can't possibly work correctly
without them.

> Your quintuples are the equivalent of THE *ARROWS* in the figure.  So,
> not states at all.  Someone suggested "rules", which is what I might
> have chosen.
>

OK that makes perfect sense.

> Your E TM will probably end up with around 5 circles and 6 arrows (if
> you go with your binary number tape representation) so if you need an
> emulator to debug your E and check you've got it right that doesn't say
> much for your problem solving skills!  :)
>
> Mike.

So you didn't find any errors in my transition_function?
I got all the code to compile now. I can adapt the TM interpreter
examples: http://www.lns.mit.edu/~dsw/turing/examples/examples.html

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

Re: Validating that the implementation meets the spec for TM transition function

<87sfpmyywj.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31824&group=comp.theory#31824

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function
Date: Sat, 07 May 2022 01:22:36 +0100
Organization: A noiseless patient Spider
Lines: 18
Message-ID: <87sfpmyywj.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="75b342e6311f1aa208c9f5345542552f";
logging-data="32518"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18xrB0suCS3eeuCkFTx2guIkAypueB5/z0="
Cancel-Lock: sha1:PWbWAXq73QcPvkwyJGNZnS6Hk/U=
sha1:JtrwlhEqMCzO/rQAoTTAdbrUaFY=
X-BSB-Auth: 1.ab9b19ba938521bf655c.20220507012236BST.87sfpmyywj.fsf@bsb.me.uk
 by: Ben - Sat, 7 May 2022 00:22 UTC

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> ThIs looks along the right lines.
> The quintuples need to be indexed by the current state and the current
> input, and a set, properly specified, will achieve this.

How? std::set is not the right container for this.

> You can probably get away with chars for the symbols. Few people work
> with Turing machines with a large number of symbols.

ACK. It's painful to write TMs with more than even a handful of
distinct symbols. There may be some value in using something like
wchar_t so that fancy symbols matching those seen in some of the papers
can be used, but that's a bit of a stretch.

--
Ben.

Re: Validating that the implementation meets the spec for TM transition function

<t54f2k$mqp$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31826&group=comp.theory#31826

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Fri, 6 May 2022 19:38:41 -0500
Organization: A noiseless patient Spider
Lines: 43
Message-ID: <t54f2k$mqp$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<87sfpmyywj.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 7 May 2022 00:38:44 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="fff6fcee31b0b14fc946e2a4134b630e";
logging-data="23385"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX199lDCCfrclNrU03KN7jrHe"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:W8ZVbGLH4tEbRRICbG+7u6+l8o0=
In-Reply-To: <87sfpmyywj.fsf@bsb.me.uk>
Content-Language: en-US
 by: olcott - Sat, 7 May 2022 00:38 UTC

On 5/6/2022 7:22 PM, Ben wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> ThIs looks along the right lines.
>> The quintuples need to be indexed by the current state and the current
>> input, and a set, properly specified, will achieve this.
>
> How? std::set is not the right container for this.

std::set::find()

std::set<Quintuple> States;
std::vector<unsigned char> Tape;
void insert(const Quintuple& QT){ States.insert(QT); };

std::set<Quintuple>::iterator
NextState(int current_input, int next_state)
{
Quintuple QT(current_input, next_state);
return States.find(QT);
}

>
>> You can probably get away with chars for the symbols. Few people work
>> with Turing machines with a large number of symbols.
>

The TM interpreter uses ASCII text as its tape elements.
For compatibility I will do the same, that way I can directly execute
all of his same filename.tm examples.

> ACK. It's painful to write TMs with more than even a handful of
> distinct symbols. There may be some value in using something like
> wchar_t so that fancy symbols matching those seen in some of the papers
> can be used, but that's a bit of a stretch.
>

One need to use more than one or two {'0', '1'} of the possible tape
elements.

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

Re: Validating that the implementation meets the spec for TM transition function

<87h762yxg6.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31827&group=comp.theory#31827

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function
Date: Sat, 07 May 2022 01:54:01 +0100
Organization: A noiseless patient Spider
Lines: 38
Message-ID: <87h762yxg6.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="75b342e6311f1aa208c9f5345542552f";
logging-data="28721"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19MdXmm2AtIM8Bc1zSHjscgEk5oasK9+hY="
Cancel-Lock: sha1:lOFYKSQDlUsnI2CIJxJgqcdY7lk=
sha1:VfAN5926Istj3ys+MKWi2w+beH0=
X-BSB-Auth: 1.c85f409f527f87edcf20.20220507015401BST.87h762yxg6.fsf@bsb.me.uk
 by: Ben - Sat, 7 May 2022 00:54 UTC

olcott <polcott2@gmail.com> writes:

> On 5/6/2022 4:41 PM, Malcolm McLean wrote:

>>>> olcott <polc...@gmail.com> wrote:

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

>> ThIs looks along the right lines.
>> The quintuples need to be indexed by the current state and the current input,
>> and a set, properly specified, will achieve this.
>
> Ben didn't seem to understand this.

Your code sketch just won't work as you have it now. Do you know how to
get it to work? The result will not be a natural use of a set.

--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

Re: Validating that the implementation meets the spec for TM transition function

<878rreyx3c.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31828&group=comp.theory#31828

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function
Date: Sat, 07 May 2022 02:01:43 +0100
Organization: A noiseless patient Spider
Lines: 36
Message-ID: <878rreyx3c.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<87sfpmyywj.fsf@bsb.me.uk> <t54f2k$mqp$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="75b342e6311f1aa208c9f5345542552f";
logging-data="28721"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19FYA2z4c75iR6PlqOiWpNi5ospReSG2mI="
Cancel-Lock: sha1:kU5fZ5m3lZxnY2Pz5L6O8Wr0whA=
sha1:KQft2tMddtLgae6TyfMoaZz/+gk=
X-BSB-Auth: 1.f732eae8b7f2455e5bf5.20220507020143BST.878rreyx3c.fsf@bsb.me.uk
 by: Ben - Sat, 7 May 2022 01:01 UTC

olcott <polcott2@gmail.com> writes:

> On 5/6/2022 7:22 PM, Ben wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> ThIs looks along the right lines.
>>> The quintuples need to be indexed by the current state and the current
>>> input, and a set, properly specified, will achieve this.
>> How? std::set is not the right container for this.
>
> std::set::find()
>
> std::set<Quintuple> States;
> std::vector<unsigned char> Tape;
> void insert(const Quintuple& QT){ States.insert(QT); };
>
> std::set<Quintuple>::iterator
> NextState(int current_input, int next_state)
> {
> Quintuple QT(current_input, next_state);
> return States.find(QT);
> }

No, this won't work. You can /make/ it work, but to do that you have to
play tricks with what's considered to be unique in the set. I think a
std::map is more natural.

And your names appear messed up again. NextState (with no declared
return type) returns a Quintuple, not a state. And it has "next_state"
as an argument which seems unlikely. Surely NextState needs the current
state and input symbol?

--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

Re: Validating that the implementation meets the spec for TM transition function

<8735hmywyf.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31829&group=comp.theory#31829

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function
Date: Sat, 07 May 2022 02:04:40 +0100
Organization: A noiseless patient Spider
Lines: 15
Message-ID: <8735hmywyf.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<87sfpmyywj.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="75b342e6311f1aa208c9f5345542552f";
logging-data="28721"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18qdULHu94pobG4hGt9l0ceAoFzMVRKkOM="
Cancel-Lock: sha1:OVgIHlGHDWNdMjKZ7FBQygc45ow=
sha1:BNgAgs3tQJOmC2aLSbBdRExdu2k=
X-BSB-Auth: 1.10e6d86d1e68c2ecd292.20220507020440BST.8735hmywyf.fsf@bsb.me.uk
 by: Ben - Sat, 7 May 2022 01:04 UTC

Ben <ben.usenet@bsb.me.uk> writes:

> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> ThIs looks along the right lines.
>> The quintuples need to be indexed by the current state and the current
>> input, and a set, properly specified, will achieve this.
>
> How? std::set is not the right container for this.

I can answer the how myself now, but I still don't think std::set is the
right choice as the reader is likely yo be confused by the look-up.

--
Ben.

Re: Validating that the implementation meets the spec for TM transition function

<t54gl1$cp$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31830&group=comp.theory#31830

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Fri, 6 May 2022 20:05:35 -0500
Organization: A noiseless patient Spider
Lines: 73
Message-ID: <t54gl1$cp$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 7 May 2022 01:05:38 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="fff6fcee31b0b14fc946e2a4134b630e";
logging-data="409"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19IUGfpA+ylYbVXzpfwu7pP"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:8wxmuIQfrHUB89YRJGi8kfFQNr4=
In-Reply-To: <87h762yxg6.fsf@bsb.me.uk>
Content-Language: en-US
 by: olcott - Sat, 7 May 2022 01:05 UTC

On 5/6/2022 7:54 PM, Ben wrote:
> olcott <polcott2@gmail.com> writes:
>
>> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
>
>>>>> olcott <polc...@gmail.com> wrote:
>
>>>>>> 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);
>>>>>> };
>>>>>> }
>
>>> ThIs looks along the right lines.
>>> The quintuples need to be indexed by the current state and the current input,
>>> and a set, properly specified, will achieve this.
>>
>> Ben didn't seem to understand this.
>
> Your code sketch just won't work as you have it now.

Not when you erase the most important part:

bool Quintuple_List::transition_function(std::set<Quintuple>::iterator&
current_quintuple)
{ unsigned int next_state = current_quintuple->next_state;
unsigned int 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 == States.end())
return false;
current_quintuple = next_quintuple;
return true;
}

If you also assume that I got All the missing pieces correctly then it
should work just fine.

> Do you know how to
> get it to work? The result will not be a natural use of a set.
>

The natural use of a std::set it to look things up very quickly with no
need for a linear search.

I decided to make my system exactly compatible with these code samples:
http://www.lns.mit.edu/~dsw/turing/examples/examples.html

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

Re: Validating that the implementation meets the spec for TM transition function

<t54hl6$67o$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31832&group=comp.theory#31832

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Fri, 6 May 2022 20:22:44 -0500
Organization: A noiseless patient Spider
Lines: 50
Message-ID: <t54hl6$67o$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<87sfpmyywj.fsf@bsb.me.uk> <t54f2k$mqp$1@dont-email.me>
<878rreyx3c.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 7 May 2022 01:22:47 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="fff6fcee31b0b14fc946e2a4134b630e";
logging-data="6392"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/CTZDnt3VqEVdS1kND5L46"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:/kgbga8geyGvHIoTA/xVfJ3Ais8=
In-Reply-To: <878rreyx3c.fsf@bsb.me.uk>
Content-Language: en-US
 by: olcott - Sat, 7 May 2022 01:22 UTC

On 5/6/2022 8:01 PM, Ben wrote:
> olcott <polcott2@gmail.com> writes:
>
>> On 5/6/2022 7:22 PM, Ben wrote:
>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>
>>>> ThIs looks along the right lines.
>>>> The quintuples need to be indexed by the current state and the current
>>>> input, and a set, properly specified, will achieve this.
>>> How? std::set is not the right container for this.
>>
>> std::set::find()
>>
>> std::set<Quintuple> States;
>> std::vector<unsigned char> Tape;
>> void insert(const Quintuple& QT){ States.insert(QT); };
>>
>> std::set<Quintuple>::iterator
>> NextState(int current_input, int next_state)
>> {
>> Quintuple QT(current_input, next_state);
>> return States.find(QT);
>> }
>
> No, this won't work. You can /make/ it work, but to do that you have to
> play tricks with what's considered to be unique in the set. I think a
> std::map is more natural.
>

I got dem tricks...
std::map has redundant data or splits the class data into two pieces.

> And your names appear messed up again. NextState (with no declared

It has a declared return type that doesn't fit well on the same line:
std::set<Quintuple>::iterator

> return type) returns a Quintuple, not a state. And it has "next_state"
> as an argument which seems unlikely. Surely NextState needs the current
> state and input symbol?
>

You missed this?
>> NextState(int current_input, int next_state)

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

Re: Validating that the implementation meets the spec for TM transition function

<t54hrr$7co$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31833&group=comp.theory#31833

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Fri, 6 May 2022 20:26:16 -0500
Organization: A noiseless patient Spider
Lines: 22
Message-ID: <t54hrr$7co$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<87sfpmyywj.fsf@bsb.me.uk> <8735hmywyf.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 7 May 2022 01:26:19 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="fff6fcee31b0b14fc946e2a4134b630e";
logging-data="7576"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/U9zKVOAaiWfVdjJCJm5tN"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:OXLbI2Lrptys3SO+247379PjEH0=
In-Reply-To: <8735hmywyf.fsf@bsb.me.uk>
Content-Language: en-US
 by: olcott - Sat, 7 May 2022 01:26 UTC

On 5/6/2022 8:04 PM, Ben wrote:
> Ben <ben.usenet@bsb.me.uk> writes:
>
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> ThIs looks along the right lines.
>>> The quintuples need to be indexed by the current state and the current
>>> input, and a set, properly specified, will achieve this.
>>
>> How? std::set is not the right container for this.
>
> I can answer the how myself now, but I still don't think std::set is the
> right choice as the reader is likely yo be confused by the look-up.
>

I have done this for may years with std::map. std::set is the same yet
one must overload: bool Quintuple::operator<(const Quintuple& QT) const

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

Re: Validating that the implementation meets the spec for TM transition function

<t559aq$jj2$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31843&group=comp.theory#31843

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: mikko.le...@iki.fi (Mikko)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function
Date: Sat, 7 May 2022 11:06:50 +0300
Organization: -
Lines: 73
Message-ID: <t559aq$jj2$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="dd0c1a9e1b86af1b8ef0ec9ee5f52432";
logging-data="20066"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/QLSoy0tdm5r9F2pL/IREY"
User-Agent: Unison/2.2
Cancel-Lock: sha1:yrmSeU3rctCVJ3lyDUWHz1Y5m00=
 by: Mikko - Sat, 7 May 2022 08:06 UTC

On 2022-05-06 20:53:58 +0000, olcott said:

> 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'.

The new state is irrelevant until (b) and (c) are performed, so
the action (a) should be last in the list.

> struct Quintuple
> {
> u32 state;
> u32 symbol;
> u32 write_symbol;
> u32 next_state;
> u8 Tape_Head_Move;
> };

If you want to print traces of the execution it is better to
give the type char* to state and next_state. As the only operations
with these values are assignment and equality test, char* is
as good as u32. But char* gives better trace if it points to the
name of the state as it is in the definition of the Turing machine.

Although not relevant to the current question, I still recommend
that Quintuple be renamed to Rule and Quintuple_List be renamed
to Rules.

> class Quintuple_List
> {
> std::set<Quintuple> list;
> NextState(int next_state, int current_input)

This function should be named getRule. Function names shoule start with
a lower case letter.

> {
> 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”;

Instead of using toupper here you should ensure that only upper case
letters 'L' and 'R' are ever stored in any tape_head_move.

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

Mikko

Re: Validating that the implementation meets the spec for TM transition function

<9f101e19-e941-45da-abf4-8a63b362347an@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31846&group=comp.theory#31846

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:622a:40e:b0:2f3:bad4:ae29 with SMTP id n14-20020a05622a040e00b002f3bad4ae29mr6790526qtx.557.1651924855988;
Sat, 07 May 2022 05:00:55 -0700 (PDT)
X-Received: by 2002:a81:ff06:0:b0:2e6:d7bc:c812 with SMTP id
k6-20020a81ff06000000b002e6d7bcc812mr6398760ywn.122.1651924855786; Sat, 07
May 2022 05:00:55 -0700 (PDT)
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!npeer.as286.net!npeer-ng0.as286.net!peer03.ams1!peer.ams1.xlned.com!news.xlned.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Sat, 7 May 2022 05:00:55 -0700 (PDT)
In-Reply-To: <8735hmywyf.fsf@bsb.me.uk>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:908b:1acb:c8dd:6ff;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:908b:1acb:c8dd:6ff
References: <t541t8$upu$1@dont-email.me> <20220506220822.000061d0@reddwarf.jmc>
<t543p9$d1h$1@dont-email.me> <0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<87sfpmyywj.fsf@bsb.me.uk> <8735hmywyf.fsf@bsb.me.uk>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <9f101e19-e941-45da-abf4-8a63b362347an@googlegroups.com>
Subject: Re: Validating that the implementation meets the spec for TM
transition function
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Sat, 07 May 2022 12:00:55 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2111
 by: Malcolm McLean - Sat, 7 May 2022 12:00 UTC

On Saturday, 7 May 2022 at 02:04:42 UTC+1, Ben wrote:
> Ben <ben.u...@bsb.me.uk> writes:
>
> > Malcolm McLean <malcolm.ar...@gmail.com> writes:
> >
> >> ThIs looks along the right lines.
> >> The quintuples need to be indexed by the current state and the current
> >> input, and a set, properly specified, will achieve this.
> >
> > How? std::set is not the right container for this.
> I can answer the how myself now, but I still don't think std::set is the
> right choice as the reader is likely yo be confused by the look-up.
>
A map or an unordered_map would be easier, I agree. But PO has chosen
a set, and that can be made to work.

Re: Validating that the implementation meets the spec for TM transition function

<20220507130216.00006cd3@reddwarf.jmc>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31847&group=comp.theory#31847

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!feeder1.feed.usenet.farm!feed.usenet.farm!peer02.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx13.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Message-ID: <20220507130216.00006cd3@reddwarf.jmc>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc>
<t543p9$d1h$1@dont-email.me>
<20220506222911.00000dd9@reddwarf.jmc>
<t5469b$115$1@dont-email.me>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Lines: 159
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Sat, 07 May 2022 12:02:14 UTC
Date: Sat, 7 May 2022 13:02:16 +0100
X-Received-Bytes: 6561
 by: Mr Flibble - Sat, 7 May 2022 12:02 UTC

On Fri, 6 May 2022 17:08:40 -0500
olcott <polcott2@gmail.com> wrote:

> 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;
> }
Using 'int' directly just makes matters worse as far as writing code
which is easy to understand is concerned. Create named typedefs whose
names describe what the type actually is.

using state_t = std::uint32_t.

Also if there are a finite number of states then consider using an
enum.

/Flibble

Re: Validating that the implementation meets the spec for TM transition function

<t565tt$6fe$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31864&group=comp.theory#31864

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Sat, 7 May 2022 11:14:50 -0500
Organization: A noiseless patient Spider
Lines: 103
Message-ID: <t565tt$6fe$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me> <t559aq$jj2$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 7 May 2022 16:14:53 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="fff6fcee31b0b14fc946e2a4134b630e";
logging-data="6638"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18naqWZwN8OF7FF1gmthJQM"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:aYVN1lwrdYxdoY7t7FghFqK3kZU=
In-Reply-To: <t559aq$jj2$1@dont-email.me>
Content-Language: en-US
 by: olcott - Sat, 7 May 2022 16:14 UTC

On 5/7/2022 3:06 AM, Mikko wrote:
> On 2022-05-06 20:53:58 +0000, olcott said:
>
>> 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'.
>
> The new state is irrelevant until (b) and (c) are performed, so
> the action (a) should be last in the list.
>

That is how I implemented it.

>> struct Quintuple
>> {
>>    u32 state;
>>    u32 symbol;
>>    u32 write_symbol;
>>    u32 next_state;
>>     u8 Tape_Head_Move;
>> };
>
> If you want to print traces of the execution it is better to
> give the type char* to state and next_state. As the only operations
> with these values are assignment and equality test, char* is
> as good as u32. But char* gives better trace if it points to the
> name of the state as it is in the definition of the Turing machine.
>

It also forces far fewer states.

> Although not relevant to the current question, I still recommend
> that Quintuple be renamed to Rule and Quintuple_List be renamed
> to Rules.
>

I want to either use the standard that David S. Woodruff use
http://www.lns.mit.edu/~dsw/turing/turing.html
Or find some common convention of computer science.

I am still thinking that State and States are good names and the opinion
that they are not good names is incorrect. A state must have all of its
transition information in itself.

>> class Quintuple_List
>> {
>>    std::set<Quintuple> list;
>>    NextState(int next_state, int current_input)
>
> This function should be named getRule. Function names shoule start with
> a lower case letter.
>

That would be inconsistent with the spec:
make a transition to state 's'.

>>    {
>>      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”;
>
> Instead of using toupper here you should ensure that only upper case
> letters 'L' and 'R' are ever stored in any tape_head_move.
>

I disagree.

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

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

Re: Validating that the implementation meets the spec for TM transition function

<87a6btx9uz.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31889&group=comp.theory#31889

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function
Date: Sat, 07 May 2022 23:21:08 +0100
Organization: A noiseless patient Spider
Lines: 102
Message-ID: <87a6btx9uz.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="2cb38d29cfd67b01879bf2bacac3ef8f";
logging-data="31475"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+oUYYiytFT5ImMBIlZrPS4/lhea0FkPTY="
Cancel-Lock: sha1:k89I5lMG35gX0AnKJY/lYaOmVTU=
sha1:fuoJiA349YJw3UEQLywPtZc32wA=
X-BSB-Auth: 1.7716931a9b34e4a534be.20220507232108BST.87a6btx9uz.fsf@bsb.me.uk
 by: Ben - Sat, 7 May 2022 22:21 UTC

olcott <polcott2@gmail.com> writes:

> On 5/6/2022 7:54 PM, Ben wrote:
>> olcott <polcott2@gmail.com> writes:
>>
>>> On 5/6/2022 4:41 PM, Malcolm McLean wrote:
>>
>>>>>> olcott <polc...@gmail.com> wrote:
>>
>>>>>>> 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);
>>>>>>> };
>>>>>>> }
>>
>>>> ThIs looks along the right lines.
>>>> The quintuples need to be indexed by the current state and the current input,
>>>> and a set, properly specified, will achieve this.
>>>
>>> Ben didn't seem to understand this.
>> Your code sketch just won't work as you have it now.
>
> Not when you erase the most important part:
>
> bool Quintuple_List::transition_function(std::set<Quintuple>::iterator& current_quintuple)
> {
> unsigned int next_state = current_quintuple->next_state;
> unsigned int 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 == States.end())
> return false;
> current_quintuple = next_quintuple;
> return true;
> }
>
> If you also assume that I got All the missing pieces correctly then it
> should work just fine.

As written, it can't, for reasons I've pointed out before (summary:
assigned to local, uses the wrong symbol to pick the next rule).

But it still also uses bad names. It's a big help that you've fixed
some of the names, but NextState returns (an iterator to) a quintuple,
not a state, and the collection States is a collections of quintuples.

>> Do you know how to
>> get it to work? The result will not be a natural use of a set.
>
> The natural use of a std::set it to look things up very quickly with
> no need for a linear search.

That's not the point. You need to play a little trick or a set is the
just the wrong collection.

> I decided to make my system exactly compatible with these code samples:
> http://www.lns.mit.edu/~dsw/turing/examples/examples.html

Here's an interesting test case that's useful for timing and so on:

A_1RB
A11LC
B_1RC
B11RB
C_1RD
C1_LE
D_1LA
D11LD
E_1RH
E1_LA

You will need to add a '(' for DSW compatibility. Also, note that my
interpreter uses _ as the tape's blank symbol. Change all _s to an
actual spaces if that's what you use.

This is (as far as I know) the current BB(5) champion. It runs for more
that 47 million steps before halting.

--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

Re: Validating that the implementation meets the spec for TM transition function

<874k21x9g3.fsf@bsb.me.uk>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=31890&group=comp.theory#31890

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function
Date: Sat, 07 May 2022 23:30:04 +0100
Organization: A noiseless patient Spider
Lines: 63
Message-ID: <874k21x9g3.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<87sfpmyywj.fsf@bsb.me.uk> <t54f2k$mqp$1@dont-email.me>
<878rreyx3c.fsf@bsb.me.uk> <t54hl6$67o$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="2cb38d29cfd67b01879bf2bacac3ef8f";
logging-data="31475"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19c/5Dswzty1ARMEdzLd7RNoIXBxeymZ14="
Cancel-Lock: sha1:GefDHdbzaQApP/8raSo8TUGCp3E=
sha1:XF7hFIlLr7goHj/Tjs0NiFbq+DA=
X-BSB-Auth: 1.b346706603cbeff522a5.20220507233004BST.874k21x9g3.fsf@bsb.me.uk
 by: Ben - Sat, 7 May 2022 22:30 UTC

olcott <polcott2@gmail.com> writes:

> On 5/6/2022 8:01 PM, Ben wrote:
>> olcott <polcott2@gmail.com> writes:
>>
>>> On 5/6/2022 7:22 PM, Ben wrote:
>>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>>
>>>>> ThIs looks along the right lines.
>>>>> The quintuples need to be indexed by the current state and the current
>>>>> input, and a set, properly specified, will achieve this.
>>>> How? std::set is not the right container for this.
>>>
>>> std::set::find()
>>>
>>> std::set<Quintuple> States;
>>> std::vector<unsigned char> Tape;
>>> void insert(const Quintuple& QT){ States.insert(QT); };
>>>
>>> std::set<Quintuple>::iterator
>>> NextState(int current_input, int next_state)
>>> {
>>> Quintuple QT(current_input, next_state);
>>> return States.find(QT);
>>> }
>> No, this won't work. You can /make/ it work, but to do that you have to
>> play tricks with what's considered to be unique in the set. I think a
>> std::map is more natural.
>>
>
> I got dem tricks...

Good. In some languages you would not be able to make a set work here
at all.

> std::map has redundant data or splits the class data into two pieces.

We should compare notes when you have it all coded. How long to go? I
just wrote a C++ TM interpreter so we can compare more accurately. (I
have an advantage here in that I've done this several times, so I can't
easily judge how long it might take the first time round.)

>> And your names appear messed up again. NextState (with no declared
>
> It has a declared return type that doesn't fit well on the same line:
> std::set<Quintuple>::iterator

Ah yes. Strange that it's called NextState then.

>> return type) returns a Quintuple, not a state. And it has "next_state"
>> as an argument which seems unlikely. Surely NextState needs the current
>> state and input symbol?
>
> You missed this?
>>> NextState(int current_input, int next_state)

No, I'm talking about the name. next_state does not sound like the
current state.

--
Ben.
"le génie humain a des limites, quand la bêtise humaine n’en a pas"
Alexandre Dumas (fils)

Pages:12345678
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor