Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

If the facts don't fit the theory, change the facts. -- Albert Einstein


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
Re: Validating that the implementation meets the spec for TM transition function

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

 copy mid

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

 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:31:04 +0100
Organization: A noiseless patient Spider
Lines: 23
Message-ID: <87y1zdvutz.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> <8735hmywyf.fsf@bsb.me.uk>
<9f101e19-e941-45da-abf4-8a63b362347an@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="2cb38d29cfd67b01879bf2bacac3ef8f";
logging-data="31475"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+IIcj97fZAwaOTF8h/mSZR++LGUbDlg74="
Cancel-Lock: sha1:jeDDaeXdKd7kWErZe0MtIS7/FyA=
sha1:rjpVfCpDcZ/3CQ5IEXKHLRp8F5k=
X-BSB-Auth: 1.8a884de12ab9c95cf741.20220507233104BST.87y1zdvutz.fsf@bsb.me.uk
 by: Ben - Sat, 7 May 2022 22:31 UTC

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

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

I wonder... Let's see. There no clear sign in the current sketches
that he can make it work.

--
Ben.

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

<lMydne2Ercz5n-r_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 07 May 2022 18:36:04 -0500
Date: Sat, 7 May 2022 18:36:04 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
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>
<9f101e19-e941-45da-abf4-8a63b362347an@googlegroups.com>
<87y1zdvutz.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87y1zdvutz.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <lMydne2Ercz5n-r_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 40
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-spf9X7Lm9Vg0jMyGD8HVHkeh3a56w8YJVcCenfxK/7/YjRqRrsGd0PiuOw8gVOFMeI14OUaKUbZFboJ!GXPDhmJGa7vTSEDgAkKSp0uA93pC0WENZG55LOl1RRFWHZq49aGZq7tSBHFXVwhMJO/DtE/LrYw=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2845
 by: olcott - Sat, 7 May 2022 23:36 UTC

On 5/7/2022 5:31 PM, Ben wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> 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.
>
> I wonder... Let's see. There no clear sign in the current sketches
> that he can make it work.
>

I got everything working besides:
bool Quintuple_List::transition_function(std::set<Quintuple>::iterator&
current_quintuple)

I knew this would be the hardest part. I also got the other TM
interpreter to work correctly. Setting the tape manually is trivial.
I am reviewing other sources for how state transitions work.

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

<t5782u$1p6$1@dont-email.me>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: jbb...@notatt.com (Jeff Barnett)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Sat, 7 May 2022 19:57:44 -0600
Organization: A noiseless patient Spider
Lines: 107
Message-ID: <t5782u$1p6$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>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 8 May 2022 01:57:51 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="5cf15a540ae5f944728a0ba2ac83aa75";
logging-data="1830"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18vtTSQWnv5cJPOcvmVf6pST9S9zFZuJkY="
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.8.1
Cancel-Lock: sha1:f2tHyglh/6DPdsoy78Fx17/EY1M=
In-Reply-To: <87a6btx9uz.fsf@bsb.me.uk>
Content-Language: en-US
 by: Jeff Barnett - Sun, 8 May 2022 01:57 UTC

On 5/7/2022 4:21 PM, Ben wrote:
> 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.

Questions:

Was 47 million steps a measured or a theoretically computed measure?

How long would you estimate that a well-written TM interpreter on modern
hardware needs to interpret the above? A few seconds or minutes?
--
Jeff Barnett

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

<B4Cdnb1LsNSkuOr_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 07 May 2022 21:04:41 -0500
Date: Sat, 7 May 2022 21:04:40 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
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> <87a6btx9uz.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87a6btx9uz.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <B4Cdnb1LsNSkuOr_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 110
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-7mIh50Vz6kLySTYQK2wgtGRISlwUoOwNXuP6+fpX1nlyWODMDrZtvqdn9Xr2iafyIWHg196q54jEDEE!pm54t0V5QniX25PuwA8zz0UXEtUzLnJb2qnnXSyBIK9MUpEhnHMio4Agq+fLeQ/+HEgr8y2V2Xc=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 4814
 by: olcott - Sun, 8 May 2022 02:04 UTC

On 5/7/2022 5:21 PM, Ben wrote:
> 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.
>

The TM interpreter uses linear search, I hate that, it doesn't scale.

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

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

<t580lc$i4f$1@dont-email.me>

 copy mid

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

 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: Sun, 8 May 2022 11:57:16 +0300
Organization: -
Lines: 22
Message-ID: <t580lc$i4f$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me> <t559aq$jj2$1@dont-email.me> <t565tt$6fe$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="46db347dd1bdd6dd40c3bda51f1b355a";
logging-data="18575"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/fYY+mrnz5xPJipbnQC5Z0"
User-Agent: Unison/2.2
Cancel-Lock: sha1:tIiQgOoFUp/a1B7ZvrKKEp16SOM=
 by: Mikko - Sun, 8 May 2022 08:57 UTC

On 2022-05-07 16:14:50 +0000, olcott said:

> On 5/7/2022 3:06 AM, Mikko wrote:
>> On 2022-05-06 20:53:58 +0000, olcott said:

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

Where in the spec is the requirement that there be a function from
int and int to std::set<Quintuple>::iterator that is named NextState?

Mikko

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

<5695f271-7534-4b2a-9454-fb83987b322fn@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:620a:4542:b0:6a0:651b:be0b with SMTP id u2-20020a05620a454200b006a0651bbe0bmr2840188qkp.633.1652002743327;
Sun, 08 May 2022 02:39:03 -0700 (PDT)
X-Received: by 2002:a5b:6c1:0:b0:633:b5c7:b9b7 with SMTP id
r1-20020a5b06c1000000b00633b5c7b9b7mr9012829ybq.67.1652002743101; Sun, 08 May
2022 02:39:03 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.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: Sun, 8 May 2022 02:39:02 -0700 (PDT)
In-Reply-To: <lMydne2Ercz5n-r_nZ2dnUU7_8zNnZ2d@giganews.com>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:5d8c:e4dd:a39c:7db6;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:5d8c:e4dd:a39c:7db6
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> <9f101e19-e941-45da-abf4-8a63b362347an@googlegroups.com>
<87y1zdvutz.fsf@bsb.me.uk> <lMydne2Ercz5n-r_nZ2dnUU7_8zNnZ2d@giganews.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <5695f271-7534-4b2a-9454-fb83987b322fn@googlegroups.com>
Subject: Re: Validating that the implementation meets the spec for TM
transition function
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Sun, 08 May 2022 09:39:03 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Malcolm McLean - Sun, 8 May 2022 09:39 UTC

On Sunday, 8 May 2022 at 00:36:12 UTC+1, olcott wrote:
> On 5/7/2022 5:31 PM, Ben wrote:
> > Malcolm McLean <malcolm.ar...@gmail.com> writes:
> >
> >> 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.
> >
> > I wonder... Let's see. There no clear sign in the current sketches
> > that he can make it work.
> >
> I got everything working besides:
> bool Quintuple_List::transition_function(std::set<Quintuple>::iterator&
> current_quintuple)
>
> I knew this would be the hardest part. I also got the other TM
> interpreter to work correctly. Setting the tape manually is trivial.
> I am reviewing other sources for how state transitions work.
>
The easiest way to make a set do what you want is to overload the '<' operator
for struct Quintuple.
Then you fill a blank Quintuple with the state and input symbol, and call
the "find" method on the set to retrive the full Quintuple.

It's a fairly horrid interface, but that's C++.

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

<KRNdK.6818$Jex1.1781@fx35.iad>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!feeder.usenetexpress.com!tr3.eu1.usenetexpress.com!81.171.65.13.MISMATCH!peer01.ams4!peer.am4.highwinds-media.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx35.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0) Gecko/20100101 Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM transition function
Content-Language: en-US
Newsgroups: comp.theory
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> <87a6btx9uz.fsf@bsb.me.uk> <B4Cdnb1LsNSkuOr_nZ2dnUU7_83NnZ2d@giganews.com>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <B4Cdnb1LsNSkuOr_nZ2dnUU7_83NnZ2d@giganews.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 127
Message-ID: <KRNdK.6818$Jex1.1781@fx35.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sun, 8 May 2022 07:30:50 -0400
X-Received-Bytes: 5337
 by: Richard Damon - Sun, 8 May 2022 11:30 UTC

On 5/7/22 10:04 PM, olcott wrote:
> On 5/7/2022 5:21 PM, Ben wrote:
>> 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.
>>
>
> The TM interpreter uses linear search, I hate that, it doesn't scale.

That means it is using the wrong data structure.

I would probably just use an array for the rule storage, having an array
of structures of Next State, Replacement Charactrer, Tape Motion, and
index it on Current State and Current Tape Character.

Then the processing loop is just a tight loop like:

curr_char = tape[index]
next_state = rules[current_state][curr_char].next_state;
tape[index] = rules[current_state][curr_char].new_char;
index += rules[current_state][curr_char].tape_incr;
current_state = next_state;

Add an end test, trace logging, and something to read in the rules and
tape, and you are done.

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

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

<zVNdK.10345$Awz.6657@fx03.iad>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!tr3.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx03.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0) Gecko/20100101 Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM transition function
Content-Language: en-US
Newsgroups: comp.theory
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> <87a6btx9uz.fsf@bsb.me.uk> <t5782u$1p6$1@dont-email.me>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <t5782u$1p6$1@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 117
Message-ID: <zVNdK.10345$Awz.6657@fx03.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sun, 8 May 2022 07:34:55 -0400
X-Received-Bytes: 5039
 by: Richard Damon - Sun, 8 May 2022 11:34 UTC

On 5/7/22 9:57 PM, Jeff Barnett wrote:
> On 5/7/2022 4:21 PM, Ben wrote:
>> 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.
>
> Questions:
>
> Was 47 million steps a measured or a theoretically computed measure?
>
> How long would you estimate that a well-written TM interpreter on modern
> hardware needs to interpret the above? A few seconds or minutes?

A well written TM interpreter on modern hardware should be able to do
many millions of steps a second (as I posted a main loop that can do
that), so we are in seconds.

IF we need to generate a trace that can be inspected by a human, we
likely get I/O bound generating that trace, and it may go to order of
minutes to maybe hours

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

<8783735f-7f11-4914-9724-044c3b57831en@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a37:b4d:0:b0:69f:7742:9778 with SMTP id 74-20020a370b4d000000b0069f77429778mr8743989qkl.109.1652011912266;
Sun, 08 May 2022 05:11:52 -0700 (PDT)
X-Received: by 2002:a81:9c48:0:b0:2ed:7f5b:84fa with SMTP id
n8-20020a819c48000000b002ed7f5b84famr9502245ywa.511.1652011911985; Sun, 08
May 2022 05:11:51 -0700 (PDT)
Path: i2pn2.org!i2pn.org!usenet.goja.nl.eu.org!weretis.net!feeder8.news.weretis.net!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: Sun, 8 May 2022 05:11:51 -0700 (PDT)
In-Reply-To: <zVNdK.10345$Awz.6657@fx03.iad>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:5d8c:e4dd:a39c:7db6;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:5d8c:e4dd:a39c:7db6
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>
<87a6btx9uz.fsf@bsb.me.uk> <t5782u$1p6$1@dont-email.me> <zVNdK.10345$Awz.6657@fx03.iad>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <8783735f-7f11-4914-9724-044c3b57831en@googlegroups.com>
Subject: Re: Validating that the implementation meets the spec for TM
transition function
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Sun, 08 May 2022 12:11:52 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Malcolm McLean - Sun, 8 May 2022 12:11 UTC

On Sunday, 8 May 2022 at 12:35:00 UTC+1, richar...@gmail.com wrote:
> On 5/7/22 9:57 PM, Jeff Barnett wrote:
> > On 5/7/2022 4:21 PM, Ben wrote:
> >> olcott <polc...@gmail.com> writes:
> >>
> >>> On 5/6/2022 7:54 PM, Ben wrote:
> >>>> olcott <polc...@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.
> >
> > Questions:
> >
> > Was 47 million steps a measured or a theoretically computed measure?
> >
> > How long would you estimate that a well-written TM interpreter on modern
> > hardware needs to interpret the above? A few seconds or minutes?
> A well written TM interpreter on modern hardware should be able to do
> many millions of steps a second (as I posted a main loop that can do
> that), so we are in seconds.
>
> IF we need to generate a trace that can be inspected by a human, we
> likely get I/O bound generating that trace, and it may go to order of
> minutes to maybe hours
>
Whilst you might write a pure implementation of a Turing machine as a
first step, you're unlikely to use it much. People want to see the machine
buzz and whir away, as it performs its magic.
So that means some sort of graphical interface. Which is orders of
magnitude slower than a simple virtual machine.

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

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

 copy mid

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

 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: Sun, 08 May 2022 14:44:45 +0100
Organization: A noiseless patient Spider
Lines: 56
Message-ID: <878rrcuoj6.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> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="2cb38d29cfd67b01879bf2bacac3ef8f";
logging-data="3082"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/Fd2dTSgfE1vDfMwhLK0j/11VFzII2fz8="
Cancel-Lock: sha1:ocM10NWz776yLlfsS4oQXzA6PsA=
sha1:RihvcFnSUOLWLBSi7B8OK3Icz6g=
X-BSB-Auth: 1.b41e4bb6d03721a267b1.20220508144445BST.878rrcuoj6.fsf@bsb.me.uk
 by: Ben - Sun, 8 May 2022 13:44 UTC

Jeff Barnett <jbb@notatt.com> writes:

> On 5/7/2022 4:21 PM, Ben wrote:

>> 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.
>
> Questions:
>
> Was 47 million steps a measured or a theoretically computed measure?

Measured.

> How long would you estimate that a well-written TM interpreter on
> modern hardware needs to interpret the above? A few seconds or
> minutes?

$ time ./tm bb-5-2 ""
A B C D E H
1 1LC 1RB _LE 1LD _LA
_ 1RB 1RC 1RD 1LA 1RH

steps=47176874

real 0m0.237s
user 0m0.237s
sys 0m0.000s

This is a C++ interpreter I've just written so that I can compare
designs with anything PO produces. I've not worked on making it fast
though I compiler with -O3 for this test.

It uses a plain std::string for the tape, so I imagine the quality of
the C++ library is the key factor (I've not profiled it yet).

(That table at the start is just the sates transition table written in a
compact form.)

--
Ben.

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

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

 copy mid

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

 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: Sun, 08 May 2022 14:46:50 +0100
Organization: A noiseless patient Spider
Lines: 11
Message-ID: <87zgjst9v9.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> <87a6btx9uz.fsf@bsb.me.uk>
<B4Cdnb1LsNSkuOr_nZ2dnUU7_83NnZ2d@giganews.com>
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="3082"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19XHaWmn0Ipx/tL5NgLsrfhZ5qY27sqgj8="
Cancel-Lock: sha1:4lTmTon/G+EjDUPN9mmMMmWKf50=
sha1:d1anD3dNlZIQH9t86tqiXN+QlLI=
X-BSB-Auth: 1.9d2e1c1278d948cc48ce.20220508144650BST.87zgjst9v9.fsf@bsb.me.uk
 by: Ben - Sun, 8 May 2022 13:46 UTC

olcott <NoOne@NoWhere.com> writes:

> The TM interpreter uses linear search, I hate that, it doesn't scale.

What do you use linear search for? I thought the key structure you used
was a std::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

<t58tdr$93p$1@dont-email.me>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: jbb...@notatt.com (Jeff Barnett)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Sun, 8 May 2022 11:08:09 -0600
Organization: A noiseless patient Spider
Lines: 77
Message-ID: <t58tdr$93p$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>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 8 May 2022 17:08:12 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="5cf15a540ae5f944728a0ba2ac83aa75";
logging-data="9337"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+B/ORwbfujHsQFaDZDyrw8xx8tWxr4St4="
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:OayLcdYs2BXAiQbtJl81Q/xq5RM=
In-Reply-To: <878rrcuoj6.fsf@bsb.me.uk>
Content-Language: en-US
 by: Jeff Barnett - Sun, 8 May 2022 17:08 UTC

On 5/8/2022 7:44 AM, Ben wrote:
> Jeff Barnett <jbb@notatt.com> writes:
>
>> On 5/7/2022 4:21 PM, Ben wrote:
>
>>> 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.
>>
>> Questions:
>>
>> Was 47 million steps a measured or a theoretically computed measure?
>
> Measured.
>
>> How long would you estimate that a well-written TM interpreter on
>> modern hardware needs to interpret the above? A few seconds or
>> minutes?
>
> $ time ./tm bb-5-2 ""
> A B C D E H
> 1 1LC 1RB _LE 1LD _LA
> _ 1RB 1RC 1RD 1LA 1RH
>
> steps=47176874
>
> real 0m0.237s
> user 0m0.237s
> sys 0m0.000s
>
> This is a C++ interpreter I've just written so that I can compare
> designs with anything PO produces. I've not worked on making it fast
> though I compiler with -O3 for this test.
>
> It uses a plain std::string for the tape, so I imagine the quality of
> the C++ library is the key factor (I've not profiled it yet).
>
> (That table at the start is just the sates transition table written in a
> compact form.)
Impressive. I'm going to conjecture from the rate of interpretation
47M/.237s ~ 200,000,000 states per second that TM definition, your code,
and used library code must have all snuggled into the machine cache. I'm
also assuming that the C++ code (because of the nature of the
computation) does not lend itself to using multiple cores which makes
the speed all that more impressive.

Other questions:

Did you directly set up a (state X character) -> (quintuple) lookup
rather than doing it in two steps? I don't think that wouldn't make a
big difference for this example but could for TM definitions with much
larger quintuple tables.

Do C++ character arrays (strings?) have provisions to grow if a char is
pushed passed the structure's end? I'm thinking of Lisp arrays with fill
pointers as an example. To ask the question a different way which of the
following did you do to set the initial size of the "tape": determine
empirically, start arbitrarily and let the C++ system run-time grow the
structure as needed, or start arbitrarily and use your own code to deal
with the issue?
--
Jeff Barnett

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

<PRTdK.8710$t72a.4785@fx10.iad>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!news.mixmin.net!news2.arglkargh.de!news.karotte.org!news.uzoreto.com!peer03.ams4!peer.am4.highwinds-media.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx10.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0)
Gecko/20100101 Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
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> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <zVNdK.10345$Awz.6657@fx03.iad>
<8783735f-7f11-4914-9724-044c3b57831en@googlegroups.com>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <8783735f-7f11-4914-9724-044c3b57831en@googlegroups.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 139
Message-ID: <PRTdK.8710$t72a.4785@fx10.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sun, 8 May 2022 14:20:31 -0400
X-Received-Bytes: 6529
 by: Richard Damon - Sun, 8 May 2022 18:20 UTC

On 5/8/22 8:11 AM, Malcolm McLean wrote:
> On Sunday, 8 May 2022 at 12:35:00 UTC+1, richar...@gmail.com wrote:
>> On 5/7/22 9:57 PM, Jeff Barnett wrote:
>>> On 5/7/2022 4:21 PM, Ben wrote:
>>>> olcott <polc...@gmail.com> writes:
>>>>
>>>>> On 5/6/2022 7:54 PM, Ben wrote:
>>>>>> olcott <polc...@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.
>>>
>>> Questions:
>>>
>>> Was 47 million steps a measured or a theoretically computed measure?
>>>
>>> How long would you estimate that a well-written TM interpreter on modern
>>> hardware needs to interpret the above? A few seconds or minutes?
>> A well written TM interpreter on modern hardware should be able to do
>> many millions of steps a second (as I posted a main loop that can do
>> that), so we are in seconds.
>>
>> IF we need to generate a trace that can be inspected by a human, we
>> likely get I/O bound generating that trace, and it may go to order of
>> minutes to maybe hours
>>
> Whilst you might write a pure implementation of a Turing machine as a
> first step, you're unlikely to use it much. People want to see the machine
> buzz and whir away, as it performs its magic.
> So that means some sort of graphical interface. Which is orders of
> magnitude slower than a simple virtual machine.

Yes, if you want to watch the machine run, you are limiting your step
rate to Human speed.

If you can watch 1 step a second, the 47 million steps is on the order
of a year and a half at 24-7, but then the limiting factor isn't the
computer but the observer.

You could probably "checkpoint" the results every, say, 1000 steps to
some log, and then build a browser to let you pull up any of the 47,000
checkpoints to see the progress, and maybe do a step by step run from
the checkpoint if interested.

The key point is that the computer running the Turing Machine isn't the
limiting factor for this case, but the human observer.

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

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

 copy mid

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

 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: Sun, 08 May 2022 19:27:35 +0100
Organization: A noiseless patient Spider
Lines: 112
Message-ID: <87tu9zubfs.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> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="2cb38d29cfd67b01879bf2bacac3ef8f";
logging-data="15371"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19T80vKKWkhroeqzA5sdeGual1yxVt493I="
Cancel-Lock: sha1:OyK5ITVXwgfxSmo27J8jdAo1v8U=
sha1:lEELvjN5TNRU81is/IRDSDsu73k=
X-BSB-Auth: 1.6e9d6e7e557cc58b161e.20220508192735BST.87tu9zubfs.fsf@bsb.me.uk
 by: Ben - Sun, 8 May 2022 18:27 UTC

Jeff Barnett <jbb@notatt.com> writes:

> On 5/8/2022 7:44 AM, Ben wrote:
>> Jeff Barnett <jbb@notatt.com> writes:
>>
>>> On 5/7/2022 4:21 PM, Ben wrote:
>>
>>>> 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.
>>>
>>> Questions:
>>>
>>> Was 47 million steps a measured or a theoretically computed measure?
>> Measured.
>>
>>> How long would you estimate that a well-written TM interpreter on
>>> modern hardware needs to interpret the above? A few seconds or
>>> minutes?
>> $ time ./tm bb-5-2 ""
>> A B C D E H
>> 1 1LC 1RB _LE 1LD _LA
>> _ 1RB 1RC 1RD 1LA 1RH
>> steps=47176874
>> real 0m0.237s
>> user 0m0.237s
>> sys 0m0.000s
>> This is a C++ interpreter I've just written so that I can compare
>> designs with anything PO produces. I've not worked on making it fast
>> though I compiler with -O3 for this test.
>> It uses a plain std::string for the tape, so I imagine the quality of
>> the C++ library is the key factor (I've not profiled it yet).
>> (That table at the start is just the sates transition table written in a
>> compact form.)
>
> Impressive.

Thanks, but there's no skill involved, other that not picking any part
of the design that looks like a certain loser.

> I'm going to conjecture from the rate of interpretation 47M/.237s ~
> 200,000,000 states per second that TM definition, your code, and used
> library code must have all snuggled into the machine cache.

Seems likely.

> I'm also
> assuming that the C++ code (because of the nature of the computation)
> does not lend itself to using multiple cores which makes the speed all
> that more impressive.

Yes, single core. My laptop is not an old banger (1.6Ghz i5-8256U), but
even so I was surprised.

> Other questions:
>
> Did you directly set up a (state X character) -> (quintuple) lookup
> rather than doing it in two steps?

There's only one lookup, but not that one. In my current design the
states are objects that hold a char to triple map, the triple being the
character to write, the tape movement, and a pointer to the next state).

The inner loop is therefore very tight. I could (probably) speed it up
a bit by using an array for that lookup, but I imagined I might like to
use fancy Unicode symbols at some stage and a map will work better for
that.

> I don't think that wouldn't make a big difference for this example but
> could for TM definitions with much larger quintuple tables.
>
> Do C++ character arrays (strings?) have provisions to grow if a char
> is pushed passed the structure's end?

push_back is amortised constant time whereas append and insert give no
guarantees. I think glibc goes to some effort to make appending and
growing at the front quote efficient.

> I'm thinking of Lisp arrays with
> fill pointers as an example. To ask the question a different way which
> of the following did you do to set the initial size of the "tape":
> determine empirically, start arbitrarily and let the C++ system
> run-time grow the structure as needed, or start arbitrarily and use
> your own code to deal with the issue?

My code is utterly trivial. The tape is a std::string to which I assign
the input. All that happens after that is that tape[head] is assigned
to, and the string is grown by one blank, either at the front or the
back, if the tape movement requires it.

I'll post the code when the time comes if case anyone cares to see it.

I plan to do a Haskell version too. I used to have one, but that got
lost in retirement.

--
Ben.

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

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

 copy mid

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

 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: Sun, 08 May 2022 19:59:56 +0100
Organization: A noiseless patient Spider
Lines: 171
Message-ID: <87fslju9xv.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> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <zVNdK.10345$Awz.6657@fx03.iad>
<8783735f-7f11-4914-9724-044c3b57831en@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="2cb38d29cfd67b01879bf2bacac3ef8f";
logging-data="30159"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX194bp2GwJGcfxzKX5JZx//g9o/FbQztf18="
Cancel-Lock: sha1:YLayVhwZitFslp1S7a5F+N8DDOQ=
sha1:60wznOH/lFJkoKCuOA3g4WaTSV4=
X-BSB-Auth: 1.b67fddc982fbfbeda7be.20220508195956BST.87fslju9xv.fsf@bsb.me.uk
 by: Ben - Sun, 8 May 2022 18:59 UTC

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

> On Sunday, 8 May 2022 at 12:35:00 UTC+1, richar...@gmail.com wrote:
>> On 5/7/22 9:57 PM, Jeff Barnett wrote:
>> > On 5/7/2022 4:21 PM, Ben wrote:

>> >> 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.
>> >
>> > Questions:
>> >
>> > Was 47 million steps a measured or a theoretically computed measure?
>> >
>> > How long would you estimate that a well-written TM interpreter on modern
>> > hardware needs to interpret the above? A few seconds or minutes?
>> A well written TM interpreter on modern hardware should be able to do
>> many millions of steps a second (as I posted a main loop that can do
>> that), so we are in seconds.
>>
>> IF we need to generate a trace that can be inspected by a human, we
>> likely get I/O bound generating that trace, and it may go to order of
>> minutes to maybe hours
>>
> Whilst you might write a pure implementation of a Turing machine as a
> first step, you're unlikely to use it much. People want to see the machine
> buzz and whir away, as it performs its magic.
> So that means some sort of graphical interface. Which is orders of
> magnitude slower than a simple virtual machine.

You don't really need much. A simple print of the tape (centred on the
head) give the feel for what's happening. Throw in a \r and a delay and
will look like an animation even in a plain tty.

With tracing turned on, my simple implementation shows this for the
BB(4) champion:

$ ./simple-tm bb-4-2 ""
A B C D H
1 1LB _LC 1LD _RA
_ 1RB 1LA 1RH 1RD
________________________________[A|_]_________________________________
________________________________[B|_]_________________________________
________________________________[A|_]_________________________________
_______________________________1[B|_]_________________________________
________________________________[A|1]1________________________________
________________________________[B|_]11_______________________________
________________________________[A|_]111______________________________
_______________________________1[B|1]11_______________________________
________________________________[C|1]_11______________________________
________________________________[D|_]1_11_____________________________
_______________________________1[D|1]_11______________________________
______________________________1_[A|_]11_______________________________
_____________________________1_1[B|1]1________________________________
______________________________1_[C|1]_1_______________________________
_______________________________1[D|_]1_1______________________________
______________________________11[D|1]_1_______________________________
_____________________________11_[A|_]1________________________________
____________________________11_1[B|1]_________________________________
_____________________________11_[C|1]_________________________________
______________________________11[D|_]1________________________________
_____________________________111[D|1]_________________________________
____________________________111_[A|_]_________________________________
___________________________111_1[B|_]_________________________________
____________________________111_[A|1]1________________________________
_____________________________111[B|_]11_______________________________
______________________________11[A|1]111______________________________
_______________________________1[B|1]1111_____________________________
________________________________[C|1]_1111____________________________
________________________________[D|_]1_1111___________________________
_______________________________1[D|1]_1111____________________________
______________________________1_[A|_]1111_____________________________
_____________________________1_1[B|1]111______________________________
______________________________1_[C|1]_111_____________________________
_______________________________1[D|_]1_111____________________________
______________________________11[D|1]_111_____________________________
_____________________________11_[A|_]111______________________________
____________________________11_1[B|1]11_______________________________
_____________________________11_[C|1]_11______________________________
______________________________11[D|_]1_11_____________________________
_____________________________111[D|1]_11______________________________
____________________________111_[A|_]11_______________________________
___________________________111_1[B|1]1________________________________
____________________________111_[C|1]_1_______________________________
_____________________________111[D|_]1_1______________________________
____________________________1111[D|1]_1_______________________________
___________________________1111_[A|_]1________________________________
__________________________1111_1[B|1]_________________________________
___________________________1111_[C|1]_________________________________
____________________________1111[D|_]1________________________________
___________________________11111[D|1]_________________________________
__________________________11111_[A|_]_________________________________
_________________________11111_1[B|_]_________________________________
__________________________11111_[A|1]1________________________________
___________________________11111[B|_]11_______________________________
____________________________1111[A|1]111______________________________
_____________________________111[B|1]1111_____________________________
______________________________11[C|1]_1111____________________________
_______________________________1[D|1]1_1111___________________________
______________________________1_[A|1]_1111____________________________
_______________________________1[B|_]1_1111___________________________
________________________________[A|1]11_1111__________________________
________________________________[B|_]111_1111_________________________
________________________________[A|_]1111_1111________________________
_______________________________1[B|1]111_1111_________________________
________________________________[C|1]_111_1111________________________
________________________________[D|_]1_111_1111_______________________
_______________________________1[D|1]_111_1111________________________
______________________________1_[A|_]111_1111_________________________
_____________________________1_1[B|1]11_1111__________________________
______________________________1_[C|1]_11_1111_________________________
_______________________________1[D|_]1_11_1111________________________
______________________________11[D|1]_11_1111_________________________
_____________________________11_[A|_]11_1111__________________________
____________________________11_1[B|1]1_1111___________________________
_____________________________11_[C|1]_1_1111__________________________
______________________________11[D|_]1_1_1111_________________________
_____________________________111[D|1]_1_1111__________________________
____________________________111_[A|_]1_1111___________________________
___________________________111_1[B|1]_1111____________________________
____________________________111_[C|1]__1111___________________________
_____________________________111[D|_]1__1111__________________________
____________________________1111[D|1]__1111___________________________
___________________________1111_[A|_]_1111____________________________
__________________________1111_1[B|_]1111_____________________________
___________________________1111_[A|1]11111____________________________
____________________________1111[B|_]111111___________________________
_____________________________111[A|1]1111111__________________________
______________________________11[B|1]11111111_________________________
_______________________________1[C|1]_11111111________________________
________________________________[D|1]1_11111111_______________________
________________________________[A|1]_11111111________________________
________________________________[B|_]1_11111111_______________________
________________________________[A|_]11_11111111______________________
_______________________________1[B|1]1_11111111_______________________
________________________________[C|1]_1_11111111______________________
________________________________[D|_]1_1_11111111_____________________
_______________________________1[D|1]_1_11111111______________________
______________________________1_[A|_]1_11111111_______________________
_____________________________1_1[B|1]_11111111________________________
______________________________1_[C|1]__11111111_______________________
_______________________________1[D|_]1__11111111______________________
______________________________11[D|1]__11111111_______________________
_____________________________11_[A|_]_11111111________________________
____________________________11_1[B|_]11111111_________________________
_____________________________11_[A|1]111111111________________________
______________________________11[B|_]1111111111_______________________
_______________________________1[A|1]11111111111______________________
________________________________[B|1]111111111111_____________________
________________________________[C|_]_111111111111____________________
_______________________________1[H|_]111111111111_____________________
steps=109


Click here to read the complete article
Re: Validating that the implementation meets the spec for TM transition function

<zLUdK.4623$arR.255@fx48.iad>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!tr3.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx48.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0) Gecko/20100101 Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM transition function
Content-Language: en-US
Newsgroups: comp.theory
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> <87a6btx9uz.fsf@bsb.me.uk> <t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk> <t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <87tu9zubfs.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 136
Message-ID: <zLUdK.4623$arR.255@fx48.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sun, 8 May 2022 15:22:07 -0400
X-Received-Bytes: 6661
 by: Richard Damon - Sun, 8 May 2022 19:22 UTC

On 5/8/22 2:27 PM, Ben wrote:
> Jeff Barnett <jbb@notatt.com> writes:
>
>> On 5/8/2022 7:44 AM, Ben wrote:
>>> Jeff Barnett <jbb@notatt.com> writes:
>>>
>>>> On 5/7/2022 4:21 PM, Ben wrote:
>>>
>>>>> 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.
>>>>
>>>> Questions:
>>>>
>>>> Was 47 million steps a measured or a theoretically computed measure?
>>> Measured.
>>>
>>>> How long would you estimate that a well-written TM interpreter on
>>>> modern hardware needs to interpret the above? A few seconds or
>>>> minutes?
>>> $ time ./tm bb-5-2 ""
>>> A B C D E H
>>> 1 1LC 1RB _LE 1LD _LA
>>> _ 1RB 1RC 1RD 1LA 1RH
>>> steps=47176874
>>> real 0m0.237s
>>> user 0m0.237s
>>> sys 0m0.000s
>>> This is a C++ interpreter I've just written so that I can compare
>>> designs with anything PO produces. I've not worked on making it fast
>>> though I compiler with -O3 for this test.
>>> It uses a plain std::string for the tape, so I imagine the quality of
>>> the C++ library is the key factor (I've not profiled it yet).
>>> (That table at the start is just the sates transition table written in a
>>> compact form.)
>>
>> Impressive.
>
> Thanks, but there's no skill involved, other that not picking any part
> of the design that looks like a certain loser.
>
>> I'm going to conjecture from the rate of interpretation 47M/.237s ~
>> 200,000,000 states per second that TM definition, your code, and used
>> library code must have all snuggled into the machine cache.
>
> Seems likely.
>
>> I'm also
>> assuming that the C++ code (because of the nature of the computation)
>> does not lend itself to using multiple cores which makes the speed all
>> that more impressive.
>
> Yes, single core. My laptop is not an old banger (1.6Ghz i5-8256U), but
> even so I was surprised.
>
>> Other questions:
>>
>> Did you directly set up a (state X character) -> (quintuple) lookup
>> rather than doing it in two steps?
>
> There's only one lookup, but not that one. In my current design the
> states are objects that hold a char to triple map, the triple being the
> character to write, the tape movement, and a pointer to the next state).
>
> The inner loop is therefore very tight. I could (probably) speed it up
> a bit by using an array for that lookup, but I imagined I might like to
> use fancy Unicode symbols at some stage and a map will work better for
> that.

My thinking is that there are only two things that have the ability to
"cost" time. One is tape management, but using an object that acts like
an array which is indexed in makes this fast except when we need to
expand it, but that will generally amortize to a small value. (Letting
the string class do that isn't a bad option).

The second "costly" operation is looking up the rule based on current
state / tape symbol. For speed this really needs to be O(1) (at least
amortized). If we reduce our state and input symbols to an internal
numbering of 0-n an array works great. If we limit our states to 'ascii
characters' then the 256 x 256 array isn't outlandish in space
requirements for modern machines.

If you want full Unicode characters, then either you need the conversion
to a simple 0-n enumeration, or going to a hash table to store the
rules. The question becomes which cost more the input/output conversion
to use 0-n values, or hashing (and handling the possible collisions).

My thought is that in the 0-n enumeration, the table is "dense" in the
sense that all non-terminal state will be fully filled out. (And
terminal states don't actually need an entry, just a value recognized as
terminal).

>
>> I don't think that wouldn't make a big difference for this example but
>> could for TM definitions with much larger quintuple tables.
>>
>> Do C++ character arrays (strings?) have provisions to grow if a char
>> is pushed passed the structure's end?
>
> push_back is amortised constant time whereas append and insert give no
> guarantees. I think glibc goes to some effort to make appending and
> growing at the front quote efficient.
>
>> I'm thinking of Lisp arrays with
>> fill pointers as an example. To ask the question a different way which
>> of the following did you do to set the initial size of the "tape":
>> determine empirically, start arbitrarily and let the C++ system
>> run-time grow the structure as needed, or start arbitrarily and use
>> your own code to deal with the issue?
>
> My code is utterly trivial. The tape is a std::string to which I assign
> the input. All that happens after that is that tape[head] is assigned
> to, and the string is grown by one blank, either at the front or the
> back, if the tape movement requires it.
>
> I'll post the code when the time comes if case anyone cares to see it.
>
> I plan to do a Haskell version too. I used to have one, but that got
> lost in retirement.
>

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

<20220508203050.00001cd7@reddwarf.jmc>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!feeder1.feed.usenet.farm!feed.usenet.farm!feeder.usenetexpress.com!tr1.eu1.usenetexpress.com!81.171.65.13.MISMATCH!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx07.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: <20220508203050.00001cd7@reddwarf.jmc>
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> <87a6btx9uz.fsf@bsb.me.uk> <t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk> <t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk> <zLUdK.4623$arR.255@fx48.iad>
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=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 129
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Sun, 08 May 2022 19:30:50 UTC
Date: Sun, 8 May 2022 20:30:50 +0100
X-Received-Bytes: 6151
 by: Mr Flibble - Sun, 8 May 2022 19:30 UTC

On Sun, 8 May 2022 15:22:07 -0400
Richard Damon <Richard@Damon-Family.org> wrote:

> On 5/8/22 2:27 PM, Ben wrote:
> > Jeff Barnett <jbb@notatt.com> writes:
> >
> >> On 5/8/2022 7:44 AM, Ben wrote:
> >>> Jeff Barnett <jbb@notatt.com> writes:
> >>>
> >>>> On 5/7/2022 4:21 PM, Ben wrote:
> >>>
> >>>>> 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.
> >>>>
> >>>> Questions:
> >>>>
> >>>> Was 47 million steps a measured or a theoretically computed
> >>>> measure?
> >>> Measured.
> >>>
> >>>> How long would you estimate that a well-written TM interpreter on
> >>>> modern hardware needs to interpret the above? A few seconds or
> >>>> minutes?
> >>> $ time ./tm bb-5-2 ""
> >>> A B C D E H
> >>> 1 1LC 1RB _LE 1LD _LA
> >>> _ 1RB 1RC 1RD 1LA 1RH
> >>> steps=47176874
> >>> real 0m0.237s
> >>> user 0m0.237s
> >>> sys 0m0.000s
> >>> This is a C++ interpreter I've just written so that I can compare
> >>> designs with anything PO produces. I've not worked on making it
> >>> fast though I compiler with -O3 for this test.
> >>> It uses a plain std::string for the tape, so I imagine the
> >>> quality of the C++ library is the key factor (I've not profiled
> >>> it yet). (That table at the start is just the sates transition
> >>> table written in a compact form.)
> >>
> >> Impressive.
> >
> > Thanks, but there's no skill involved, other that not picking any
> > part of the design that looks like a certain loser.
> >
> >> I'm going to conjecture from the rate of interpretation 47M/.237s ~
> >> 200,000,000 states per second that TM definition, your code, and
> >> used library code must have all snuggled into the machine cache.
> >
> > Seems likely.
> >
> >> I'm also
> >> assuming that the C++ code (because of the nature of the
> >> computation) does not lend itself to using multiple cores which
> >> makes the speed all that more impressive.
> >
> > Yes, single core. My laptop is not an old banger (1.6Ghz
> > i5-8256U), but even so I was surprised.
> >
> >> Other questions:
> >>
> >> Did you directly set up a (state X character) -> (quintuple) lookup
> >> rather than doing it in two steps?
> >
> > There's only one lookup, but not that one. In my current design the
> > states are objects that hold a char to triple map, the triple being
> > the character to write, the tape movement, and a pointer to the
> > next state).
> >
> > The inner loop is therefore very tight. I could (probably) speed
> > it up a bit by using an array for that lookup, but I imagined I
> > might like to use fancy Unicode symbols at some stage and a map
> > will work better for that.
>
> My thinking is that there are only two things that have the ability
> to "cost" time. One is tape management, but using an object that acts
> like an array which is indexed in makes this fast except when we need
> to expand it, but that will generally amortize to a small value.
> (Letting the string class do that isn't a bad option).
>
> The second "costly" operation is looking up the rule based on current
> state / tape symbol. For speed this really needs to be O(1) (at least
> amortized). If we reduce our state and input symbols to an internal
> numbering of 0-n an array works great. If we limit our states to
> 'ascii characters' then the 256 x 256 array isn't outlandish in space
> requirements for modern machines.
>
> If you want full Unicode characters, then either you need the
> conversion to a simple 0-n enumeration, or going to a hash table to
> store the rules. The question becomes which cost more the
> input/output conversion to use 0-n values, or hashing (and handling
> the possible collisions).
>
> My thought is that in the 0-n enumeration, the table is "dense" in
> the sense that all non-terminal state will be fully filled out. (And
> terminal states don't actually need an entry, just a value recognized
> as terminal).
>
> >
> >> I don't think that wouldn't make a big difference for this example
> >> but could for TM definitions with much larger quintuple tables.
> >>
> >> Do C++ character arrays (strings?) have provisions to grow if a
> >> char is pushed passed the structure's end?
> >
> > push_back is amortised constant time whereas append and insert give
> > no guarantees. I think glibc goes to some effort to make appending
> > and growing at the front quote efficient.

Have you considered std::deque? Might be worth trying if the tape
sequence isn't small.

/Flibble

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

<t59ag5$ima$1@dont-email.me>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: jbb...@notatt.com (Jeff Barnett)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Date: Sun, 8 May 2022 14:51:14 -0600
Organization: A noiseless patient Spider
Lines: 124
Message-ID: <t59ag5$ima$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>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<zLUdK.4623$arR.255@fx48.iad>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: base64
Injection-Date: Sun, 8 May 2022 20:51:17 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="5cf15a540ae5f944728a0ba2ac83aa75";
logging-data="19146"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/33D49TtX4/7GbFgY3XJoK4HGIJiZcUT8="
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:Fs6zBcDKPORRxidN6QODaTXBxmw=
In-Reply-To: <zLUdK.4623$arR.255@fx48.iad>
Content-Language: en-US
 by: Jeff Barnett - Sun, 8 May 2022 20:51 UTC

On 5/8/2022 1:22 PM, Richard Damon wrote:
> On 5/8/22 2:27 PM, Ben wrote:
>> Jeff Barnett <jbb@notatt.com> writes:
>>
>>> On 5/8/2022 7:44 AM, Ben wrote:
>>>> Jeff Barnett <jbb@notatt.com> writes:
>>>>
>>>>> On 5/7/2022 4:21 PM, Ben wrote:
>>>>
>>>>>> 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.
>>>>>
>>>>> Questions:
>>>>>
>>>>> Was 47 million steps a measured or a theoretically computed measure?
>>>> Measured.
>>>>
>>>>> How long would you estimate that a well-written TM interpreter on
>>>>> modern hardware needs to interpret the above? A few seconds or
>>>>> minutes?
>>>> $ time ./tm bb-5-2 ""
>>>>      A   B   C   D   E   H
>>>> 1 1LC 1RB _LE 1LD _LA
>>>> _ 1RB 1RC 1RD 1LA 1RH
>>>> steps=47176874
>>>> real    0m0.237s
>>>> user    0m0.237s
>>>> sys    0m0.000s
>>>> This is a C++ interpreter I've just written so that I can compare
>>>> designs with anything PO produces.  I've not worked on making it fast
>>>> though I compiler with -O3 for this test.
>>>> It uses a plain std::string for the tape, so I imagine the quality of
>>>> the C++ library is the key factor (I've not profiled it yet).
>>>> (That table at the start is just the sates transition table written
>>>> in a
>>>> compact form.)
>>>
>>> Impressive.
>>
>> Thanks, but there's no skill involved, other that not picking any part
>> of the design that looks like a certain loser.
>>
>>> I'm going to conjecture from the rate of interpretation 47M/.237s ~
>>> 200,000,000 states per second that TM definition, your code, and used
>>> library code must have all snuggled into the machine cache.
>>
>> Seems likely.
>>
>>> I'm also
>>> assuming that the C++ code (because of the nature of the computation)
>>> does not lend itself to using multiple cores which makes the speed all
>>> that more impressive.
>>
>> Yes, single core.  My laptop is not an old banger (1.6Ghz i5-8256U), but
>> even so I was surprised.
>>
>>> Other questions:
>>>
>>> Did you directly set up a (state X character) -> (quintuple) lookup
>>> rather than doing it in two steps?
>>
>> There's only one lookup, but not that one.  In my current design the
>> states are objects that hold a char to triple map, the triple being the
>> character to write, the tape movement, and a pointer to the next state).
>>
>> The inner loop is therefore very tight.  I could (probably) speed it up
>> a bit by using an array for that lookup, but I imagined I might like to
>> use fancy Unicode symbols at some stage and a map will work better for
>> that.
>
> My thinking is that there are only two things that have the ability to
> "cost" time. One is tape management, but using an object that acts like
> an array which is indexed in makes this fast except when we need to
> expand it, but that will generally amortize to a small value. (Letting
> the string class do that isn't a bad option).
>
> The second "costly" operation is looking up the rule based on current
> state / tape symbol. For speed this really needs to be O(1) (at least
> amortized). If we reduce our state and input symbols to an internal
> numbering of 0-n an array works great. If we limit our states to 'ascii
> characters' then the 256 x 256 array isn't outlandish in space
> requirements for modern machines.
>
> If you want full Unicode characters, then either you need the conversion
> to a simple 0-n enumeration, or going to a hash table to store the
> rules. The question becomes which cost more the input/output conversion
> to use 0-n values, or hashing (and handling the possible collisions).
>
> My thought is that in the 0-n enumeration, the table is "dense" in the
> sense that all non-terminal state will be fully filled out. (And
> terminal states don't actually need an entry, just a value recognized as
> terminal).
Why not just "compile" the tuples into a graph? Take all the tuples
defined by one state and sort them on current character and look up by
binary search. If you have a truly large character set and many states
have lots of out-branches, then organize the nodes using hash tables as
you suggest.
It's interesting to note that many Common Lisp make such representation
decisions under the table especially for sorting and hashing. For
example sorting chooses from n^2 complexity sorting for short sequences
to n*log(n) varieties as the input is longer. Hashing starts with just a
linear list and linear time searching for small tables and switches
representations to arrays when the number of elements increase. Many of
these strategies use strategies depending on the comparison predicate.
All of these morphs are swept under the rug by using its object system
and dynamic ability to morph structures, dynamically, to different types.
>
>>
>>> I don't think that wouldn't make a big difference for this example but
>>> could for TM definitions with much larger quintuple tables.
>>>
>>> Do C++ character arrays (strings?) have provisions to grow if a char
>>> is pushed passed the structure's end?
>>
>> push_back is amortised constant time whereas append and insert give no
>> guarantees.  I think glibc goes to some effort to make appending and
>> growing at the front quote efficient.
>>
>>> I'm thinking of Lisp arrays with
>>> fill pointers as an example. To ask the question a different way which
>>> of the following did you do to set the initial size of the "tape":
>>> determine empirically, start arbitrarily and let the C++ system
>>> run-time grow the structure as needed, or start arbitrarily and use
>>> your own code to deal with the issue?
>>
>> My code is utterly trivial.  The tape is a std::string to which I assign
>> the input.  All that happens after that is that tape[head] is assigned
>> to, and the string is grown by one blank, either at the front or the
>> back, if the tape movement requires it.
>>
>> I'll post the code when the time comes if case anyone cares to see it.
>>
>> I plan to do a Haskell version too.  I used to have one, but that got
>> lost in retirement.--
Jeff Barnett

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

<zZCdnSj9ucP93-X_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!rocksolid2!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 08 May 2022 17:21:20 -0500
Date: Sun, 8 May 2022 17:21:18 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ priorities ]
Content-Language: en-US
Newsgroups: comp.theory
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>
<9f101e19-e941-45da-abf4-8a63b362347an@googlegroups.com>
<87y1zdvutz.fsf@bsb.me.uk> <lMydne2Ercz5n-r_nZ2dnUU7_8zNnZ2d@giganews.com>
<5695f271-7534-4b2a-9454-fb83987b322fn@googlegroups.com>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <5695f271-7534-4b2a-9454-fb83987b322fn@googlegroups.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <zZCdnSj9ucP93-X_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 55
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-pwlS6+bUXNvhBSMDAlh5n1e+7XrF0HNBrxXUlKANwfaPrGyur6ukFOVHEYAkrNZ/UgSQ0zrGEQe07Oe!tdM03r4WIdlXDWd3viMQan83B+NkVjKtvafnINdDyRgYi8mmlpo2jBg5vcr2QGiPO35TW2XQEvQ=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3879
 by: olcott - Sun, 8 May 2022 22:21 UTC

On 5/8/2022 4:39 AM, Malcolm McLean wrote:
> On Sunday, 8 May 2022 at 00:36:12 UTC+1, olcott wrote:
>> On 5/7/2022 5:31 PM, Ben wrote:
>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>
>>>> 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.
>>>
>>> I wonder... Let's see. There no clear sign in the current sketches
>>> that he can make it work.
>>>
>> I got everything working besides:
>> bool Quintuple_List::transition_function(std::set<Quintuple>::iterator&
>> current_quintuple)
>>
>> I knew this would be the hardest part. I also got the other TM
>> interpreter to work correctly. Setting the tape manually is trivial.
>> I am reviewing other sources for how state transitions work.
>>
> The easiest way to make a set do what you want is to overload the '<' operator
> for struct Quintuple.
> Then you fill a blank Quintuple with the state and input symbol, and call
> the "find" method on the set to retrive the full Quintuple.
>
> It's a fairly horrid interface, but that's C++.

Yes that is the way that I did it.
David S. Woodruff simply does a linear search.

When I am refraining from doing work on Sunday, responding to your posts
has a higher priority than responding to anyone else's posts because you
are my only reviewer that has been consistently honest.

All of my other reviewers have at least a very strong bias for rebuttal
thus causing an honest dialogue to have much less priority.

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

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

 copy mid

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

 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: Mon, 09 May 2022 03:14:19 +0100
Organization: A noiseless patient Spider
Lines: 17
Message-ID: <87ee13sb9g.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> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <zVNdK.10345$Awz.6657@fx03.iad>
<8783735f-7f11-4914-9724-044c3b57831en@googlegroups.com>
<87fslju9xv.fsf@bsb.me.uk>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="618c43d03445855480f9653e38dab192";
logging-data="16191"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+hWXDzIWcJutBq+OjLiG3q+2uRBR76Wsk="
Cancel-Lock: sha1:QObkwbbOhv84otJougZmqeL7FWo=
sha1:Wh+b3sGIY8OLrQWpWdjYpG620AY=
X-BSB-Auth: 1.eb14e6da32d5e6b6aa02.20220509031419BST.87ee13sb9g.fsf@bsb.me.uk
 by: Ben - Mon, 9 May 2022 02:14 UTC

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

> With tracing turned on, my simple implementation shows this for the
> BB(4) champion:
>
> $ ./simple-tm bb-4-2 ""
> A B C D H
> 1 1LB _LC 1LD _RA
> _ 1RB 1LA 1RH 1RD
> ________________________________[A|_]_________________________________
> ________________________________[B|_]_________________________________

There was a bug (now fixed) so that when the initial tape is empty there
would be a couple of false transitions.

--
Ben.

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

<ePKdnciMLI1qEeX_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 08 May 2022 22:39:35 -0500
Date: Sun, 8 May 2022 22:39:33 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
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> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <zVNdK.10345$Awz.6657@fx03.iad>
<8783735f-7f11-4914-9724-044c3b57831en@googlegroups.com>
<87fslju9xv.fsf@bsb.me.uk> <87ee13sb9g.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87ee13sb9g.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <ePKdnciMLI1qEeX_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 29
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-hwY/mXd1V4hTo0ma6jUlGewxEDskTPOfk+DqqAzdCUfXBcVY+m6TaxEpOHMV88rt75RvJug4CM+z1Yo!jSnB/fJabcgJ0dK/vvQuaIQwHAZGauxRP1zsNwIB3/a/Wq8VoK9dOsY54rsfl0QvmVqIF9Nq3eQ=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2511
 by: olcott - Mon, 9 May 2022 03:39 UTC

On 5/8/2022 9:14 PM, Ben wrote:
> Ben <ben.usenet@bsb.me.uk> writes:
>
>> With tracing turned on, my simple implementation shows this for the
>> BB(4) champion:
>>
>> $ ./simple-tm bb-4-2 ""
>> A B C D H
>> 1 1LB _LC 1LD _RA
>> _ 1RB 1LA 1RH 1RD
>> ________________________________[A|_]_________________________________
>> ________________________________[B|_]_________________________________
>
> There was a bug (now fixed) so that when the initial tape is empty there
> would be a couple of false transitions.
>

Mine is almost working.
I got David S. Woodruff's TM.exe to show me the trace
that I am supposed to get on his paren.tm program.

My TM.cpp does the first four steps of this correctly.

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

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

 copy mid

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

 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: Mon, 09 May 2022 12:36:44 +0100
Organization: A noiseless patient Spider
Lines: 47
Message-ID: <878rrbrl83.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> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <zVNdK.10345$Awz.6657@fx03.iad>
<8783735f-7f11-4914-9724-044c3b57831en@googlegroups.com>
<87fslju9xv.fsf@bsb.me.uk> <87ee13sb9g.fsf@bsb.me.uk>
<ePKdnciMLI1qEeX_nZ2dnUU7_8zNnZ2d@giganews.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="618c43d03445855480f9653e38dab192";
logging-data="7247"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/5uxSXUc084ZIDBbxRRfj00nz1meGguS8="
Cancel-Lock: sha1:ATI6mVi9mRY2IlcXSQR7rXxGZmA=
sha1:WrTR7shWTy3DBBVp5EpUMk4pRFQ=
X-BSB-Auth: 1.a5fc0eb68e9f1031aeb8.20220509123644BST.878rrbrl83.fsf@bsb.me.uk
 by: Ben - Mon, 9 May 2022 11:36 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/8/2022 9:14 PM, Ben wrote:
>> Ben <ben.usenet@bsb.me.uk> writes:
>>
>>> With tracing turned on, my simple implementation shows this for the
>>> BB(4) champion:
>>>
>>> $ ./simple-tm bb-4-2 ""
>>> A B C D H
>>> 1 1LB _LC 1LD _RA
>>> _ 1RB 1LA 1RH 1RD
>>> ________________________________[A|_]_________________________________
>>> ________________________________[B|_]_________________________________
>> There was a bug (now fixed) so that when the initial tape is empty there
>> would be a couple of false transitions.
>
> Mine is almost working.
> I got David S. Woodruff's TM.exe to show me the trace
> that I am supposed to get on his paren.tm program.

If you want, I can provide traces for testing. My interpreter takes a
trace format argument so there's a reasonable chance I can make traces
similar to yours.

> My TM.cpp does the first four steps of this correctly.

A reasonable test would be if you get the same number of steps for BB(4)
and BB(5). BB(4) is (as above)

A B C D H
1 1LB _LC 1LD _RA
_ 1RB 1LA 1RH 1RD

and BB(5) is

A B C D E H
1 1LC 1RB _LE 1LD _LA
_ 1RB 1RC 1RD 1LA 1RH

BB(4) halts after 107 steps. B(5) halts after 47176870 steps.
Obviously the output could also be compared.

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

<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 09 May 2022 10:18:30 -0500
Date: Mon, 9 May 2022 10:18:29 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
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> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87tu9zubfs.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 122
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-Mso9qHsfQpuhJituyM2X3FbiPPRZ50uDCvWE42xX7u6n+kgBMblEXGX1oHPxOOYmcz4XvGor2WaTJSK!9uhtBiEb9OJ6SxQSbVe5dmtpUA5FJJxZbf9/KEFYLHXkkHraFiht9qeR8n1Cn+NtsoTGV4Tj408=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 5992
 by: olcott - Mon, 9 May 2022 15:18 UTC

On 5/8/2022 1:27 PM, Ben wrote:
> Jeff Barnett <jbb@notatt.com> writes:
>
>> On 5/8/2022 7:44 AM, Ben wrote:
>>> Jeff Barnett <jbb@notatt.com> writes:
>>>
>>>> On 5/7/2022 4:21 PM, Ben wrote:
>>>
>>>>> 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.
>>>>
>>>> Questions:
>>>>
>>>> Was 47 million steps a measured or a theoretically computed measure?
>>> Measured.
>>>
>>>> How long would you estimate that a well-written TM interpreter on
>>>> modern hardware needs to interpret the above? A few seconds or
>>>> minutes?
>>> $ time ./tm bb-5-2 ""
>>> A B C D E H
>>> 1 1LC 1RB _LE 1LD _LA
>>> _ 1RB 1RC 1RD 1LA 1RH
>>> steps=47176874
>>> real 0m0.237s
>>> user 0m0.237s
>>> sys 0m0.000s
>>> This is a C++ interpreter I've just written so that I can compare
>>> designs with anything PO produces. I've not worked on making it fast
>>> though I compiler with -O3 for this test.
>>> It uses a plain std::string for the tape, so I imagine the quality of
>>> the C++ library is the key factor (I've not profiled it yet).
>>> (That table at the start is just the sates transition table written in a
>>> compact form.)
>>
>> Impressive.
>
> Thanks, but there's no skill involved, other that not picking any part
> of the design that looks like a certain loser.
>
>> I'm going to conjecture from the rate of interpretation 47M/.237s ~
>> 200,000,000 states per second that TM definition, your code, and used
>> library code must have all snuggled into the machine cache.
>
> Seems likely.
>
>> I'm also
>> assuming that the C++ code (because of the nature of the computation)
>> does not lend itself to using multiple cores which makes the speed all
>> that more impressive.
>
> Yes, single core. My laptop is not an old banger (1.6Ghz i5-8256U), but
> even so I was surprised.
>
>> Other questions:
>>
>> Did you directly set up a (state X character) -> (quintuple) lookup
>> rather than doing it in two steps?
>
> There's only one lookup, but not that one. In my current design the
> states are objects that hold a char to triple map, the triple being the
> character to write, the tape movement, and a pointer to the next state).
>
> The inner loop is therefore very tight. I could (probably) speed it up
> a bit by using an array for that lookup, but I imagined I might like to
> use fancy Unicode symbols at some stage and a map will work better for
> that.
>
>> I don't think that wouldn't make a big difference for this example but
>> could for TM definitions with much larger quintuple tables.
>>
>> Do C++ character arrays (strings?) have provisions to grow if a char
>> is pushed passed the structure's end?
>
> push_back is amortised constant time whereas append and insert give no
> guarantees. I think glibc goes to some effort to make appending and
> growing at the front quote efficient.
>
>> I'm thinking of Lisp arrays with
>> fill pointers as an example. To ask the question a different way which
>> of the following did you do to set the initial size of the "tape":
>> determine empirically, start arbitrarily and let the C++ system
>> run-time grow the structure as needed, or start arbitrarily and use
>> your own code to deal with the issue?
>
> My code is utterly trivial. The tape is a std::string to which I assign
> the input. All that happens after that is that tape[head] is assigned
> to, and the string is grown by one blank, either at the front or the
> back, if the tape movement requires it.
>

Conventionally tapes have an actual beginning, yet no fixed end.

> I'll post the code when the time comes if case anyone cares to see it.
>
> I plan to do a Haskell version too. I used to have one, but that got
> lost in retirement.
>

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

<0YCdnaiQZ9yHrOT_nZ2dnUU7_8xQAAAA@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 09 May 2022 10:19:54 -0500
Date: Mon, 9 May 2022 10:19:54 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
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> <87a6btx9uz.fsf@bsb.me.uk>
<B4Cdnb1LsNSkuOr_nZ2dnUU7_83NnZ2d@giganews.com> <87zgjst9v9.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87zgjst9v9.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <0YCdnaiQZ9yHrOT_nZ2dnUU7_8xQAAAA@giganews.com>
Lines: 17
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-UwRz8NPhURSM076uxRa83bvzttDNRTTIkHB8ApAXibuiLZW3OT26nTZ2jiJY7CqmyBsL2UoUP8nljQo!1X1tiYUijNzdlnLSFi4qx0Hb0yQ+2LYcmfjTpEJl5JxTzBRjSqC51bqo54v4q1YuM06CZuwdUaQ=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 1981
 by: olcott - Mon, 9 May 2022 15:19 UTC

On 5/8/2022 8:46 AM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> The TM interpreter uses linear search, I hate that, it doesn't scale.
>
> What do you use linear search for? I thought the key structure you used
> was a std::set.
>

David S. Woodruff's TM interpretor uses linear search.

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

<Rv-dndpesPZLqeT_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 09 May 2022 10:35:50 -0500
Date: Mon, 9 May 2022 10:35:50 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <t559aq$jj2$1@dont-email.me>
<t565tt$6fe$1@dont-email.me> <t580lc$i4f$1@dont-email.me>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <t580lc$i4f$1@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <Rv-dndpesPZLqeT_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 40
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-OSHpwu+gLaz34BOz/A0n2Bg8DET3Rvlp4rFc4IkbXfLumpQQo7QaJwEi6k9I8ZFVMgK0E676pvcElDo!3bNBvFxth0THzReEL9HhbJzBdCht67ii6jXQDKhHt/AetZHHkBq9he4Ji/2zlXdDJjIrSijiC+g=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2588
 by: olcott - Mon, 9 May 2022 15:35 UTC

On 5/8/2022 3:57 AM, Mikko wrote:
> On 2022-05-07 16:14:50 +0000, olcott said:
>
>> On 5/7/2022 3:06 AM, Mikko wrote:
>>> On 2022-05-06 20:53:58 +0000, olcott said:
>
>>>> 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'.
>
> Where in the spec is the requirement that there be a function from
> int and int to std::set<Quintuple>::iterator that is named NextState?
>
> Mikko
>

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'.
http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt

--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

Pages:12345678
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor