Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

Don't hit the keys so hard, it hurts.


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

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 [ best tape]

<cr-dnW5GGv7kYuf_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 10 May 2022 19:12:41 -0500
Date: Tue, 10 May 2022 19:12:39 -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 [ best tape]
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>
<zLUdK.4623$arR.255@fx48.iad> <20220508203050.00001cd7@reddwarf.jmc>
<sdydnYLI-KSQpOT_nZ2dnUU7_81g4p2d@giganews.com> <87wneuqryi.fsf@bsb.me.uk>
<XcmdnbaZ-aTnC-T_nZ2dnUU7_83NnZ2d@giganews.com> <87r152mdd2.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87r152mdd2.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <cr-dnW5GGv7kYuf_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 42
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-Eag7fn4kS6eeCFUTmw0JvJsyvtSWiB8pD9dGO9DR7zBUuZEaN6G6MjrMBvFVJ80pDLi3fJDwNTf6n27!F3jqjyadYH70EFBbMh4yxRq5244ImUQjLurTEuidI/PxF9FPUmtxJ5frJCdtFMZFBWRwV9qRVeo=
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: 3303
X-Received-Bytes: 3394
 by: olcott - Wed, 11 May 2022 00:12 UTC

On 5/9/2022 7:37 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/9/2022 5:08 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> The classic TM is not allowed to move before its beginning thus a
>>>> std::vector is best for the tape.
>>> In the usual definition the tape has no beginning so I can't make out
>>> what you are saying here. Something about it is wrong but I tell
>>> exactly what.
>>>
>> Linz agrees with you, Kozen agrees with me and I can't find where
>> Sipser specifies this.
>
> The definition is simpler if the tape in unbounded at both ends. If you
> are going to use any of the BB candidates as tests, you need a tape open
> at both ends.
>

You have convinced me that this is the best way I am going to implement
this using David kleinecke's solution. It is a much more efficient and
simpler way to implement push_back() and push_front() than std::deque
that also has none of the pitfalls such as:

https://www.cplusplus.com/reference/deque/deque/push_front/
All iterators related to this container are invalidated.

> Given that you've gone for a one-ended tape, what rule do you apply when
> the transition function specifies going left from the left-most cell?
>
> I've modified my implementation to do either, just in case we end up
> comparing traces.
>

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

<8vydnYgTy7nRm-b_nZ2dnUU7_8xh4p2d@giganews.com>

 copy mid

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

 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: Tue, 10 May 2022 19:41:47 -0500
Date: Tue, 10 May 2022 19:41:47 -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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220510190118.00006b59@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <8vydnYgTy7nRm-b_nZ2dnUU7_8xh4p2d@giganews.com>
Lines: 114
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-0PEfYasG1LGjJX0g14TQpzcDpgDzHMlVge5ZRVpyO+VNT1qn5cIJ6Kpa0SVJQ/wlWTiE33/fIA+h35p!DvPHM9S0EEVKLZEdSKmvxn9eYxqHfgrpmrZicjgKZef7DW9qKmtb0djmOBc6ZGv0+e29JlcRZw0=
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: 6647
 by: olcott - Wed, 11 May 2022 00:41 UTC

On 5/10/2022 1:01 PM, Mr Flibble wrote:
> On Tue, 10 May 2022 16:41:28 +0100
> Ben <ben.usenet@bsb.me.uk> wrote:
>
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>>
>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>
>>>>>>>>>>>> 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.
>>>>>>>>>>
>>>>>>>>>> No.
>>>>>>>>>
>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>
>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>> however, that that is not the case.
>>>>>>>
>>>>>>> How would you define conventional?
>>>>>>
>>>>>> "the accepted or traditional method of doing something"
>>>>>>
>>>>>>> The most typical use is one way unlimited, right?
>>>>>>
>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>> commonly used in modern presentations, but the only real way to
>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>> that.
>>>>>>
>>>>>> From a technical point of view, double-open is clearly
>>>>>> preferable as it removes a special case with no technical
>>>>>> down-side.
>>>>> There's a technical downside if you implement the tape in the
>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>> fast to append characters to the buffer's end.
>>>> I meant for the theory of such machines. It's the theory and the
>>>> theorems that will dictate which style an authors chooses and
>>>> there's no down-side in that context.
>>>>
>>>>> There's usually spare memory there in the system, so
>>>>> the push_back() operation is just a case of incrementing a size
>>>>> field.
>>>> If you do the resizing right, the same is true of push_front().
>>>>
>>>>> push_front(), however, generally requires a push_back, followed
>>>>> by a move for the entire buffer.
>>>> Every now and then, your realloc will need an extra move, but
>>>> that's a cost that will be amortised if you do the usual
>>>> exponential resizing.
>>>>> There are ways round this, of course, but you have to know what
>>>>> you are doing, and it's not as easy to write.
>>>>
>>>> Gosh, you have a low opinion of what's generally understood!
>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>> other or even both ends seems to me to be utterly trivial.
>>>
>>> https://en.cppreference.com/w/cpp/container/deque
>>> push_back adds an element to the end
>>> push_front inserts an element to the beginning
>>
>> I think everyone here knows that.
>>
>> Using std::deque was suggested before (by Jeff I think), but at nearly
>> 200 million steps a second, I didn't think there was much room for a
>> speed-up.
>>
>> I've just tried it, and using std::deque rather than std::string slows
>> my implementation down to 106 million steps a second, and it doesn't
>> simplify the logic at all. In fact, the few places where you really
>> want a string get a bit more fiddly.
>>
>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>> champions.
>
> std::string (or std::vector) will likely win for small N and std::deque
> for large N as far as push_front is concerned.
>
> /Flibble
>

David kleinecke's solution is a much more efficient and simpler way to
implement push_back() and push_front() than std::deque that also has
none of the pitfalls such as:

https://www.cplusplus.com/reference/deque/deque/push_front/
All iterators related to this container are invalidated.

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

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

 copy mid

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

 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: Wed, 11 May 2022 01:42:48 +0100
Organization: A noiseless patient Spider
Lines: 137
Message-ID: <87bkw4lx13.fsf@bsb.me.uk>
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com>
<87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
<87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_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="0e1d4fd29744a738b604ac23bca2b355";
logging-data="5308"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX191CpRURLOU0yjZ6YOQ3LwOrWGbtpste/I="
Cancel-Lock: sha1:xdZ8eXhGSqk9KW/7T359G15kqXs=
sha1:MLfHVVIO00lBT/bLSmEIkGy6yVI=
X-BSB-Auth: 1.434a9b49649539f9be4b.20220511014248BST.87bkw4lx13.fsf@bsb.me.uk
 by: Ben - Wed, 11 May 2022 00:42 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>> On Tue, 10 May 2022 16:41:28 +0100
>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>
>>>> olcott <No...@NoWhere.com> writes:
>>>>
>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>
>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>
>>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>
>>>>>>>>>>>> No.
>>>>>>>>>>>
>>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>>
>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>> however, that that is not the case.
>>>>>>>>>
>>>>>>>>> How would you define conventional?
>>>>>>>>
>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>
>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>
>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>>> that.
>>>>>>>>
>>>>>>>> From a technical point of view, double-open is clearly
>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>> down-side.
>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>> fast to append characters to the buffer's end.
>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>> theorems that will dictate which style an authors chooses and
>>>>>> there's no down-side in that context.
>>>>>>
>>>>>>> There's usually spare memory there in the system, so
>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>> field.
>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>
>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>> by a move for the entire buffer.
>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>> that's a cost that will be amortised if you do the usual
>>>>>> exponential resizing.
>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>> you are doing, and it's not as easy to write.
>>>>>>
>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>
>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>> push_back adds an element to the end
>>>>> push_front inserts an element to the beginning
>>>>
>>>> I think everyone here knows that.
>>>>
>>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>>> 200 million steps a second, I didn't think there was much room for a
>>>> speed-up.
>>>>
>>>> I've just tried it, and using std::deque rather than std::string slows
>>>> my implementation down to 106 million steps a second, and it doesn't
>>>> simplify the logic at all. In fact, the few places where you really
>>>> want a string get a bit more fiddly.
>>>>
>>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>>> champions.
>>> std::string (or std::vector) will likely win for small N and std::deque
>>> for large N as far as push_front is concerned.
>>>
>>> /Flibble
>> If you are not actually implementing a machine replacing the tape by
>> a pair of stacks is attractive. Actually you replace the tape by
>> three things - two stacks (called for example left and right) and a
>> single focus cell.

I've tried both (two stacks and two stacks and a cell) and I think the
extra cell just makes it a bit fussy.

If you have an array of two stacks:

stack<symbol> tape[2];

and 'dir' is the move direction as 0 or 1, then

tape[dir].push(tape[!dir].pop())

is the move operation. Reading the tape cell is done just once per
step, so tape[0].top() is not going to be expensive.

>> But none of this is really needed. We don't really need TM's for anything
>> practical.
>
> This is the best idea yet. I spent all day researching this
> on my cell phone during chemotherapy infusion.
>
> I am implemented this idea in code and will post it as another
> reply to your message.

My Haskell TM interpreter did it this way with a pair of strings
(Haskell strings are essentially stacks). But I've lost the code. I
might have time to re-create it.

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

<8vydnYsTy7kxm-b_nZ2dnUU7_8xh4p2d@giganews.com>

 copy mid

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

 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: Tue, 10 May 2022 19:43:24 -0500
Date: Tue, 10 May 2022 19:43:23 -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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <t5e902$61j$1@dont-email.me>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <t5e902$61j$1@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <8vydnYsTy7kxm-b_nZ2dnUU7_8xh4p2d@giganews.com>
Lines: 129
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-XhoShjlJsx+pX+XbORFbvYaCPvm6IeSA5MW6ABdiDF1DSMzZPP0Vw5VtpmMTsE+hRGD3t+/Bvt0m5YR!mMF/iaqOuY9KODJ8dj7XwZsrPzDOoGUMeU16W3lBCo2PfrTXkcWGIkZq83/qgx7BY4E8FYnGxgo=
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: 7338
 by: olcott - Wed, 11 May 2022 00:43 UTC

On 5/10/2022 12:56 PM, Jeff Barnett wrote:
> On 5/10/2022 9:41 AM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>>
>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>
>>>>>>>>>>>> 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.
>>>>>>>>>>
>>>>>>>>>> No.
>>>>>>>>>
>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>
>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>> certain is
>>>>>>>> that if there were a convention, an author not using that
>>>>>>>> convention
>>>>>>>> should say as much. You'll find, however, that that is not the
>>>>>>>> case.
>>>>>>>
>>>>>>> How would you define conventional?
>>>>>>
>>>>>> "the accepted or traditional method of doing something"
>>>>>>
>>>>>>> The most typical use is one way unlimited, right?
>>>>>>
>>>>>> I don't know. I know it's not a widely agreed convention, but what it
>>>>>> "typical" is hard to assess. I think double-open is more commonly
>>>>>> used in
>>>>>> modern presentations, but the only real way to know would be to do a
>>>>>> survey and I don't think the topic merits that.
>>>>>>
>>>>>>   From a technical point of view, double-open is clearly
>>>>>> preferable as it
>>>>>> removes a special case with no technical down-side.
>>>>>>
>>>>> There's a technical downside if you implement the tape in the
>>>>> obvious way,
>>>>> as a dynamic buffer. Most languages make it quite fast to append
>>>>> characters
>>>>> to the buffer's end.
>>>> I meant for the theory of such machines.  It's the theory and the
>>>> theorems that will dictate which style an authors chooses and
>>>> there's no
>>>> down-side in that context.
>>>>
>>>>> There's usually spare memory there in the system, so
>>>>> the push_back() operation is just a case of incrementing a size field.
>>>> If you do the resizing right, the same is true of push_front().
>>>>
>>>>> push_front(), however, generally requires a push_back, followed by
>>>>> a move
>>>>> for the entire buffer.
>>>> Every now and then, your realloc will need an extra move, but that's a
>>>> cost that will be amortised if you do the usual exponential resizing.
>>>>
>>>>> There are ways round this, of course, but you have to know what you
>>>>> are doing, and it's not as easy to write.
>>>>
>>>> Gosh, you have a low opinion of what's generally understood!  Maybe I
>>>> have too high an opinion, but growing a buffer at one or other or even
>>>> both ends seems to me to be utterly trivial.
>>>
>>> https://en.cppreference.com/w/cpp/container/deque
>>> push_back adds an element to the end
>>> push_front inserts an element to the beginning
>>
>> I think everyone here knows that.
>>
>> Using std::deque was suggested before (by Jeff I think), but at nearly
>> 200 million steps a second, I didn't think there was much room for a
>> speed-up.
>>
>> I've just tried it, and using std::deque rather than std::string slows
>> my implementation down to 106 million steps a second, and it doesn't
>> simplify the logic at all.  In fact, the few places where you really
>> want a string get a bit more fiddly.
>>
>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>> champions.
>
> One possibility is to use a linked list where each node contains a
> character, a pointer to the following node, and a pointer to the
> previous node. Since the TM can only move one tape square per state
> transition, the > cache will do a good job of speeding things up. Of
> course storage per character is more and that will slow things down.
>
> Another way to make tape storage almost all characters is to allocate a
> block (page sized) at a time with one block initially. A block is
> allocated each time you are about to go off either the front or back end
> and is linked. The cache hit ratio is extremely good and only a tiny
> fraction less then using a big array. It wins, however, when growing an
> array would cause you to move it.

David kleinecke's solution is a much more efficient and simpler way to
implement push_back() and push_front() than std::deque that also has
none of the pitfalls such as:

https://www.cplusplus.com/reference/deque/deque/push_front/
All iterators related to this container are invalidated.

I consider it an optimal solution and the one that I am implementing.

--
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 [ best tape ]

<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 10 May 2022 20:12:18 -0500
Date: Tue, 10 May 2022 20:12:17 -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 [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87bkw4lx13.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 133
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-tL63aHZNgKnfNDDGVDaCvCf3vZ9DCz0f6VohVgGbEpNIsdXFaR380IwCLHK2rSctzH3D1vX130xltGL!k/NtEZ+vFN1Hzhe/CQLnB2j2UJily1DygHqTcYQKcYOwJL77NvNBQMhYOwNQls1RW+PJ0/bJbJo=
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: 7426
X-Received-Bytes: 7517
 by: olcott - Wed, 11 May 2022 01:12 UTC

On 5/10/2022 7:42 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>>> On Tue, 10 May 2022 16:41:28 +0100
>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>
>>>>> olcott <No...@NoWhere.com> writes:
>>>>>
>>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>
>>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>
>>>>>>>>>>>>> No.
>>>>>>>>>>>>
>>>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>>>
>>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>>> however, that that is not the case.
>>>>>>>>>>
>>>>>>>>>> How would you define conventional?
>>>>>>>>>
>>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>>
>>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>>
>>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>>>> that.
>>>>>>>>>
>>>>>>>>> From a technical point of view, double-open is clearly
>>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>>> down-side.
>>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>>> fast to append characters to the buffer's end.
>>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>>> theorems that will dictate which style an authors chooses and
>>>>>>> there's no down-side in that context.
>>>>>>>
>>>>>>>> There's usually spare memory there in the system, so
>>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>>> field.
>>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>>
>>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>>> by a move for the entire buffer.
>>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>>> that's a cost that will be amortised if you do the usual
>>>>>>> exponential resizing.
>>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>>> you are doing, and it's not as easy to write.
>>>>>>>
>>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>>
>>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>>> push_back adds an element to the end
>>>>>> push_front inserts an element to the beginning
>>>>>
>>>>> I think everyone here knows that.
>>>>>
>>>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>>>> 200 million steps a second, I didn't think there was much room for a
>>>>> speed-up.
>>>>>
>>>>> I've just tried it, and using std::deque rather than std::string slows
>>>>> my implementation down to 106 million steps a second, and it doesn't
>>>>> simplify the logic at all. In fact, the few places where you really
>>>>> want a string get a bit more fiddly.
>>>>>
>>>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>>>> champions.
>>>> std::string (or std::vector) will likely win for small N and std::deque
>>>> for large N as far as push_front is concerned.
>>>>
>>>> /Flibble
>>> If you are not actually implementing a machine replacing the tape by
>>> a pair of stacks is attractive. Actually you replace the tape by
>>> three things - two stacks (called for example left and right) and a
>>> single focus cell.
>
> I've tried both (two stacks and two stacks and a cell) and I think the
> extra cell just makes it a bit fussy.
>

std::vector <is> essentially a stack.

struct Tape
{ unsigned int Tape_Head;
std::vector<unsigned char> Left;
std::vector<unsigned char> Right;
unsigned int move_left();
unsigned int move_right();
};

Tape_Head is mapped to its location in Left or Right.
I am still working out the details of this part.

--
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 [ best tape ]

<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>

 copy mid

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

 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!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 10 May 2022 21:05:30 -0500
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Newsgroups: comp.theory
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
From: news.dea...@darjeeling.plus.com (Mike Terry)
Date: Wed, 11 May 2022 03:05:29 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.7.1
MIME-Version: 1.0
In-Reply-To: <QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
Lines: 143
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-XRSvHRuwcxvJBNHyjpZ5kNByFjgN6Jh9N5TgprBT9mS6HLmEE8itDN/EFdSZ8f4+3oEA9uNkbrRkN3U!ZLskA2nR44JK++zNEikeKvWd0hbNLkPwlqo9JbyrR1RW3q5mTWNL/ppkHWfee3/iky/34tSrPvQt!gRQz3dj9MjrYm9DQ1cre98Y9aP4=
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: 8299
 by: Mike Terry - Wed, 11 May 2022 02:05 UTC

On 11/05/2022 02:12, olcott wrote:
> On 5/10/2022 7:42 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>>>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>>>> On Tue, 10 May 2022 16:41:28 +0100
>>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>>
>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>>
>>>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>
>>>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> No.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>>>>
>>>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>>>> however, that that is not the case.
>>>>>>>>>>>
>>>>>>>>>>> How would you define conventional?
>>>>>>>>>>
>>>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>>>
>>>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>>>
>>>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>>>>> that.
>>>>>>>>>>
>>>>>>>>>>   From a technical point of view, double-open is clearly
>>>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>>>> down-side.
>>>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>>>> fast to append characters to the buffer's end.
>>>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>>>> theorems that will dictate which style an authors chooses and
>>>>>>>> there's no down-side in that context.
>>>>>>>>
>>>>>>>>> There's usually spare memory there in the system, so
>>>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>>>> field.
>>>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>>>
>>>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>>>> by a move for the entire buffer.
>>>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>>>> that's a cost that will be amortised if you do the usual
>>>>>>>> exponential resizing.
>>>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>>>> you are doing, and it's not as easy to write.
>>>>>>>>
>>>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>>>
>>>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>>>> push_back adds an element to the end
>>>>>>> push_front inserts an element to the beginning
>>>>>>
>>>>>> I think everyone here knows that.
>>>>>>
>>>>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>>>>> 200 million steps a second, I didn't think there was much room for a
>>>>>> speed-up.
>>>>>>
>>>>>> I've just tried it, and using std::deque rather than std::string slows
>>>>>> my implementation down to 106 million steps a second, and it doesn't
>>>>>> simplify the logic at all. In fact, the few places where you really
>>>>>> want a string get a bit more fiddly.
>>>>>>
>>>>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>>>>> champions.
>>>>> std::string (or std::vector) will likely win for small N and std::deque
>>>>> for large N as far as push_front is concerned.
>>>>>
>>>>> /Flibble
>>>> If you are not actually implementing a machine replacing the tape by
>>>> a pair of stacks is attractive. Actually you replace the tape by
>>>> three things - two stacks (called for example left and right) and a
>>>> single focus cell.
>>
>> I've tried both (two stacks and two stacks and a cell) and I think the
>> extra cell just makes it a bit fussy.
>>
>
> std::vector <is> essentially a stack.
>
> struct Tape
> {
>   unsigned int Tape_Head;
>   std::vector<unsigned char> Left;
>   std::vector<unsigned char> Right;
>   unsigned int move_left();
>   unsigned int move_right();
> };
>
> Tape_Head is mapped to its location in Left or Right.
> I am still working out the details of this part.
>

I think you've misunderstood DK's and Ben's approaches. I think what you're suggesting is that Left
handles all the "negative" tape head positions, and Right all the "positive" ones, while Tape_Head
contains the tape head index (positive or negative) which changes by 1 each time the head moves?

DK and Ben propose two stacks, and with this approach the tape head is effectively always in a fixed
place "in between the two stacks", or (with Ben's) at the top of [say] the left stack. So there is
no Tape_Head index to track.

But what you suggest is quite workable...

I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a
comfortably large chosen page size. (But efficiency really isn't an issue for this task!)

Mike.

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

<ecadnXdd_YWih-b_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

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

 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: Tue, 10 May 2022 21:06:55 -0500
Date: Tue, 10 May 2022 21:06: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>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <ecadnXdd_YWih-b_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 130
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-QSKs6soaJsUoX9AVrLhwd+bJJPSbOh34g9exwaQT2kRPYgKVM8ylunNjmxMUj1B6kyxE+6PAZFrApHn!CDK2D0rp4ystBVqr9XahBzUR3P6epB+5UlgjpezG/EdI5KwTplqmMRxiqseMcooHEAu7KzCPG/c=
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: 7247
 by: olcott - Wed, 11 May 2022 02:06 UTC

On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>> On Tue, 10 May 2022 16:41:28 +0100
>> Ben <ben.u...@bsb.me.uk> wrote:
>>
>>> olcott <No...@NoWhere.com> writes:
>>>
>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>
>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>
>>>>>>>>>>>>> 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.
>>>>>>>>>>>
>>>>>>>>>>> No.
>>>>>>>>>>
>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>
>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>> however, that that is not the case.
>>>>>>>>
>>>>>>>> How would you define conventional?
>>>>>>>
>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>
>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>
>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>> that.
>>>>>>>
>>>>>>> From a technical point of view, double-open is clearly
>>>>>>> preferable as it removes a special case with no technical
>>>>>>> down-side.
>>>>>> There's a technical downside if you implement the tape in the
>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>> fast to append characters to the buffer's end.
>>>>> I meant for the theory of such machines. It's the theory and the
>>>>> theorems that will dictate which style an authors chooses and
>>>>> there's no down-side in that context.
>>>>>
>>>>>> There's usually spare memory there in the system, so
>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>> field.
>>>>> If you do the resizing right, the same is true of push_front().
>>>>>
>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>> by a move for the entire buffer.
>>>>> Every now and then, your realloc will need an extra move, but
>>>>> that's a cost that will be amortised if you do the usual
>>>>> exponential resizing.
>>>>>> There are ways round this, of course, but you have to know what
>>>>>> you are doing, and it's not as easy to write.
>>>>>
>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>> other or even both ends seems to me to be utterly trivial.
>>>>
>>>> https://en.cppreference.com/w/cpp/container/deque
>>>> push_back adds an element to the end
>>>> push_front inserts an element to the beginning
>>>
>>> I think everyone here knows that.
>>>
>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>> 200 million steps a second, I didn't think there was much room for a
>>> speed-up.
>>>
>>> I've just tried it, and using std::deque rather than std::string slows
>>> my implementation down to 106 million steps a second, and it doesn't
>>> simplify the logic at all. In fact, the few places where you really
>>> want a string get a bit more fiddly.
>>>
>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>> champions.
>> std::string (or std::vector) will likely win for small N and std::deque
>> for large N as far as push_front is concerned.
>>
>> /Flibble
>
> If you are not actually implementing a machine replacing the tape by a pair of
> stacks is attractive. Actually you replace the tape by three things - two stacks
> (called for example left and right) and a single focus cell.
>
> But none of this is really needed. We don't really need TM's for anything
> practical.

std::vector essentially <is> a stack.

I consider your solution optimal. Here is the first part of its
implementation:

struct Tape
{ unsigned int Tape_Head;
std::vector<unsigned char> Left;
std::vector<unsigned char> Right;
unsigned int move_left();
unsigned int move_right();
};

Tape_Head is mapped to its location in Left or Right.

--
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 [ best tape ]

<Tb2dnQFwPLxohub_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory comp.lang.c comp.lang.c++
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: Tue, 10 May 2022 21:14:13 -0500
Date: Tue, 10 May 2022 21:14:12 -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 [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory,comp.lang.c,comp.lang.c++
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <Tb2dnQFwPLxohub_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 168
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-mikMHhSeZ8E6WuLRJR4C7ZB4Q2pAANZyN3sgGZ3VrGDbAAAgrc81Z2rC7LkkidmucN6ZqrRGymmDCIb!6ARo7lSbwxyRnuF8yAFk9PwAA4cn7Fz9GzYWMUWEbjeBQZyGT3QJ8oWSt2BlnrG6o85S+6x5K3I=
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: 9175
 by: olcott - Wed, 11 May 2022 02:14 UTC

On 5/10/2022 9:05 PM, Mike Terry wrote:
> On 11/05/2022 02:12, olcott wrote:
>> On 5/10/2022 7:42 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>>>>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>>>>> On Tue, 10 May 2022 16:41:28 +0100
>>>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>>>
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>>>
>>>>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> No.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>>>>>
>>>>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>>>>> however, that that is not the case.
>>>>>>>>>>>>
>>>>>>>>>>>> How would you define conventional?
>>>>>>>>>>>
>>>>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>>>>
>>>>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>>>>
>>>>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>>>>>> that.
>>>>>>>>>>>
>>>>>>>>>>>   From a technical point of view, double-open is clearly
>>>>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>>>>> down-side.
>>>>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>>>>> fast to append characters to the buffer's end.
>>>>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>>>>> theorems that will dictate which style an authors chooses and
>>>>>>>>> there's no down-side in that context.
>>>>>>>>>
>>>>>>>>>> There's usually spare memory there in the system, so
>>>>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>>>>> field.
>>>>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>>>>
>>>>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>>>>> by a move for the entire buffer.
>>>>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>>>>> that's a cost that will be amortised if you do the usual
>>>>>>>>> exponential resizing.
>>>>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>>>>> you are doing, and it's not as easy to write.
>>>>>>>>>
>>>>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>>>>
>>>>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>>>>> push_back adds an element to the end
>>>>>>>> push_front inserts an element to the beginning
>>>>>>>
>>>>>>> I think everyone here knows that.
>>>>>>>
>>>>>>> Using std::deque was suggested before (by Jeff I think), but at
>>>>>>> nearly
>>>>>>> 200 million steps a second, I didn't think there was much room for a
>>>>>>> speed-up.
>>>>>>>
>>>>>>> I've just tried it, and using std::deque rather than std::string
>>>>>>> slows
>>>>>>> my implementation down to 106 million steps a second, and it doesn't
>>>>>>> simplify the logic at all. In fact, the few places where you really
>>>>>>> want a string get a bit more fiddly.
>>>>>>>
>>>>>>> Mind you, the speed is almost irrelevant unless you are hunting
>>>>>>> for BB
>>>>>>> champions.
>>>>>> std::string (or std::vector) will likely win for small N and
>>>>>> std::deque
>>>>>> for large N as far as push_front is concerned.
>>>>>>
>>>>>> /Flibble
>>>>> If you are not actually implementing a machine replacing the tape by
>>>>> a pair of stacks is attractive. Actually you replace the tape by
>>>>> three things - two stacks (called for example left and right) and a
>>>>> single focus cell.
>>>
>>> I've tried both (two stacks and two stacks and a cell) and I think the
>>> extra cell just makes it a bit fussy.
>>>
>>
>> std::vector <is> essentially a stack.
>>
>> struct Tape
>> {
>>    unsigned int Tape_Head;
>>    std::vector<unsigned char> Left;
>>    std::vector<unsigned char> Right;
>>    unsigned int move_left();
>>    unsigned int move_right();
>> };
>>
>> Tape_Head is mapped to its location in Left or Right.
>> I am still working out the details of this part.
>>
>
> I think you've misunderstood DK's and Ben's approaches.  I think what
> you're suggesting is that Left handles all the "negative" tape head
> positions, and Right all the "positive" ones, while Tape_Head contains
> the tape head index (positive or negative) which changes by 1 each time
> the head moves?
>


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

<t5f87p$n3e$1@dont-email.me>

 copy mid

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

 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: Tue, 10 May 2022 20:49:24 -0600
Organization: A noiseless patient Spider
Lines: 106
Message-ID: <t5f87p$n3e$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <t5e902$61j$1@dont-email.me>
<8vydnYsTy7kxm-b_nZ2dnUU7_8xh4p2d@giganews.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: base64
Injection-Date: Wed, 11 May 2022 02:49:30 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="5f7c8c24d28c1c216986c4ed78941ec3";
logging-data="23662"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+a9oxg/l8X9EX9aV10kWIlREAxnwv2Sek="
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:8knF7EJNlErANfZ26mecTioNKoY=
In-Reply-To: <8vydnYsTy7kxm-b_nZ2dnUU7_8xh4p2d@giganews.com>
Content-Language: en-US
 by: Jeff Barnett - Wed, 11 May 2022 02:49 UTC

On 5/10/2022 6:43 PM, olcott wrote:
> On 5/10/2022 12:56 PM, Jeff Barnett wrote:
>> On 5/10/2022 9:41 AM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>>>
>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>
>>>>>>>>>>>>> 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.
>>>>>>>>>>>
>>>>>>>>>>> No.
>>>>>>>>>>
>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>
>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>> certain is
>>>>>>>>> that if there were a convention, an author not using that
>>>>>>>>> convention
>>>>>>>>> should say as much. You'll find, however, that that is not the
>>>>>>>>> case.
>>>>>>>>
>>>>>>>> How would you define conventional?
>>>>>>>
>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>
>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>
>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>> what it
>>>>>>> "typical" is hard to assess. I think double-open is more commonly
>>>>>>> used in
>>>>>>> modern presentations, but the only real way to know would be to do a
>>>>>>> survey and I don't think the topic merits that.
>>>>>>>
>>>>>>>   From a technical point of view, double-open is clearly
>>>>>>> preferable as it
>>>>>>> removes a special case with no technical down-side.
>>>>>>>
>>>>>> There's a technical downside if you implement the tape in the
>>>>>> obvious way,
>>>>>> as a dynamic buffer. Most languages make it quite fast to append
>>>>>> characters
>>>>>> to the buffer's end.
>>>>> I meant for the theory of such machines.  It's the theory and the
>>>>> theorems that will dictate which style an authors chooses and
>>>>> there's no
>>>>> down-side in that context.
>>>>>
>>>>>> There's usually spare memory there in the system, so
>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>> field.
>>>>> If you do the resizing right, the same is true of push_front().
>>>>>
>>>>>> push_front(), however, generally requires a push_back, followed by
>>>>>> a move
>>>>>> for the entire buffer.
>>>>> Every now and then, your realloc will need an extra move, but that's a
>>>>> cost that will be amortised if you do the usual exponential resizing.
>>>>>
>>>>>> There are ways round this, of course, but you have to know what you
>>>>>> are doing, and it's not as easy to write.
>>>>>
>>>>> Gosh, you have a low opinion of what's generally understood!  Maybe I
>>>>> have too high an opinion, but growing a buffer at one or other or even
>>>>> both ends seems to me to be utterly trivial.
>>>>
>>>> https://en.cppreference.com/w/cpp/container/deque
>>>> push_back adds an element to the end
>>>> push_front inserts an element to the beginning
>>>
>>> I think everyone here knows that.
>>>
>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>> 200 million steps a second, I didn't think there was much room for a
>>> speed-up.
>>>
>>> I've just tried it, and using std::deque rather than std::string slows
>>> my implementation down to 106 million steps a second, and it doesn't
>>> simplify the logic at all.  In fact, the few places where you really
>>> want a string get a bit more fiddly.
>>>
>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>> champions.
>>
>> One possibility is to use a linked list where each node contains a
>> character, a pointer to the following node, and a pointer to the
>> previous node. Since the TM can only move one tape square per state
>> transition, the > cache will do a good job of speeding things up. Of
>> course storage per character is more and that will slow things down.
>>
>> Another way to make tape storage almost all characters is to allocate
>> a block (page sized) at a time with one block initially. A block is
>> allocated each time you are about to go off either the front or back
>> end and is linked. The cache hit ratio is extremely good and only a
>> tiny fraction less then using a big array. It wins, however, when
>> growing an array would cause you to move it.
>
>
> David kleinecke's solution is a much more efficient and simpler way to
> implement push_back() and push_front() than std::deque that also has
> none of the pitfalls such as:
>
> https://www.cplusplus.com/reference/deque/deque/push_front/
> All iterators related to this container are invalidated.
>
> I consider it an optimal solution and the one that I am implementing.
I'm not sure what any of what you said has to do with what I wrote. All
I assume from the runtime is a way of occasionally allocating some multi
page-sized blocks. That and a few lines (a dozen or so) of code will
handle the allocation and usage: fairly trivial and quick stuff.
--
Jeff Barnett

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

<871qx0lqkn.fsf@bsb.me.uk>

 copy mid

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

 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 [ best tape ]
Date: Wed, 11 May 2022 04:02:16 +0100
Organization: A noiseless patient Spider
Lines: 138
Message-ID: <871qx0lqkn.fsf@bsb.me.uk>
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com>
<87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
<87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_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="0e1d4fd29744a738b604ac23bca2b355";
logging-data="23034"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/FYgSQWovE6RFgqROdF5FmpJn7SCgc9Yo="
Cancel-Lock: sha1:6nkECjiyZBb8LoSnMOA9wz2NGEQ=
sha1:rNn+Gkps1Cdjm1QtnPks9leDy7o=
X-BSB-Auth: 1.777b851887248534803b.20220511040216BST.871qx0lqkn.fsf@bsb.me.uk
 by: Ben - Wed, 11 May 2022 03:02 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/10/2022 7:42 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>>>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>>>> On Tue, 10 May 2022 16:41:28 +0100
>>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>>
>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>>
>>>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>
>>>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> No.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>>>>
>>>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>>>> however, that that is not the case.
>>>>>>>>>>>
>>>>>>>>>>> How would you define conventional?
>>>>>>>>>>
>>>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>>>
>>>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>>>
>>>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>>>>> that.
>>>>>>>>>>
>>>>>>>>>> From a technical point of view, double-open is clearly
>>>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>>>> down-side.
>>>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>>>> fast to append characters to the buffer's end.
>>>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>>>> theorems that will dictate which style an authors chooses and
>>>>>>>> there's no down-side in that context.
>>>>>>>>
>>>>>>>>> There's usually spare memory there in the system, so
>>>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>>>> field.
>>>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>>>
>>>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>>>> by a move for the entire buffer.
>>>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>>>> that's a cost that will be amortised if you do the usual
>>>>>>>> exponential resizing.
>>>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>>>> you are doing, and it's not as easy to write.
>>>>>>>>
>>>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>>>
>>>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>>>> push_back adds an element to the end
>>>>>>> push_front inserts an element to the beginning
>>>>>>
>>>>>> I think everyone here knows that.
>>>>>>
>>>>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>>>>> 200 million steps a second, I didn't think there was much room for a
>>>>>> speed-up.
>>>>>>
>>>>>> I've just tried it, and using std::deque rather than std::string slows
>>>>>> my implementation down to 106 million steps a second, and it doesn't
>>>>>> simplify the logic at all. In fact, the few places where you really
>>>>>> want a string get a bit more fiddly.
>>>>>>
>>>>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>>>>> champions.
>>>>> std::string (or std::vector) will likely win for small N and std::deque
>>>>> for large N as far as push_front is concerned.
>>>>>
>>>>> /Flibble
>>>> If you are not actually implementing a machine replacing the tape by
>>>> a pair of stacks is attractive. Actually you replace the tape by
>>>> three things - two stacks (called for example left and right) and a
>>>> single focus cell.
>> I've tried both (two stacks and two stacks and a cell) and I think the
>> extra cell just makes it a bit fussy.
>>
>
> std::vector <is> essentially a stack.

You can certainly use a std::vector as a stack but I'd derive my own
stack from a vector so as to make it infinitely "popable" with the pop
operation returning the tape's blank symbol.

> struct Tape
> {
> unsigned int Tape_Head;
> std::vector<unsigned char> Left;
> std::vector<unsigned char> Right;
> unsigned int move_left();
> unsigned int move_right();
> };
>
> Tape_Head is mapped to its location in Left or Right.
> I am still working out the details of this part.

This looks odd. If you use the two stacks approach, you don't need
Tape_Head. The current cell is never indexed but is always the top of
the Right stack.

--
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 [ best tape ]

<BPKdnQMRR6v4teb_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 10 May 2022 22:07:17 -0500
Date: Tue, 10 May 2022 22:07:16 -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 [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <871qx0lqkn.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <BPKdnQMRR6v4teb_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 145
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-eWLyZmPJzAR8sVFg+mBWMV7tMeCANWNsxmCY57x/p1uepB6dLjG/PCQW3SZ6G4chMwL9eSHHRjagBKx!2kHP8ZVRpHvFS2H2xGNlSJJVicQzFkqmS/H2Ktx0E+wrCo2N3VaYb0hIhncioqbSSsU4lNTHowA=
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: 8248
 by: olcott - Wed, 11 May 2022 03:07 UTC

On 5/10/2022 10:02 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/10/2022 7:42 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>>>>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>>>>> On Tue, 10 May 2022 16:41:28 +0100
>>>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>>>
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>>>
>>>>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> No.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>>>>>
>>>>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>>>>> however, that that is not the case.
>>>>>>>>>>>>
>>>>>>>>>>>> How would you define conventional?
>>>>>>>>>>>
>>>>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>>>>
>>>>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>>>>
>>>>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>>>>>> that.
>>>>>>>>>>>
>>>>>>>>>>> From a technical point of view, double-open is clearly
>>>>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>>>>> down-side.
>>>>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>>>>> fast to append characters to the buffer's end.
>>>>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>>>>> theorems that will dictate which style an authors chooses and
>>>>>>>>> there's no down-side in that context.
>>>>>>>>>
>>>>>>>>>> There's usually spare memory there in the system, so
>>>>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>>>>> field.
>>>>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>>>>
>>>>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>>>>> by a move for the entire buffer.
>>>>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>>>>> that's a cost that will be amortised if you do the usual
>>>>>>>>> exponential resizing.
>>>>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>>>>> you are doing, and it's not as easy to write.
>>>>>>>>>
>>>>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>>>>
>>>>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>>>>> push_back adds an element to the end
>>>>>>>> push_front inserts an element to the beginning
>>>>>>>
>>>>>>> I think everyone here knows that.
>>>>>>>
>>>>>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>>>>>> 200 million steps a second, I didn't think there was much room for a
>>>>>>> speed-up.
>>>>>>>
>>>>>>> I've just tried it, and using std::deque rather than std::string slows
>>>>>>> my implementation down to 106 million steps a second, and it doesn't
>>>>>>> simplify the logic at all. In fact, the few places where you really
>>>>>>> want a string get a bit more fiddly.
>>>>>>>
>>>>>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>>>>>> champions.
>>>>>> std::string (or std::vector) will likely win for small N and std::deque
>>>>>> for large N as far as push_front is concerned.
>>>>>>
>>>>>> /Flibble
>>>>> If you are not actually implementing a machine replacing the tape by
>>>>> a pair of stacks is attractive. Actually you replace the tape by
>>>>> three things - two stacks (called for example left and right) and a
>>>>> single focus cell.
>>> I've tried both (two stacks and two stacks and a cell) and I think the
>>> extra cell just makes it a bit fussy.
>>>
>>
>> std::vector <is> essentially a stack.
>
> You can certainly use a std::vector as a stack but I'd derive my own
> stack from a vector so as to make it infinitely "popable" with the pop
> operation returning the tape's blank symbol.
>
>> struct Tape
>> {
>> unsigned int Tape_Head;
>> std::vector<unsigned char> Left;
>> std::vector<unsigned char> Right;
>> unsigned int move_left();
>> unsigned int move_right();
>> };
>>
>> Tape_Head is mapped to its location in Left or Right.
>> I am still working out the details of this part.
>
> This looks odd. If you use the two stacks approach, you don't need
> Tape_Head. The current cell is never indexed but is always the top of
> the Right stack.
>


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

<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
X-Received: by 2002:ad4:5f89:0:b0:45a:f6d9:41c1 with SMTP id jp9-20020ad45f89000000b0045af6d941c1mr17408712qvb.50.1652260752645;
Wed, 11 May 2022 02:19:12 -0700 (PDT)
X-Received: by 2002:a5b:6c1:0:b0:633:b5c7:b9b7 with SMTP id
r1-20020a5b06c1000000b00633b5c7b9b7mr22661828ybq.67.1652260752304; Wed, 11
May 2022 02:19:12 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Wed, 11 May 2022 02:19:12 -0700 (PDT)
In-Reply-To: <eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
Injection-Info: google-groups.googlegroups.com; posting-host=81.143.231.9; posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 81.143.231.9
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com> <874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com> <87sfphl7iv.fsf@bsb.me.uk>
<20220510190118.00006b59@reddwarf.jmc> <f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Wed, 11 May 2022 09:19:12 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 2841
 by: Malcolm McLean - Wed, 11 May 2022 09:19 UTC

On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>
> But what you suggest is quite workable...
>
> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a
> comfortably large chosen page size. (But efficiency really isn't an issue for this task!)
>
The tape is unbounded. And even some very simple machines will fill it up to infinity.
If you stop the machine when the process runs out of memory, which is a reasonable
strategy, you don't want O(N) tape write operations.

Chained blocks are probably the best model. They don't scale up, so a machine that was written
for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know
the approximate szie of your tape, however, then blocks are a good solution.

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

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

 copy mid

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

 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 [ best tape ]
Date: Wed, 11 May 2022 13:40:58 +0100
Organization: A noiseless patient Spider
Lines: 35
Message-ID: <87ee108co5.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com>
<87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
<87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<871qx0lqkn.fsf@bsb.me.uk>
<BPKdnQMRR6v4teb_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="0e1d4fd29744a738b604ac23bca2b355";
logging-data="6150"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1881WuMH6ycgWkb9anekIdF4Z4MTFRZYUA="
Cancel-Lock: sha1:rADTSbBmPW7ABt/4vLAX0Db2Z24=
sha1:5hw/r2xvIcOHe6ypDxubVmQ4gxI=
X-BSB-Auth: 1.1afcfaea7a636b8af4b6.20220511134058BST.87ee108co5.fsf@bsb.me.uk
 by: Ben - Wed, 11 May 2022 12:40 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/10/2022 10:02 PM, Ben wrote:

>> You can certainly use a std::vector as a stack but I'd derive my own
>> stack from a vector so as to make it infinitely "popable" with the pop
>> operation returning the tape's blank symbol.
>>
>>> struct Tape
>>> {
>>> unsigned int Tape_Head;
>>> std::vector<unsigned char> Left;
>>> std::vector<unsigned char> Right;
>>> unsigned int move_left();
>>> unsigned int move_right();
>>> };
>>>
>>> Tape_Head is mapped to its location in Left or Right.
>>> I am still working out the details of this part.
>>
>> This looks odd. If you use the two stacks approach, you don't need
>> Tape_Head. The current cell is never indexed but is always the top of
>> the Right stack.
>
> The current Tape_Head maps to elements of Left or Right
> or to an element before Left or after Right.

Even talking about code you won't address the points made -- you just
assert something equally wrong. I won't repeat what I said. Address it
if you like or not.

--
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 [ best tape ]

<QJudnRpb3qKIXeb_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 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: Wed, 11 May 2022 08:54:29 -0500
Date: Wed, 11 May 2022 08:54:27 -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 [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <QJudnRpb3qKIXeb_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 33
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-ZJUtmzujWfepIeLW+skid34DpjNBL1dj8znRcHaIe382fwGtmP1EtPAoj7WwhFG7NS0gqCTPmxmYGiB!2fbor/3OgTLcvVczCkINu988mDhw5g8rDn8FGwGc7U89VGZq+EaBANMzFNrxGqNoNazZHniNF+M=
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: 3720
 by: olcott - Wed, 11 May 2022 13:54 UTC

On 5/11/2022 4:19 AM, Malcolm McLean wrote:
> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>>
>> But what you suggest is quite workable...
>>
>> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a
>> comfortably large chosen page size. (But efficiency really isn't an issue for this task!)
>>
> The tape is unbounded. And even some very simple machines will fill it up to infinity.
> If you stop the machine when the process runs out of memory, which is a reasonable
> strategy, you don't want O(N) tape write operations.
>
> Chained blocks are probably the best model. They don't scale up, so a machine that was written
> for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know
> the approximate szie of your tape, however, then blocks are a good solution.

I prefer the exponential memory allocation of std:vector.
It seems to be the optimal balance between speed and memory use.

My implementation of David Kleinecke's double stack based std::deque
will allow std::deque::push_front() to work exactly the same way as
std:vector::push_back().

It doesn't invalidate iterators or integer subscripts or have any of the
extra (memory or time) overhead of std:deque. It seems to me to simply
be a much better way to implement the same functionality as std::deque.

--
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 [ best tape ]

<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

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

 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: Wed, 11 May 2022 09:02:26 -0500
Date: Wed, 11 May 2022 09:02:24 -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 [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <871qx0lqkn.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 149
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-JXscXYsglbBNBwZJ9qwXccZiFHbozdXkRxx5cXagw1OfzQ+qtNze6IOwkUoeV912S9fh6hV98c1CdWQ!d+TCGYfOTtNSKdMBFr0F4rkyNjHcPTozBcCg2BUPMqveKUPQKbIzgguwoLGAVpDd0dyucSGZB30=
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: 8331
 by: olcott - Wed, 11 May 2022 14:02 UTC

On 5/10/2022 10:02 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/10/2022 7:42 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>>>>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>>>>> On Tue, 10 May 2022 16:41:28 +0100
>>>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>>>
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>>>
>>>>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> No.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>>>>>
>>>>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>>>>> however, that that is not the case.
>>>>>>>>>>>>
>>>>>>>>>>>> How would you define conventional?
>>>>>>>>>>>
>>>>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>>>>
>>>>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>>>>
>>>>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>>>>>> that.
>>>>>>>>>>>
>>>>>>>>>>> From a technical point of view, double-open is clearly
>>>>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>>>>> down-side.
>>>>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>>>>> fast to append characters to the buffer's end.
>>>>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>>>>> theorems that will dictate which style an authors chooses and
>>>>>>>>> there's no down-side in that context.
>>>>>>>>>
>>>>>>>>>> There's usually spare memory there in the system, so
>>>>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>>>>> field.
>>>>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>>>>
>>>>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>>>>> by a move for the entire buffer.
>>>>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>>>>> that's a cost that will be amortised if you do the usual
>>>>>>>>> exponential resizing.
>>>>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>>>>> you are doing, and it's not as easy to write.
>>>>>>>>>
>>>>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>>>>
>>>>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>>>>> push_back adds an element to the end
>>>>>>>> push_front inserts an element to the beginning
>>>>>>>
>>>>>>> I think everyone here knows that.
>>>>>>>
>>>>>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>>>>>> 200 million steps a second, I didn't think there was much room for a
>>>>>>> speed-up.
>>>>>>>
>>>>>>> I've just tried it, and using std::deque rather than std::string slows
>>>>>>> my implementation down to 106 million steps a second, and it doesn't
>>>>>>> simplify the logic at all. In fact, the few places where you really
>>>>>>> want a string get a bit more fiddly.
>>>>>>>
>>>>>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>>>>>> champions.
>>>>>> std::string (or std::vector) will likely win for small N and std::deque
>>>>>> for large N as far as push_front is concerned.
>>>>>>
>>>>>> /Flibble
>>>>> If you are not actually implementing a machine replacing the tape by
>>>>> a pair of stacks is attractive. Actually you replace the tape by
>>>>> three things - two stacks (called for example left and right) and a
>>>>> single focus cell.
>>> I've tried both (two stacks and two stacks and a cell) and I think the
>>> extra cell just makes it a bit fussy.
>>>
>>
>> std::vector <is> essentially a stack.
>
> You can certainly use a std::vector as a stack but I'd derive my own
> stack from a vector so as to make it infinitely "popable" with the pop
> operation returning the tape's blank symbol.
>

No need for the pop operation.

>> struct Tape
>> {
>> unsigned int Tape_Head;
>> std::vector<unsigned char> Left;
>> std::vector<unsigned char> Right;
>> unsigned int move_left();
>> unsigned int move_right();
>> };
>>
>> Tape_Head is mapped to its location in Left or Right.
>> I am still working out the details of this part.
>
> This looks odd. If you use the two stacks approach, you don't need
> Tape_Head. The current cell is never indexed but is always the top of
> the Right stack.
>


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

<t5gjk2$1qj3$1@gioia.aioe.org>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!CC3uK9WYEoa7s1kzH7komw.user.46.165.242.75.POSTED!not-for-mail
From: news.dea...@darjeeling.plus.com (Mike Terry)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Date: Wed, 11 May 2022 16:09:54 +0100
Organization: Aioe.org NNTP Server
Message-ID: <t5gjk2$1qj3$1@gioia.aioe.org>
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: gioia.aioe.org; logging-data="60003"; posting-host="CC3uK9WYEoa7s1kzH7komw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.7.1
X-Notice: Filtered by postfilter v. 0.9.2
 by: Mike Terry - Wed, 11 May 2022 15:09 UTC

On 11/05/2022 15:02, olcott wrote:
> On 5/10/2022 10:02 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/10/2022 7:42 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>>>>>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>>>>>> On Tue, 10 May 2022 16:41:28 +0100
>>>>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>>>>
>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>>>>
>>>>>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>
>>>>>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> No.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>>>>>> however, that that is not the case.
>>>>>>>>>>>>>
>>>>>>>>>>>>> How would you define conventional?
>>>>>>>>>>>>
>>>>>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>>>>>
>>>>>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>>>>>
>>>>>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>>>>>> what it "typical" is hard to assess. I think double-open is more
>>>>>>>>>>>> commonly used in modern presentations, but the only real way to
>>>>>>>>>>>> know would be to do a survey and I don't think the topic merits
>>>>>>>>>>>> that.
>>>>>>>>>>>>
>>>>>>>>>>>>    From a technical point of view, double-open is clearly
>>>>>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>>>>>> down-side.
>>>>>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>>>>>> fast to append characters to the buffer's end.
>>>>>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>>>>>> theorems that will dictate which style an authors chooses and
>>>>>>>>>> there's no down-side in that context.
>>>>>>>>>>
>>>>>>>>>>> There's usually spare memory there in the system, so
>>>>>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>>>>>> field.
>>>>>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>>>>>
>>>>>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>>>>>> by a move for the entire buffer.
>>>>>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>>>>>> that's a cost that will be amortised if you do the usual
>>>>>>>>>> exponential resizing.
>>>>>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>>>>>> you are doing, and it's not as easy to write.
>>>>>>>>>>
>>>>>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>>>>>
>>>>>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>>>>>> push_back adds an element to the end
>>>>>>>>> push_front inserts an element to the beginning
>>>>>>>>
>>>>>>>> I think everyone here knows that.
>>>>>>>>
>>>>>>>> Using std::deque was suggested before (by Jeff I think), but at nearly
>>>>>>>> 200 million steps a second, I didn't think there was much room for a
>>>>>>>> speed-up.
>>>>>>>>
>>>>>>>> I've just tried it, and using std::deque rather than std::string slows
>>>>>>>> my implementation down to 106 million steps a second, and it doesn't
>>>>>>>> simplify the logic at all. In fact, the few places where you really
>>>>>>>> want a string get a bit more fiddly.
>>>>>>>>
>>>>>>>> Mind you, the speed is almost irrelevant unless you are hunting for BB
>>>>>>>> champions.
>>>>>>> std::string (or std::vector) will likely win for small N and std::deque
>>>>>>> for large N as far as push_front is concerned.
>>>>>>>
>>>>>>> /Flibble
>>>>>> If you are not actually implementing a machine replacing the tape by
>>>>>> a pair of stacks is attractive. Actually you replace the tape by
>>>>>> three things - two stacks (called for example left and right) and a
>>>>>> single focus cell.
>>>> I've tried both (two stacks and two stacks and a cell) and I think the
>>>> extra cell just makes it a bit fussy.
>>>>
>>>
>>> std::vector <is> essentially a stack.
>>
>> You can certainly use a std::vector as a stack but I'd derive my own
>> stack from a vector so as to make it infinitely "popable" with the pop
>> operation returning the tape's blank symbol.
>>
>
> No need for the pop operation.
>
>>> struct Tape
>>> {
>>>    unsigned int Tape_Head;
>>>    std::vector<unsigned char> Left;
>>>    std::vector<unsigned char> Right;
>>>    unsigned int move_left();
>>>    unsigned int move_right();
>>> };
>>>
>>> Tape_Head is mapped to its location in Left or Right.
>>> I am still working out the details of this part.
>>
>> This looks odd.  If you use the two stacks approach, you don't need
>> Tape_Head.  The current cell is never indexed but is always the top of
>> the Right stack.
>>
>
> That is simply factually incorrect with my implementation of David Kleinecke's double stack based
> std::deque applied to a doubled ended TM tape.
>


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

<t5gkl6$8og$1@gioia.aioe.org>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!CC3uK9WYEoa7s1kzH7komw.user.46.165.242.75.POSTED!not-for-mail
From: news.dea...@darjeeling.plus.com (Mike Terry)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Date: Wed, 11 May 2022 16:27:34 +0100
Organization: Aioe.org NNTP Server
Message-ID: <t5gkl6$8og$1@gioia.aioe.org>
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="8976"; posting-host="CC3uK9WYEoa7s1kzH7komw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.7.1
X-Notice: Filtered by postfilter v. 0.9.2
 by: Mike Terry - Wed, 11 May 2022 15:27 UTC

On 11/05/2022 10:19, Malcolm McLean wrote:
> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>>
>> But what you suggest is quite workable...
>>
>> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a
>> comfortably large chosen page size. (But efficiency really isn't an issue for this task!)
>>
> The tape is unbounded. And even some very simple machines will fill it up to infinity.
> If you stop the machine when the process runs out of memory, which is a reasonable
> strategy, you don't want O(N) tape write operations.
>
> Chained blocks are probably the best model. They don't scale up, so a machine that was written
> for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know
> the approximate szie of your tape, however, then blocks are a good solution.
>

I don't get why you say a chained block approach doesn't scale up. Such a design works well until
the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine with
page files etc.. When the tape gets very large, only a small portion of it needs to be in the
working set for the process to avoid paging.

The only design I can think of that might scale up better would be one using an output device larger
than the logical address space limit. Maybe you were just saying that a hard-coded small block size
(for a ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you
would use a chained block approach on such a tiny machine! Perhaps you meant to say the design
doesn't scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at
run time if we like.)

Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory around
when the vector/string is extended, so perhaps you meant to say that /those/ designs don't scale up,
but the chained blocks scale up?

Mike.

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

<GPCdnW5yC47BS-b_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 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: Wed, 11 May 2022 10:29:32 -0500
Date: Wed, 11 May 2022 10:29:30 -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 [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com>
<t5gjk2$1qj3$1@gioia.aioe.org>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <t5gjk2$1qj3$1@gioia.aioe.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <GPCdnW5yC47BS-b_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 183
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-vyIZuxVboKMDJUovTswwl44AqJosFR1wbnYDWuYjr1N6mFIMJyDikAbLGCjgVUW5YXagqzGL57e7bRZ!y3rsYhVLbDqT1aWQFaHwd4rg/4UMRMCRwytWYSZeQejccFpUDBdHDT2BBUbFx/gCOngoLiTDFCQ=
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: 9752
 by: olcott - Wed, 11 May 2022 15:29 UTC

On 5/11/2022 10:09 AM, Mike Terry wrote:
> On 11/05/2022 15:02, olcott wrote:
>> On 5/10/2022 10:02 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/10/2022 7:42 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/10/2022 1:59 PM, dklei...@gmail.com wrote:
>>>>>>> On Tuesday, May 10, 2022 at 11:01:21 AM UTC-7, Mr Flibble wrote:
>>>>>>>> On Tue, 10 May 2022 16:41:28 +0100
>>>>>>>> Ben <ben.u...@bsb.me.uk> wrote:
>>>>>>>>
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 5/10/2022 6:23 AM, Ben wrote:
>>>>>>>>>>> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On Tuesday, 10 May 2022 at 11:31:46 UTC+1, Ben wrote:
>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> On 5/9/2022 7:13 PM, Ben wrote:
>>>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>>>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>> On 5/8/2022 1:27 PM, Ben wrote:
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>>> No.
>>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> Sipser and Kozen agree with me, Linz agrees with you.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> None of these authors say what is "conventional". What is
>>>>>>>>>>>>>>> certain is that if there were a convention, an author not
>>>>>>>>>>>>>>> using that convention should say as much. You'll find,
>>>>>>>>>>>>>>> however, that that is not the case.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> How would you define conventional?
>>>>>>>>>>>>>
>>>>>>>>>>>>> "the accepted or traditional method of doing something"
>>>>>>>>>>>>>
>>>>>>>>>>>>>> The most typical use is one way unlimited, right?
>>>>>>>>>>>>>
>>>>>>>>>>>>> I don't know. I know it's not a widely agreed convention, but
>>>>>>>>>>>>> what it "typical" is hard to assess. I think double-open is
>>>>>>>>>>>>> more
>>>>>>>>>>>>> commonly used in modern presentations, but the only real
>>>>>>>>>>>>> way to
>>>>>>>>>>>>> know would be to do a survey and I don't think the topic
>>>>>>>>>>>>> merits
>>>>>>>>>>>>> that.
>>>>>>>>>>>>>
>>>>>>>>>>>>>    From a technical point of view, double-open is clearly
>>>>>>>>>>>>> preferable as it removes a special case with no technical
>>>>>>>>>>>>> down-side.
>>>>>>>>>>>> There's a technical downside if you implement the tape in the
>>>>>>>>>>>> obvious way, as a dynamic buffer. Most languages make it quite
>>>>>>>>>>>> fast to append characters to the buffer's end.
>>>>>>>>>>> I meant for the theory of such machines. It's the theory and the
>>>>>>>>>>> theorems that will dictate which style an authors chooses and
>>>>>>>>>>> there's no down-side in that context.
>>>>>>>>>>>
>>>>>>>>>>>> There's usually spare memory there in the system, so
>>>>>>>>>>>> the push_back() operation is just a case of incrementing a size
>>>>>>>>>>>> field.
>>>>>>>>>>> If you do the resizing right, the same is true of push_front().
>>>>>>>>>>>
>>>>>>>>>>>> push_front(), however, generally requires a push_back, followed
>>>>>>>>>>>> by a move for the entire buffer.
>>>>>>>>>>> Every now and then, your realloc will need an extra move, but
>>>>>>>>>>> that's a cost that will be amortised if you do the usual
>>>>>>>>>>> exponential resizing.
>>>>>>>>>>>> There are ways round this, of course, but you have to know what
>>>>>>>>>>>> you are doing, and it's not as easy to write.
>>>>>>>>>>>
>>>>>>>>>>> Gosh, you have a low opinion of what's generally understood!
>>>>>>>>>>> Maybe I have too high an opinion, but growing a buffer at one or
>>>>>>>>>>> other or even both ends seems to me to be utterly trivial.
>>>>>>>>>>
>>>>>>>>>> https://en.cppreference.com/w/cpp/container/deque
>>>>>>>>>> push_back adds an element to the end
>>>>>>>>>> push_front inserts an element to the beginning
>>>>>>>>>
>>>>>>>>> I think everyone here knows that.
>>>>>>>>>
>>>>>>>>> Using std::deque was suggested before (by Jeff I think), but at
>>>>>>>>> nearly
>>>>>>>>> 200 million steps a second, I didn't think there was much room
>>>>>>>>> for a
>>>>>>>>> speed-up.
>>>>>>>>>
>>>>>>>>> I've just tried it, and using std::deque rather than
>>>>>>>>> std::string slows
>>>>>>>>> my implementation down to 106 million steps a second, and it
>>>>>>>>> doesn't
>>>>>>>>> simplify the logic at all. In fact, the few places where you
>>>>>>>>> really
>>>>>>>>> want a string get a bit more fiddly.
>>>>>>>>>
>>>>>>>>> Mind you, the speed is almost irrelevant unless you are hunting
>>>>>>>>> for BB
>>>>>>>>> champions.
>>>>>>>> std::string (or std::vector) will likely win for small N and
>>>>>>>> std::deque
>>>>>>>> for large N as far as push_front is concerned.
>>>>>>>>
>>>>>>>> /Flibble
>>>>>>> If you are not actually implementing a machine replacing the tape by
>>>>>>> a pair of stacks is attractive. Actually you replace the tape by
>>>>>>> three things - two stacks (called for example left and right) and a
>>>>>>> single focus cell.
>>>>> I've tried both (two stacks and two stacks and a cell) and I think the
>>>>> extra cell just makes it a bit fussy.
>>>>>
>>>>
>>>> std::vector <is> essentially a stack.
>>>
>>> You can certainly use a std::vector as a stack but I'd derive my own
>>> stack from a vector so as to make it infinitely "popable" with the pop
>>> operation returning the tape's blank symbol.
>>>
>>
>> No need for the pop operation.
>>
>>>> struct Tape
>>>> {
>>>>    unsigned int Tape_Head;
>>>>    std::vector<unsigned char> Left;
>>>>    std::vector<unsigned char> Right;
>>>>    unsigned int move_left();
>>>>    unsigned int move_right();
>>>> };
>>>>
>>>> Tape_Head is mapped to its location in Left or Right.
>>>> I am still working out the details of this part.
>>>
>>> This looks odd.  If you use the two stacks approach, you don't need
>>> Tape_Head.  The current cell is never indexed but is always the top of
>>> the Right stack.
>>>
>>
>> That is simply factually incorrect with my implementation of David
>> Kleinecke's double stack based std::deque applied to a doubled ended
>> TM tape.
>>
>
> Then you've not understood DK and Ben's approach, like I said.  Your
> replies are typical of you not reading what people write, or simply not
> understanding what they've written.  Do you know what a stack is?
>
> So, tell us what how Tape_Head changes as the TM runs?  Is it not the
> case Tape_Head will go up by 1 for each R tape movement and down for a L
> tape movement?


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

<2oSdnbrtJu94Sub_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 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: Wed, 11 May 2022 10:36:05 -0500
Date: Wed, 11 May 2022 10:36:03 -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 [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
<t5gkl6$8og$1@gioia.aioe.org>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <t5gkl6$8og$1@gioia.aioe.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <2oSdnbrtJu94Sub_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 65
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-POjM+SS/myAXfIgVVsLAi4p/JuEgMocWjcXfXvumDH79oPXjgWFoJhY0b7+vTaUOnNmnf0Nxu80XsHo!LN8Simlwk6Mxy84+sO4Wkp9gegy0QKKzN+AdqhUSEAY4fV2IXCDwMtzaBr57pey56F3uKcZR6ek=
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: 4915
 by: olcott - Wed, 11 May 2022 15:36 UTC

On 5/11/2022 10:27 AM, Mike Terry wrote:
> On 11/05/2022 10:19, Malcolm McLean wrote:
>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>>>
>>> But what you suggest is quite workable...
>>>
>>> I think if I were interested in ultimate efficiency, I might go with
>>> Jeff's "chained blocks" with a
>>> comfortably large chosen page size. (But efficiency really isn't an
>>> issue for this task!)
>>>
>> The tape is unbounded. And even some very simple machines will fill it
>> up to infinity.
>> If you stop the machine when the process runs out of memory, which is
>> a reasonable
>> strategy, you don't want O(N) tape write operations.
>>
>> Chained blocks are probably the best model. They don't scale up, so a
>> machine that was written
>> for a 16K ZX81 might struggle when ported to a 16GB typical modern
>> desktop. If you know
>> the approximate szie of your tape, however, then blocks are a good
>> solution.
>>
>
> I don't get why you say a chained block approach doesn't scale up.  Such
> a design works well until the logical (user) address space is filled,
> which is absolutely huge on a modern 64-bit machine with page files
> etc..  When the tape gets very large, only a small portion of it needs
> to be in the working set for the process to avoid paging.
>

The exponential growth rate factor of std::vector seems to be a more
efficient tradeoff of space versus time and does not have the extra
(space/time) overhead of multiple levels of reference.

> The only design I can think of that might scale up better would be one
> using an output device larger than the logical address space limit.
> Maybe you were just saying that a hard-coded small block size (for a

The fastest output devices are still enormously slower than RAM.

> ZX81?) is not as efficient as big blocks if you've got lots of memory?
> I don't see that you would use a chained block approach on such a tiny
> machine!  Perhaps you meant to say the design doesn't scale /down/
> rather than up?  (And the size of chained blocks can be dynamically
> decided at run time if we like.)
>
> Other designs, e.g. using vector or strings will involve copying ever
> larger blocks of memory around when the vector/string is extended, so
> perhaps you meant to say that /those/ designs don't scale up, but the
> chained blocks scale up?
>
>
> Mike.

Empirical testing seems to prove that std::vector is faster than other
methods because it greatly reduces the number of allocations required.

--
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 [ best tape ]

<rsidnRMUF-lhR-b_nZ2dnUU7-TnNnZ2d@brightview.co.uk>

 copy mid

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

 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!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 11 May 2022 10:49:16 -0500
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <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> <0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87r152qrp2.fsf@bsb.me.uk> <rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com>
<87wneumegw.fsf@bsb.me.uk> <ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
<87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
<t5gkl6$8og$1@gioia.aioe.org> <2oSdnbrtJu94Sub_nZ2dnUU7_83NnZ2d@giganews.com>
From: news.dea...@darjeeling.plus.com (Mike Terry)
Date: Wed, 11 May 2022 16:49:16 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.7.1
MIME-Version: 1.0
In-Reply-To: <2oSdnbrtJu94Sub_nZ2dnUU7_83NnZ2d@giganews.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <rsidnRMUF-lhR-b_nZ2dnUU7-TnNnZ2d@brightview.co.uk>
Lines: 58
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-ns8zipo0yFGg3gBtEhM9icUgLufSiteTn9NKpNJ7rh+aTKC8djUdhqIiP8oc1l1UtwwySFpZmdF7fML!TTw3i4OVBlgxaI4zdOHQbpmARrNtyRbk93XjWeTcyHXFUWMpI6o2e40YhkVMAwvhd+yG1+OqBtpZ!t90AgQ2TmcotkWtKiLKYp7xfvMY=
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: 5266
 by: Mike Terry - Wed, 11 May 2022 15:49 UTC

On 11/05/2022 16:36, olcott wrote:
> On 5/11/2022 10:27 AM, Mike Terry wrote:
>> On 11/05/2022 10:19, Malcolm McLean wrote:
>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>>>>
>>>> But what you suggest is quite workable...
>>>>
>>>> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a
>>>> comfortably large chosen page size. (But efficiency really isn't an issue for this task!)
>>>>
>>> The tape is unbounded. And even some very simple machines will fill it up to infinity.
>>> If you stop the machine when the process runs out of memory, which is a reasonable
>>> strategy, you don't want O(N) tape write operations.
>>>
>>> Chained blocks are probably the best model. They don't scale up, so a machine that was written
>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know
>>> the approximate szie of your tape, however, then blocks are a good solution.
>>>
>>
>> I don't get why you say a chained block approach doesn't scale up.  Such a design works well until
>> the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine
>> with page files etc..  When the tape gets very large, only a small portion of it needs to be in
>> the working set for the process to avoid paging.
>>
>
> The exponential growth rate factor of std::vector seems to be a more efficient tradeoff of space
> versus time and does not have the extra (space/time) overhead of multiple levels of reference.
>
>> The only design I can think of that might scale up better would be one using an output device
>> larger than the logical address space limit. Maybe you were just saying that a hard-coded small
>> block size (for a
>
> The fastest output devices are still enormously slower than RAM.
>
>> ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you would
>> use a chained block approach on such a tiny machine!  Perhaps you meant to say the design doesn't
>> scale /down/ rather than up?  (And the size of chained blocks can be dynamically decided at run
>> time if we like.)
>>
>> Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory
>> around when the vector/string is extended, so perhaps you meant to say that /those/ designs don't
>> scale up, but the chained blocks scale up?
>>
>>
>> Mike.
>
> Empirical testing seems to prove that std::vector is faster than other methods because it greatly
> reduces the number of allocations required.

So you don't understand DK/Ben's two stack approach, and you don't understand the chained blocks
approach. I could ask "what empirical testing?" but that would just be a waste of time, so I won't...

Anyway, none of that matters - just concentrate on finishing your coding! (I did say that your two
vector approach was ok, so I was never suggesting you're incapable of finishing it, or that it can't
work or anything...)

Mike.

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

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

 copy mid

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

 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 [ best tape ]
Date: Wed, 11 May 2022 20:35:32 +0100
Organization: A noiseless patient Spider
Lines: 87
Message-ID: <87sfpf7th7.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com>
<87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
<87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@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="0e1d4fd29744a738b604ac23bca2b355";
logging-data="26809"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+6PHgMCwS3y5+c2DQ0TPtGLotpGb4jTTs="
Cancel-Lock: sha1:ln5YWBkFFDs6DGPhL2w4r20F4Sk=
sha1:kMupmCh7tZhFgZ1HrVSDi9yD1P8=
X-BSB-Auth: 1.cad7addbb2f1ddb45b4e.20220511203532BST.87sfpf7th7.fsf@bsb.me.uk
 by: Ben - Wed, 11 May 2022 19:35 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/10/2022 10:02 PM, Ben wrote:

>> You can certainly use a std::vector as a stack but I'd derive my own
>> stack from a vector so as to make it infinitely "popable" with the pop
>> operation returning the tape's blank symbol.
>
> No need for the pop operation.
>
>>> struct Tape
>>> {
>>> unsigned int Tape_Head;
>>> std::vector<unsigned char> Left;
>>> std::vector<unsigned char> Right;
>>> unsigned int move_left();
>>> unsigned int move_right();
>>> };
>>>
>>> Tape_Head is mapped to its location in Left or Right.
>>> I am still working out the details of this part.
>>
>> This looks odd. If you use the two stacks approach, you don't need
>> Tape_Head. The current cell is never indexed but is always the top of
>> the Right stack.
>
> That is simply factually incorrect with my implementation of David
> Kleinecke's double stack based std::deque applied to a doubled ended
> TM tape.

You still don't understand the two stack method. Here is a sketch of
how it's done. The reason it's efficient (in so far as it is) is that
the tape move is simply:

if (go_right) left.push(right.pop());
else right.push(left.pop());

---------- code -------
#include <iostream>
#include <vector>
#include <string>

struct infinite_stack : public std::vector<char> {
char top() const { return empty() ? '_' : back(); }
char pop() { char c = top(); if (!empty()) pop_back(); return c; }
void push(char c) { push_back(c); }
};

struct tape {
tape(std::string s);
infinite_stack left, right;
void move(bool go_right) {
if (go_right) left.push(right.pop());
else right.push(left.pop());
}
friend std::ostream &operator<<(std::ostream &os, const tape &t);
};

tape::tape(std::string s)
{ for (auto i = s.size(); i-- > 0;) right.push(s[i]);
}

std::ostream &operator<<(std::ostream &os, const tape &t)
{ for (char c : t.left) os.put(c);
os << '[' << t.right.top() << ']';
for (auto i = t.right.size() - 1; i-- > 0;) os.put(t.right[i]);
return os;
}

int main()
{ tape test("abcdef");
std::cout << test << "\n";
test.move(0); std::cout << test << "\n";
test.move(0); std::cout << test << "\n";
test.move(1); std::cout << test << "\n";
test.move(1); std::cout << test << "\n";
test.move(1); std::cout << test << "\n";
}

--
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 [ best tape ]

<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 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: Wed, 11 May 2022 15:12:13 -0500
Date: Wed, 11 May 2022 15:12:10 -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 [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com> <87sfpf7th7.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87sfpf7th7.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 94
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-AmCAjOnjrmBZ/Ph0n4FHjOQx4O/msA/S8e4t3FgB1XonXDm+k6Qq1Dvbfx3KqjT9Td1z+owKexZu03G!A0tQUqfEGA3TZNmwi556s9AwB1MtxQkfA+XZwkfzxt8wnQTWabcWvQsSGhSE93GKPp8uzU6+nAU=
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: 4989
 by: olcott - Wed, 11 May 2022 20:12 UTC

On 5/11/2022 2:35 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/10/2022 10:02 PM, Ben wrote:
>
>>> You can certainly use a std::vector as a stack but I'd derive my own
>>> stack from a vector so as to make it infinitely "popable" with the pop
>>> operation returning the tape's blank symbol.
>>
>> No need for the pop operation.
>>
>>>> struct Tape
>>>> {
>>>> unsigned int Tape_Head;
>>>> std::vector<unsigned char> Left;
>>>> std::vector<unsigned char> Right;
>>>> unsigned int move_left();
>>>> unsigned int move_right();
>>>> };
>>>>
>>>> Tape_Head is mapped to its location in Left or Right.
>>>> I am still working out the details of this part.
>>>
>>> This looks odd. If you use the two stacks approach, you don't need
>>> Tape_Head. The current cell is never indexed but is always the top of
>>> the Right stack.
>>
>> That is simply factually incorrect with my implementation of David
>> Kleinecke's double stack based std::deque applied to a doubled ended
>> TM tape.
>
> You still don't understand the two stack method. Here is a sketch of
> how it's done. The reason it's efficient (in so far as it is) is that
> the tape move is simply:
>
> if (go_right) left.push(right.pop());
> else right.push(left.pop());
>
> ---------- code -------
> #include <iostream>
> #include <vector>
> #include <string>
>
> struct infinite_stack : public std::vector<char> {
> char top() const { return empty() ? '_' : back(); }
> char pop() { char c = top(); if (!empty()) pop_back(); return c; }
> void push(char c) { push_back(c); }
> };
>
> struct tape {
> tape(std::string s);
> infinite_stack left, right;
> void move(bool go_right) {
> if (go_right) left.push(right.pop());
> else right.push(left.pop());
> }
> friend std::ostream &operator<<(std::ostream &os, const tape &t);
> };
>
> tape::tape(std::string s)
> {
> for (auto i = s.size(); i-- > 0;) right.push(s[i]);
> }
>
> std::ostream &operator<<(std::ostream &os, const tape &t)
> {
> for (char c : t.left) os.put(c);
> os << '[' << t.right.top() << ']';
> for (auto i = t.right.size() - 1; i-- > 0;) os.put(t.right[i]);
> return os;
> }
>
> int main()
> {
> tape test("abcdef");
> std::cout << test << "\n";
> test.move(0); std::cout << test << "\n";
> test.move(0); std::cout << test << "\n";
> test.move(1); std::cout << test << "\n";
> test.move(1); std::cout << test << "\n";
> test.move(1); std::cout << test << "\n";
> }
>
>

I think that my way is more efficient.
I will post it as soon as it is done.

--
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 [ best tape ]

<0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:622a:38b:b0:2f3:dcce:a7a3 with SMTP id j11-20020a05622a038b00b002f3dccea7a3mr14053648qtx.439.1652304656671;
Wed, 11 May 2022 14:30:56 -0700 (PDT)
X-Received: by 2002:a25:8c87:0:b0:64a:870a:e29d with SMTP id
m7-20020a258c87000000b0064a870ae29dmr22949613ybl.596.1652304656246; Wed, 11
May 2022 14:30:56 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Wed, 11 May 2022 14:30:55 -0700 (PDT)
In-Reply-To: <t5gkl6$8og$1@gioia.aioe.org>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:44a6:5950:aa59:c9d2;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:44a6:5950:aa59:c9d2
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com> <874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com> <87sfphl7iv.fsf@bsb.me.uk>
<20220510190118.00006b59@reddwarf.jmc> <f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com> <t5gkl6$8og$1@gioia.aioe.org>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Wed, 11 May 2022 21:30:56 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 4530
 by: Malcolm McLean - Wed, 11 May 2022 21:30 UTC

On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote:
> On 11/05/2022 10:19, Malcolm McLean wrote:
> > On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
> >>
> >> But what you suggest is quite workable...
> >>
> >> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a
> >> comfortably large chosen page size. (But efficiency really isn't an issue for this task!)
> >>
> > The tape is unbounded. And even some very simple machines will fill it up to infinity.
> > If you stop the machine when the process runs out of memory, which is a reasonable
> > strategy, you don't want O(N) tape write operations.
> >
> > Chained blocks are probably the best model. They don't scale up, so a machine that was written
> > for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know
> > the approximate szie of your tape, however, then blocks are a good solution.
> >
> I don't get why you say a chained block approach doesn't scale up. Such a design works well until
> the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine with
> page files etc.. When the tape gets very large, only a small portion of it needs to be in the
> working set for the process to avoid paging.
>
> The only design I can think of that might scale up better would be one using an output device larger
> than the logical address space limit. Maybe you were just saying that a hard-coded small block size
> (for a ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you
> would use a chained block approach on such a tiny machine! Perhaps you meant to say the design
> doesn't scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at
> run time if we like.)
>
> Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory around
> when the vector/string is extended, so perhaps you meant to say that /those/ designs don't scale up,
> but the chained blocks scale up?
>
I was thinking that the chained block degenerates into effectively a linked list when block size becomes
small in relation to tape length. However that isn't really a problem - it still works more effectively
than a contiguous model.

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

<bfWdnfWTUopbseH_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

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

 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: Wed, 11 May 2022 16:38:14 -0500
Date: Wed, 11 May 2022 16:38:11 -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 [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$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>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
<t5gkl6$8og$1@gioia.aioe.org>
<0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <bfWdnfWTUopbseH_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 48
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-pSFG0tf1bKaO23N3RG9t4YepHSksr374SF+oGkwHkOZ3Z/QYQkF1STMoSqSY5hu4gZ28mpPyWQDkkpw!KhF+0fXsIW2mGrAgO92qVdYQYFniIKJJMMOJzbIg4TP2DplyNXdVW+w34LUJtMjtq9jnxZP1GUk=
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: 4990
 by: olcott - Wed, 11 May 2022 21:38 UTC

On 5/11/2022 4:30 PM, Malcolm McLean wrote:
> On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote:
>> On 11/05/2022 10:19, Malcolm McLean wrote:
>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>>>>
>>>> But what you suggest is quite workable...
>>>>
>>>> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks" with a
>>>> comfortably large chosen page size. (But efficiency really isn't an issue for this task!)
>>>>
>>> The tape is unbounded. And even some very simple machines will fill it up to infinity.
>>> If you stop the machine when the process runs out of memory, which is a reasonable
>>> strategy, you don't want O(N) tape write operations.
>>>
>>> Chained blocks are probably the best model. They don't scale up, so a machine that was written
>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know
>>> the approximate szie of your tape, however, then blocks are a good solution.
>>>
>> I don't get why you say a chained block approach doesn't scale up. Such a design works well until
>> the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine with
>> page files etc.. When the tape gets very large, only a small portion of it needs to be in the
>> working set for the process to avoid paging.
>>
>> The only design I can think of that might scale up better would be one using an output device larger
>> than the logical address space limit. Maybe you were just saying that a hard-coded small block size
>> (for a ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you
>> would use a chained block approach on such a tiny machine! Perhaps you meant to say the design
>> doesn't scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at
>> run time if we like.)
>>
>> Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory around
>> when the vector/string is extended, so perhaps you meant to say that /those/ designs don't scale up,
>> but the chained blocks scale up?
>>
> I was thinking that the chained block degenerates into effectively a linked list when block size becomes
> small in relation to tape length. However that isn't really a problem - it still works more effectively
> than a contiguous model.

The actual run-time cost issue is not copying data, this is fairly
cheap. A linear growth factor has far many more very expensive operating
system memory allocation calls than an exponential growth factor.

--
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 [ best tape ]

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

 copy mid

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

 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 [ best tape ]
Date: Wed, 11 May 2022 22:54:36 +0100
Organization: A noiseless patient Spider
Lines: 67
Message-ID: <87bkw37n1f.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com>
<87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
<87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com>
<87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_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="0e1d4fd29744a738b604ac23bca2b355";
logging-data="25831"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19VDULuFD/bFNFae44FkVfWK7MJAo7DZ/0="
Cancel-Lock: sha1:4GfGI/sxsCYrQYhO8dwnO8ecEhI=
sha1:4ctS/8sqpmdsID9a4/5285pdltU=
X-BSB-Auth: 1.c416a0ceb56a678f6420.20220511225436BST.87bkw37n1f.fsf@bsb.me.uk
 by: Ben - Wed, 11 May 2022 21:54 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/11/2022 2:35 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/10/2022 10:02 PM, Ben wrote:
>>
>>>> You can certainly use a std::vector as a stack but I'd derive my own
>>>> stack from a vector so as to make it infinitely "popable" with the pop
>>>> operation returning the tape's blank symbol.
>>>
>>> No need for the pop operation.

>> You still don't understand the two stack method. Here is a sketch of
>> how it's done. The reason it's efficient (in so far as it is) is that
>> the tape move is simply:
>> if (go_right) left.push(right.pop());
>> else right.push(left.pop());
>> ---------- code -------
>> #include <iostream>
>> #include <vector>
>> #include <string>
>> struct infinite_stack : public std::vector<char> {
>> char top() const { return empty() ? '_' : back(); }
>> char pop() { char c = top(); if (!empty()) pop_back(); return c; }
>> void push(char c) { push_back(c); }
>> };
>> struct tape {
>> tape(std::string s);
>> infinite_stack left, right;
>> void move(bool go_right) {
>> if (go_right) left.push(right.pop());
>> else right.push(left.pop());
>> }
>> friend std::ostream &operator<<(std::ostream &os, const tape &t);
>> };
>> tape::tape(std::string s)
>> {
>> for (auto i = s.size(); i-- > 0;) right.push(s[i]);
>> }
>> std::ostream &operator<<(std::ostream &os, const tape &t)
>> {
>> for (char c : t.left) os.put(c);
>> os << '[' << t.right.top() << ']';
>> for (auto i = t.right.size() - 1; i-- > 0;) os.put(t.right[i]);
>> return os;
>> }
>> int main()
>> {
>> tape test("abcdef");
>> std::cout << test << "\n";
>> test.move(0); std::cout << test << "\n";
>> test.move(0); std::cout << test << "\n";
>> test.move(1); std::cout << test << "\n";
>> test.move(1); std::cout << test << "\n";
>> test.move(1); std::cout << test << "\n";
>> }
>
> I think that my way is more efficient.

That may well be the case. But your way is not the "two stacks" way if
there is no need for pop.

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

Pages:12345678
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor