Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

"Our vision is to speed up time, eventually eliminating it." -- Alex Schure


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

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

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

<sdydnYLI-KSQpOT_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 09 May 2022 10:53:49 -0500
Date: Mon, 9 May 2022 10:53:48 -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>
<zLUdK.4623$arR.255@fx48.iad> <20220508203050.00001cd7@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220508203050.00001cd7@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <sdydnYLI-KSQpOT_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 140
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-bkvhlvXdqdxfP7HUQp8LPTJjmnbSK/CDugPySGtrrQZ9ty5y0sRYNjyoCll6oHBB03gGJoKHANQZWT3!Q6Imq50rhqxejm2knCIGGspSz+8mlOkaa1NR5cgLQkxGUsGGqZa0gFR8bgTR88V7sj8K19NhbEE=
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: 7062
 by: olcott - Mon, 9 May 2022 15:53 UTC

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

The classic TM is not allowed to move before its beginning thus a
std::vector is best for the tape.

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

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

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function
Date: Mon, 09 May 2022 23:08:53 +0100
Organization: A noiseless patient Spider
Lines: 13
Message-ID: <87wneuqryi.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<zLUdK.4623$arR.255@fx48.iad> <20220508203050.00001cd7@reddwarf.jmc>
<sdydnYLI-KSQpOT_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="8f4b18f06fcc0bb5681d9a39c037aa43";
logging-data="5457"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19sNgqtCz9ciLY81Z/37h8Vye9kCfIwaiI="
Cancel-Lock: sha1:JfOw7N4BpVtxNYpSnuLRqSOMquQ=
sha1:QhT2QPbgdzwphajssrGmGKiHAHg=
X-BSB-Auth: 1.109cb83845860cdaadbf.20220509230853BST.87wneuqryi.fsf@bsb.me.uk
 by: Ben - Mon, 9 May 2022 22:08 UTC

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.

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

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

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function
Date: Mon, 09 May 2022 23:14:33 +0100
Organization: A noiseless patient Spider
Lines: 17
Message-ID: <87r152qrp2.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="8f4b18f06fcc0bb5681d9a39c037aa43";
logging-data="5457"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+hYFuQeh02EpziQs1yp15IKVCbygLJh7M="
Cancel-Lock: sha1:JvXiKgnh1lsjBsFl5PeA1bYXQ5A=
sha1:fiX6rTfy+ISDYNLW+o/v0yqhiqw=
X-BSB-Auth: 1.1c376e5a85015446d40b.20220509231433BST.87r152qrp2.fsf@bsb.me.uk
 by: Ben - Mon, 9 May 2022 22:14 UTC

olcott <NoOne@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.

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

<XcmdnbaZ-aTnC-T_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 09 May 2022 17:32:26 -0500
Date: Mon, 9 May 2022 17:32:25 -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>
<zLUdK.4623$arR.255@fx48.iad> <20220508203050.00001cd7@reddwarf.jmc>
<sdydnYLI-KSQpOT_nZ2dnUU7_81g4p2d@giganews.com> <87wneuqryi.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87wneuqryi.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <XcmdnbaZ-aTnC-T_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 19
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-PjLO0z7et61OylRitJep52tTax2zvvGklVxYNntVUfGhmZ5qv7ncwGta0yOJK9rIfio45mWd0j+CTMG!DXsibyl/rg15qChjJDlqqIj1ot9r3xEUU4jetQVFOir8mflmwWfa8bG9FyxCw+F1s1MJOhBSQVI=
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: 2301
 by: olcott - Mon, 9 May 2022 22:32 UTC

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.

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

<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 09 May 2022 17:42:07 -0500
Date: Mon, 9 May 2022 17:42:06 -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>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87r152qrp2.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 23
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-hgRSDxKjzCguAa6uqH+vvx35ghma69+rpxKgjCunNOb/00eFOBdS2bK35X4myxTw5WLwkExgKeXkSbG!mr/SFHDkUiGUH1LFyN1O6nOoZYei69N6bKmF5VN1IoQ9eIbSRBwzU7w069cU3LUy6rynZSK7gvY=
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: 2321
 by: olcott - Mon, 9 May 2022 22:42 UTC

On 5/9/2022 5:14 PM, Ben wrote:
> olcott <NoOne@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.

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

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

 copy mid

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

 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: Tue, 10 May 2022 01:13:51 +0100
Organization: A noiseless patient Spider
Lines: 26
Message-ID: <87wneumegw.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_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="8f4b18f06fcc0bb5681d9a39c037aa43";
logging-data="23566"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19IWUujvE89yqz10sOtKUKBrt+0itsL4QA="
Cancel-Lock: sha1:ipZn4FYrUN1SR7QRGbl/aum2sJw=
sha1:RIK8qtmhN3JyjfDOLUbHMTKJRjE=
X-BSB-Auth: 1.e4a33d9474f302d1bbec.20220510011351BST.87wneumegw.fsf@bsb.me.uk
 by: Ben - Tue, 10 May 2022 00:13 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/9/2022 5:14 PM, Ben wrote:
>> olcott <NoOne@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.

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

<JnieK.57309$t72a.38684@fx10.iad>

 copy mid

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

 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!fx10.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0)
Gecko/20100101 Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <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>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <XcmdnbaZ-aTnC-T_nZ2dnUU7_83NnZ2d@giganews.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 30
Message-ID: <JnieK.57309$t72a.38684@fx10.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Mon, 9 May 2022 20:31:39 -0400
X-Received-Bytes: 2588
 by: Richard Damon - Tue, 10 May 2022 00:31 UTC

On 5/9/22 6:32 PM, olcott wrote:
> 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 truth is that this is one area where different models of Turing
Machines define the tape differently.

Just like some allow for multiple tapes (and thus multiple "tape op"
fields in the instruction, and multiple tape symbols in the rule lookup.)

It can be shown that all the variations are computationally equivalent,
it just changes how complicated some operations are.

For a tape with a fixed beginning spot, if you wanted to extend it in
that dirrection, you just need a short program to go to the other end
and move ever cell out one cell to make room.

Since the tape is finite, this is by definition doable in a finite
number of steps.

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

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

 copy mid

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

 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: Tue, 10 May 2022 01:37:45 +0100
Organization: A noiseless patient Spider
Lines: 28
Message-ID: <87r152mdd2.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="8f4b18f06fcc0bb5681d9a39c037aa43";
logging-data="9297"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX196e+0UHTcg99Tlct0lXBcWFtHE0vCNi4E="
Cancel-Lock: sha1:aybTxAk46MjFMFFeXQnD/kMPE7M=
sha1:FI60q3tefJPmMn+8jfxVAB0otNc=
X-BSB-Auth: 1.7baaaefcfb1d39929fa2.20220510013745BST.87r152mdd2.fsf@bsb.me.uk
 by: Ben - Tue, 10 May 2022 00:37 UTC

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.

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.

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

<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 09 May 2022 20:28:17 -0500
Date: Mon, 9 May 2022 20:28: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
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>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87wneumegw.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
Lines: 33
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-0Kx5/2KuiRPBJ2XSmlpMYccY+L5dgHXQYJNQbnFqj4+R/fkCRMqs0VoGqYobdSc8dULMiUWTD+k6yUI!bZJkQzg59zLwfzy1DiBBgm9eO1tKYChwoY99UHgOHa95HIL3rKwjuxabo8ckw5HJGuwRn9ByhB4=
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: 2813
 by: olcott - Tue, 10 May 2022 01:28 UTC

On 5/9/2022 7:13 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/9/2022 5:14 PM, Ben wrote:
>>> olcott <NoOne@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 most typical use is one way unlimited, 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

<ZK-dnZfTk9JjIuT_nZ2dnUU7_8xh4p2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!1.us.feeder.erje.net!3.us.feeder.erje.net!feeder.erje.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 09 May 2022 20:29:34 -0500
Date: Mon, 9 May 2022 20:29:33 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <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: <ZK-dnZfTk9JjIuT_nZ2dnUU7_8xh4p2d@giganews.com>
Lines: 36
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-1wH8EVOhbsIdsi5NQzuo0YnJSDm0kSSqGMRTGd90KwwLmRnZEu8ZjlCSVxz2Z1ymKaPkhNQoibDGfOz!5o0LaYU2hLOEO41pPSZGG1Pr6KQq3rgOit3OrPeqQWp3AJfzj4iqtII2+VNJwuzBye1lX5a5xQY=
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: 2984
 by: olcott - Tue, 10 May 2022 01:29 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.
>
> 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?
>
(a) Abnormal termination error index out-of-bounds.
(b) Extend the std::vector.

> 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

<63leK.5428$Xh%d.2134@fx98.iad>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!feeder1.feed.usenet.farm!feed.usenet.farm!tr2.eu1.usenetexpress.com!feeder.usenetexpress.com!tr2.iad1.usenetexpress.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx98.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0) Gecko/20100101 Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM transition function
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me> <0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com> <t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk> <t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk> <t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk> <t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk> <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>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 55
Message-ID: <63leK.5428$Xh%d.2134@fx98.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Mon, 9 May 2022 23:34:27 -0400
X-Received-Bytes: 3845
 by: Richard Damon - Tue, 10 May 2022 03:34 UTC

On 5/9/22 9:28 PM, olcott wrote:
> On 5/9/2022 7:13 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>> olcott <NoOne@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 most typical use is one way unlimited, right?
>

Actually, I see unlimited in both directions as more normal, otherwise
you get the odd case of what happens if the system tries to move past
the end of the tape. It basically says you need a special character for
that end of the tape, which just adds an asymmetry to the system.

As I mentioned, it is just a small bit of code to implement an expand
the tape one cell in that direction that just needs to be added to every
case to handle running into the beginning of tape symbol, so there is no
difference in what can be computed, just how much work you need to do
that computation.

The one-directional tape may be easier on the simulator, but that is
just a small advantage, and the impact on the Turing Machine is an
uglification and asymmetry so it seems common to just make the tape
double ended.

Maybe very simple examples for teaching might seem simpler with a single
ended, since you don't need to think as much about where you need to
leave space on your page that you are keeping track of your tape on, and
many of the simple problems only need to extend in one direction, but
that is only a small benifit, and again, you need to add a dedicated
'Beginning of tape' symbol to let the machine know that is the edge (you
might be able to make it double as an end of tape that is allowed to be
overwritten in the other direction.

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

<b30f22cb-7bbd-4336-9741-7fd74980be8en@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:620a:4542:b0:6a0:651b:be0b with SMTP id u2-20020a05620a454200b006a0651bbe0bmr8932507qkp.633.1652167457550;
Tue, 10 May 2022 00:24:17 -0700 (PDT)
X-Received: by 2002:a25:8552:0:b0:64a:df55:efa4 with SMTP id
f18-20020a258552000000b0064adf55efa4mr6591674ybn.527.1652167457331; Tue, 10
May 2022 00:24:17 -0700 (PDT)
Path: i2pn2.org!i2pn.org!aioe.org!news.mixmin.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Tue, 10 May 2022 00:24:17 -0700 (PDT)
In-Reply-To: <63leK.5428$Xh%d.2134@fx98.iad>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:7d65:9d30:c57b:7e1f;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:7d65:9d30:c57b:7e1f
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> <63leK.5428$Xh%d.2134@fx98.iad>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <b30f22cb-7bbd-4336-9741-7fd74980be8en@googlegroups.com>
Subject: Re: Validating that the implementation meets the spec for TM
transition function
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Tue, 10 May 2022 07:24:17 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Malcolm McLean - Tue, 10 May 2022 07:24 UTC

On Tuesday, 10 May 2022 at 04:34:31 UTC+1, richar...@gmail.com wrote:
> On 5/9/22 9:28 PM, olcott wrote:
> > 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 most typical use is one way unlimited, right?
> >
> Actually, I see unlimited in both directions as more normal, otherwise
> you get the odd case of what happens if the system tries to move past
> the end of the tape. It basically says you need a special character for
> that end of the tape, which just adds an asymmetry to the system.
>
> As I mentioned, it is just a small bit of code to implement an expand
> the tape one cell in that direction that just needs to be added to every
> case to handle running into the beginning of tape symbol, so there is no
> difference in what can be computed, just how much work you need to do
> that computation.
>
> The one-directional tape may be easier on the simulator, but that is
> just a small advantage, and the impact on the Turing Machine is an
> uglification and asymmetry so it seems common to just make the tape
> double ended.
>
> Maybe very simple examples for teaching might seem simpler with a single
> ended, since you don't need to think as much about where you need to
> leave space on your page that you are keeping track of your tape on, and
> many of the simple problems only need to extend in one direction, but
> that is only a small benifit, and again, you need to add a dedicated
> 'Beginning of tape' symbol to let the machine know that is the edge (you
> might be able to make it double as an end of tape that is allowed to be
> overwritten in the other direction.
>
As a mathematical model, a tape which is open at both ends is simpler.

If you are engineering a physical machine, a tape which extends arbitrarily
in only one direction may well be easier to implement. As you say, it's easier
to draw the tape, for example.

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

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

 copy mid

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

 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: Tue, 10 May 2022 11:31:44 +0100
Organization: A noiseless patient Spider
Lines: 43
Message-ID: <87fslhn0fj.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="8f4b18f06fcc0bb5681d9a39c037aa43";
logging-data="3224"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19qSCnvPCkhb/4149ACcZwqlruubEhbYSA="
Cancel-Lock: sha1:CmbDYCYlPzRJ32uKG/MGUPCO2NQ=
sha1:bseq6epCqI8zHQL3I6zJn4h8dTI=
X-BSB-Auth: 1.082e08b3f48dfe0d2b04.20220510113144BST.87fslhn0fj.fsf@bsb.me.uk
 by: Ben - Tue, 10 May 2022 10:31 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/9/2022 7:13 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/9/2022 5:14 PM, Ben wrote:
>>>> olcott <NoOne@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.

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

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

 copy mid

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

 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: Tue, 10 May 2022 11:35:52 +0100
Organization: A noiseless patient Spider
Lines: 43
Message-ID: <87a6bpn08n.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <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>
<ZK-dnZfTk9JjIuT_nZ2dnUU7_8xh4p2d@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="8f4b18f06fcc0bb5681d9a39c037aa43";
logging-data="3224"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX183G2dMT/vKwSNDGfs5RMZiJQNNq54/nQ4="
Cancel-Lock: sha1:JMJeyF2uauyaT+33n50zqzOHLXg=
sha1:yCuXdFqVAkKBeNb78WAymYTkj5M=
X-BSB-Auth: 1.29da6ba2ba0736b26ad3.20220510113552BST.87a6bpn08n.fsf@bsb.me.uk
 by: Ben - Tue, 10 May 2022 10:35 UTC

olcott <NoOne@NoWhere.com> writes:

> 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.
>>
>> 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?
>>
> (a) Abnormal termination error index out-of-bounds.

There is no such concept for a Turing machine. The TM can be defined to
halt in this situation (though I don't know any authors who specify it
like that) but halting is halting no matter the reason.

> (b) Extend the std::vector.

Why extend the vector if you've terminated?

>> I've modified my implementation to do either, just in case we end up
>> comparing traces.

Anywhere closer to writing E and specifying P?

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

<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
X-Received: by 2002:ac8:7dc1:0:b0:2f3:c70a:df9e with SMTP id c1-20020ac87dc1000000b002f3c70adf9emr18270920qte.307.1652179596510;
Tue, 10 May 2022 03:46:36 -0700 (PDT)
X-Received: by 2002:a25:4194:0:b0:64a:4c65:9c72 with SMTP id
o142-20020a254194000000b0064a4c659c72mr17029467yba.607.1652179596290; Tue, 10
May 2022 03:46:36 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Tue, 10 May 2022 03:46:36 -0700 (PDT)
In-Reply-To: <87fslhn0fj.fsf@bsb.me.uk>
Injection-Info: google-groups.googlegroups.com; posting-host=2a00:23a8:400a:5601:80f:5126:9143:bd81;
posting-account=Dz2zqgkAAADlK5MFu78bw3ab-BRFV4Qn
NNTP-Posting-Host: 2a00:23a8:400a:5601:80f:5126:9143:bd81
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>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
Subject: Re: Validating that the implementation meets the spec for TM
transition function
From: malcolm....@gmail.com (Malcolm McLean)
Injection-Date: Tue, 10 May 2022 10:46:36 +0000
Content-Type: text/plain; charset="UTF-8"
 by: Malcolm McLean - Tue, 10 May 2022 10:46 UTC

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. There's usually spare memory there in the system, so
the push_back() operation is just a case of incrementing a size field.
push_front(), however, generally requires a push_back, followed by a move
for the entire buffer.

There are ways round this, of course, but you have to know what you are doing,
and it's not as easy to write. ,

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

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

 copy mid

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

 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: Tue, 10 May 2022 12:23:08 +0100
Organization: A noiseless patient Spider
Lines: 70
Message-ID: <874k1xmy1v.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <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>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="8f4b18f06fcc0bb5681d9a39c037aa43";
logging-data="23141"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19bnWm/8lKcOLYKxft8f2xKdp3VV8rAVDY="
Cancel-Lock: sha1:6F7MV0GH/mdrOVkviqxqazj7n/8=
sha1:+drZIQrb05jKj8CnOIsleJlKsr8=
X-BSB-Auth: 1.affa68c3ec0fd992760b.20220510122308BST.874k1xmy1v.fsf@bsb.me.uk
 by: Ben - Tue, 10 May 2022 11:23 UTC

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.

--
Ben.

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

<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 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 06:53:05 -0500
Date: Tue, 10 May 2022 06:53:04 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<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>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <874k1xmy1v.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 80
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-WwgqNzX/wohT8IPjjVoO/WM659g3o2w2YzLzP9A0HMWG1PeHG3wYR8CDOR8syTkyDDdK9c//ik07o0j!8gI/bJmbCeIAyTxqIgPBumqVUeAyMik5NgAdWBnQus0NCQ7RY3cPNtbFJk7If79AsH79PDNzNkU=
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: 5069
 by: olcott - Tue, 10 May 2022 11:53 UTC

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

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

<TKmdnVKs6o7Pz-f_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

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

 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 06:53:54 -0500
Date: Tue, 10 May 2022 06:53: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>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <TKmdnVKs6o7Pz-f_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 61
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-vYGo2UM8Y++hzcw7GT8RJ7l7W9v5xZKyg4lmE1vM5o6G/Zd7J013n1Qm0nqABqMLgn4YPi6wKHAfraE!vYnj6nsPEaOXn7zYnM2e6phjet8DXyPp688XfqqgZM0Dix4JoO4aCXELPGE6S5KueqCSvwk0FIk=
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: 4354
 by: olcott - Tue, 10 May 2022 11:53 UTC

On 5/10/2022 5:46 AM, Malcolm McLean wrote:
> 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. There's usually spare memory there in the system, so
> the push_back() operation is just a case of incrementing a size field.
> push_front(), however, generally requires a push_back, followed by a move
> for the entire buffer.
>
> There are ways round this, of course, but you have to know what you are doing,
> and it's not as easy to write. ,
>

>

https://en.cppreference.com/w/cpp/container/deque
push_back adds an element to the end
push_front inserts an element to the beginning

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

<SuseK.34$w1W1.2@fx47.iad>

 copy mid

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

 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!fx47.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0)
Gecko/20100101 Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<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>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 95
Message-ID: <SuseK.34$w1W1.2@fx47.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Tue, 10 May 2022 08:01:56 -0400
X-Received-Bytes: 5343
 by: Richard Damon - Tue, 10 May 2022 12:01 UTC

On 5/10/22 7:53 AM, olcott wrote:
> 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
>

Yes, but they are arguing about what works efficiently.

deque is designed for this, so both are likely reasonably efficient,
though all extentions that need a realloc to the front will need a move,
while some realloction to the end won't.

Note, I think some people are still thinking about string, which
generally doesn't preallocate extra space to the front of the string
(because push_front isn't a common operation) which deque almost
certainly does (would need to see if required by complexity specifications).

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

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

 copy mid

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

 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: Tue, 10 May 2022 16:41:28 +0100
Organization: A noiseless patient Spider
Lines: 90
Message-ID: <87sfphl7iv.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk>
<t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="8f4b18f06fcc0bb5681d9a39c037aa43";
logging-data="25627"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/9YBjh/WvWeRfH++Tc/GjXFL1XnHD861w="
Cancel-Lock: sha1:JxNKDCSNWpIgdlTuFgGM1EELcaM=
sha1:yiwowleUjitz2kjwysRbpLM0lyQ=
X-BSB-Auth: 1.627408b6fdf7fa87a93a.20220510164128BST.87sfphl7iv.fsf@bsb.me.uk
 by: Ben - Tue, 10 May 2022 15:41 UTC

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.

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

<t5e902$61j$1@dont-email.me>

 copy mid

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

 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 11:56:14 -0600
Organization: A noiseless patient Spider
Lines: 101
Message-ID: <t5e902$61j$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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 10 May 2022 17:56:19 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="0342975f941ea277319df9b16d949731";
logging-data="6195"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/gpYi+OGuhzeyL0OEKRDlRHi54HoDtmL0="
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:fO5rEDrVG4KYsMKnGA2RajIlqbw=
In-Reply-To: <87sfphl7iv.fsf@bsb.me.uk>
Content-Language: en-US
 by: Jeff Barnett - Tue, 10 May 2022 17:56 UTC

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

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

<20220510190118.00006b59@reddwarf.jmc>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!feeder.usenetexpress.com!tr2.eu1.usenetexpress.com!feeder1.feed.usenet.farm!feed.usenet.farm!peer02.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx09.ams4.POSTED!not-for-mail
From: flib...@reddwarf.jmc (Mr Flibble)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function
Message-ID: <20220510190118.00006b59@reddwarf.jmc>
References: <t541t8$upu$1@dont-email.me> <20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me> <0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com> <t545tm$u69$1@dont-email.me> <87h762yxg6.fsf@bsb.me.uk> <t54gl1$cp$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk> <t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk> <t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk> <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>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 99
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Tue, 10 May 2022 18:01:17 UTC
Date: Tue, 10 May 2022 19:01:18 +0100
X-Received-Bytes: 5561
 by: Mr Flibble - Tue, 10 May 2022 18:01 UTC

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

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

<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:620a:484:b0:69f:b1b1:3308 with SMTP id 4-20020a05620a048400b0069fb1b13308mr15789977qkr.293.1652209159163;
Tue, 10 May 2022 11:59:19 -0700 (PDT)
X-Received: by 2002:a25:9849:0:b0:64b:2de4:67c8 with SMTP id
k9-20020a259849000000b0064b2de467c8mr684233ybo.607.1652209158948; Tue, 10 May
2022 11:59:18 -0700 (PDT)
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!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Tue, 10 May 2022 11:59:18 -0700 (PDT)
In-Reply-To: <20220510190118.00006b59@reddwarf.jmc>
Injection-Info: google-groups.googlegroups.com; posting-host=47.208.151.23; posting-account=7Xc2EwkAAABXMcQfERYamr3b-64IkBws
NNTP-Posting-Host: 47.208.151.23
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>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
Subject: Re: Validating that the implementation meets the spec for TM
transition function
From: dkleine...@gmail.com (dklei...@gmail.com)
Injection-Date: Tue, 10 May 2022 18:59:19 +0000
Content-Type: text/plain; charset="UTF-8"
X-Received-Bytes: 6661
 by: dklei...@gmail.com - Tue, 10 May 2022 18:59 UTC

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.

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

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

 copy mid

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

 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 00:11:32 +0100
Organization: A noiseless patient Spider
Lines: 114
Message-ID: <87h75xkmor.fsf@bsb.me.uk>
References: <t541t8$upu$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>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="0e1d4fd29744a738b604ac23bca2b355";
logging-data="31296"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+pA9SZQgzw0oof9ysCMc6cWscZazCKkfE="
Cancel-Lock: sha1:wk+fVSeiyKWhiFuqubFHfFmdCII=
sha1:EdHyVce1uXNuLcJF30yI2hrcjK8=
X-BSB-Auth: 1.0e37facd2ca74f1acc4d.20220511001132BST.87h75xkmor.fsf@bsb.me.uk
 by: Ben - Tue, 10 May 2022 23:11 UTC

Mr Flibble <flibble@reddwarf.jmc> writes:

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

I'm sure that's true. std::string /could/ be made fast for inserts at
position 0 (there is no push_front for a string) but I doubt that case
has been optimised.

But very long tapes will be rare though. And for them to occur there
has to be quite of lots going back and forth as well so I'm not sure if
the tape growth cost will ever dominate.

My test case (BB(5)) ends up with a resulting tape of 12,289 characters,
and all but 45 of those were added at the front. Of course, 12,289 is
not really a long string, and the vast majority of moves happened away
form the "ends".

--
Ben.

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

<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 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:04:05 -0500
Date: Tue, 10 May 2022 19:04:04 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me>
<20220506220822.000061d0@reddwarf.jmc> <t543p9$d1h$1@dont-email.me>
<0ea85390-c036-47ec-bf5c-db53a3c5a3dbn@googlegroups.com>
<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: <ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 119
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-tbbARVUyYp4hEgzSu6kVsOzQ8fteZwJSw3IZQODarNKSsmRfZC52bgILQvJQNjNbyanGljXE38yQWZ3!YZXeAXHVEgGgRfTDeH36DKWutcoQBONwIYfPuMs3As3ZOjbgfvR/4/n4+3mBe2Flx6iUgnedk9I=
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: 7077
 by: olcott - Wed, 11 May 2022 00:04 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.

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.

--
Copyright 2022 Pete Olcott

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

Pages:12345678
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor