Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

Disclaimer: "These opinions are my own, though for a small fee they be yours too." -- Dave Haynie


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

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

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

<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 11 May 2022 17:02:04 -0500
Date: Wed, 11 May 2022 17:02:02 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com> <87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw37n1f.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87bkw37n1f.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 75
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-gxcYjfRMPzEAfIQEL2X99QxwHYsLJuzSNl8X7S1fOEfJQdWNH3AZk0QeHkr7KkL0Ykj8f/TDzgTPpPR!ulzItbuEce5UxqFIA/mFS1jTAAh9H02y0rqvcZBHV3r2iuY82d7gIcw+pGHDEc4iaCV83+F4xZs=
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: 4740
 by: olcott - Wed, 11 May 2022 22:02 UTC

On 5/11/2022 4:54 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/11/2022 2:35 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/10/2022 10:02 PM, Ben wrote:
>>>
>>>>> You can certainly use a std::vector as a stack but I'd derive my own
>>>>> stack from a vector so as to make it infinitely "popable" with the pop
>>>>> operation returning the tape's blank symbol.
>>>>
>>>> No need for the pop operation.
>
>>> You still don't understand the two stack method. Here is a sketch of
>>> how it's done. The reason it's efficient (in so far as it is) is that
>>> the tape move is simply:
>>> if (go_right) left.push(right.pop());
>>> else right.push(left.pop());
>>> ---------- code -------
>>> #include <iostream>
>>> #include <vector>
>>> #include <string>
>>> struct infinite_stack : public std::vector<char> {
>>> char top() const { return empty() ? '_' : back(); }
>>> char pop() { char c = top(); if (!empty()) pop_back(); return c; }
>>> void push(char c) { push_back(c); }
>>> };
>>> struct tape {
>>> tape(std::string s);
>>> infinite_stack left, right;
>>> void move(bool go_right) {
>>> if (go_right) left.push(right.pop());
>>> else right.push(left.pop());
>>> }
>>> friend std::ostream &operator<<(std::ostream &os, const tape &t);
>>> };
>>> tape::tape(std::string s)
>>> {
>>> for (auto i = s.size(); i-- > 0;) right.push(s[i]);
>>> }
>>> std::ostream &operator<<(std::ostream &os, const tape &t)
>>> {
>>> for (char c : t.left) os.put(c);
>>> os << '[' << t.right.top() << ']';
>>> for (auto i = t.right.size() - 1; i-- > 0;) os.put(t.right[i]);
>>> return os;
>>> }
>>> int main()
>>> {
>>> tape test("abcdef");
>>> std::cout << test << "\n";
>>> test.move(0); std::cout << test << "\n";
>>> test.move(0); std::cout << test << "\n";
>>> test.move(1); std::cout << test << "\n";
>>> test.move(1); std::cout << test << "\n";
>>> test.move(1); std::cout << test << "\n";
>>> }
>>
>> I think that my way is more efficient.
>
> That may well be the case. But your way is not the "two stacks" way if
> there is no need for pop.
>

It is only two stacks in the sense that Left accesses its elements from
back to front. Since Right accesses its elements from front to back only
Left is like a stack.

--
Copyright 2022 Pete Olcott

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

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

<t5hf7p$1kd4$1@gioia.aioe.org>

 copy mid

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

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

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

Yes, for a fixed block length it will be like a tape element linked list, but only some small
fraction of the allocation overhead. Bigger blocks resulting in a smaller fraction. Or we could
have some kind of exponential block size growth, so we start with, say, 1 allocation cost for the
first 50000 tape elements, then getting smaller as blocks get bigger - but 1 allocation per 50000
tape elements is already a pretty small overhead for most purposes. E.g. writing/testing PO's Even
TM, we could make do with one single fixed block of just 20 tape elements!!! I'd think the key
thing for PO should be to get on with the exercise, rather than playing with TM emulator efficiency.

Mike.

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

<aYadnaAI4O_Z0uH_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 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!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 11 May 2022 19:05:24 -0500
Date: Wed, 11 May 2022 19:05:21 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk> <t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk> <0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk> <rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk> <ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk> <adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com> <874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com> <87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc> <f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com> <ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk> <QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk> <d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com> <t5gkl6$8og$1@gioia.aioe.org> <0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com> <t5hf7p$1kd4$1@gioia.aioe.org>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <t5hf7p$1kd4$1@gioia.aioe.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <aYadnaAI4O_Z0uH_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 87
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-AvbdNOgD635NT4L9pvfdEWh/ZDK7PWStpyy9re6Pkv4ToQoLRsBVBAmwIEFB24nb2LKYObMfPlcGzHQ!R+6tdTaId6w4jvxyiLKIbnvmnDs4aahmDXVjoNTH5tZgJLldFvqJBnFqo+3yqp6QZYfLG/9/F6s=
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: 6127
X-Received-Bytes: 6234
 by: olcott - Thu, 12 May 2022 00:05 UTC

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

It is more cost-effective to make it right the first time rather than
have to go back and fix it.

My adaptation of David's approach to the TM tape also seems to be an
objectively better way to implement std::deque.

I can't possibly do the exercise until I see 100% exactly how the
transition function works. Although it is exactly the same idea as a DFA
state transition, its seems to not be working that way.

--
Copyright 2022 Pete Olcott

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

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

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

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function [ best tape ]
Date: Thu, 12 May 2022 02:00:29 +0100
Organization: A noiseless patient Spider
Lines: 43
Message-ID: <87lev75zv6.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com>
<87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
<87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com>
<87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_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="b918120b717b1a0036d52ef1ce111b9c";
logging-data="24581"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19puSOlChH/lWrthigNFoU3f9NvUcWcgW8="
Cancel-Lock: sha1:6ZzO9QbriPLV1tBchh927JJEQCY=
sha1:wwmZLpoD46/T/d8ZoOfgAI4p3Ng=
X-BSB-Auth: 1.9c1cc9da2736e765221a.20220512020029BST.87lev75zv6.fsf@bsb.me.uk
 by: Ben - Thu, 12 May 2022 01:00 UTC

olcott <NoOne@NoWhere.com> writes:

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

>>> I think that my way is more efficient.
>>
>> That may well be the case. But your way is not the "two stacks" way if
>> there is no need for pop.
>
> It is only two stacks in the sense that Left accesses its elements
> from back to front. Since Right accesses its elements from front to
> back only Left is like a stack.

That's not what a stack is.

Mind you, your writing is poor in that Right and Left don't access
themselves so I have had to guess what you mean: possibly "the elements
of Left are accessed from back to front" (and analogous wording for
Right).

It's even possible that you /are/ using two stacks and simply writing
words that hide that fact.

Can't you even post the code for the function that moves and/or updates
the tape? Surely that part is now written? That way we'd know what
data structure you are using...

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

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

<TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 11 May 2022 20:37:03 -0500
Date: Wed, 11 May 2022 20:37:00 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com> <87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com> <87lev75zv6.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87lev75zv6.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 65
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-HaEUOvEII7Tpza8VT6xSz/ib92dCQ9gcbRRCxDAn7gmLp5TkxbjrMXwGPT+n/CqYGXkfNp5vfnRLV+s!OgE0v0lUp3EJ/VgS/64eestMHzPcXuXj1XwbbGJxqfg85GQiwFe40GdP2cGC04uAPV7FXOYz+g0=
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: 4159
 by: olcott - Thu, 12 May 2022 01:37 UTC

On 5/11/2022 8:00 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/11/2022 4:54 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/11/2022 2:35 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/10/2022 10:02 PM, Ben wrote:
>>>>>
>>>>>>> You can certainly use a std::vector as a stack but I'd derive my own
>>>>>>> stack from a vector so as to make it infinitely "popable" with the pop
>>>>>>> operation returning the tape's blank symbol.
>>>>>>
>>>>>> No need for the pop operation.
>
>>>> I think that my way is more efficient.
>>>
>>> That may well be the case. But your way is not the "two stacks" way if
>>> there is no need for pop.
>>
>> It is only two stacks in the sense that Left accesses its elements
>> from back to front. Since Right accesses its elements from front to
>> back only Left is like a stack.
>
> That's not what a stack is.
>
> Mind you, your writing is poor in that Right and Left don't access
> themselves so I have had to guess what you mean: possibly "the elements
> of Left are accessed from back to front" (and analogous wording for
> Right).
>
> It's even possible that you /are/ using two stacks and simply writing
> words that hide that fact.
>
> Can't you even post the code for the function that moves and/or updates
> the tape? Surely that part is now written? That way we'd know what
> data structure you are using...
>

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

The part of mapping Tape_Head to a location in Left or Right needs more
desk checking before I will implement it.

We can add space with the efficiently of std::vector.
Much more (time & space) efficient and far less clumsy of an
implementation than std::deque. Seems to simply be a better std::deque.

--
Copyright 2022 Pete Olcott

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

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

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

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function [ best tape ]
Date: Thu, 12 May 2022 02:49:26 +0100
Organization: A noiseless patient Spider
Lines: 26
Message-ID: <874k1v5xll.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
<87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com>
<87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com>
<87lev75zv6.fsf@bsb.me.uk>
<TpidnUev2PYi-eH_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="b918120b717b1a0036d52ef1ce111b9c";
logging-data="24581"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+cF5P5dX/f+02dkVQl0zRErShm6kmmuiw="
Cancel-Lock: sha1:TPESGJAt+EQyrDq+66LFLpU+e9I=
sha1:q4dpwRn37wSUSP5qmvZcHlUL4ZM=
X-BSB-Auth: 1.1dbe57367aa706a412e3.20220512024926BST.874k1v5xll.fsf@bsb.me.uk
 by: Ben - Thu, 12 May 2022 01:49 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/11/2022 8:00 PM, Ben wrote:

>> Can't you even post the code for the function that moves and/or updates
>> the tape? Surely that part is now written? That way we'd know what
>> data structure you are using...
>
> struct Tape
> {
> unsigned int Tape_Head;
> std::vector<unsigned char> Left;
> std::vector<unsigned char> Right;
> unsigned int move_left();
> unsigned int move_right();
> };
>
> The part of mapping Tape_Head to a location in Left or Right needs
> more desk checking before I will implement it.

How long is that going to take?

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

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

<_ZZeK.55$C7G6.31@fx46.iad>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx46.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 [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com> <87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com> <87lev75zv6.fsf@bsb.me.uk>
<TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 86
Message-ID: <_ZZeK.55$C7G6.31@fx46.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: Wed, 11 May 2022 22:07:55 -0400
X-Received-Bytes: 4736
 by: Richard Damon - Thu, 12 May 2022 02:07 UTC

On 5/11/22 9:37 PM, olcott wrote:
> On 5/11/2022 8:00 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/11/2022 4:54 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/11/2022 2:35 PM, Ben wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/10/2022 10:02 PM, Ben wrote:
>>>>>>
>>>>>>>> You can certainly use a std::vector as a stack but I'd derive my
>>>>>>>> own
>>>>>>>> stack from a vector so as to make it infinitely "popable" with
>>>>>>>> the pop
>>>>>>>> operation returning the tape's blank symbol.
>>>>>>>
>>>>>>> No need for the pop operation.
>>
>>>>> I think that my way is more efficient.
>>>>
>>>> That may well be the case.  But your way is not the "two stacks" way if
>>>> there is no need for pop.
>>>
>>> It is only two stacks in the sense that Left accesses its elements
>>> from back to front. Since Right accesses its elements from front to
>>> back only Left is like a stack.
>>
>> That's not what a stack is.
>>
>> Mind you, your writing is poor in that Right and Left don't access
>> themselves so I have had to guess what you mean: possibly "the elements
>> of Left are accessed from back to front" (and analogous wording for
>> Right).
>>
>> It's even possible that you /are/ using two stacks and simply writing
>> words that hide that fact.
>>
>> Can't you even post the code for the function that moves and/or updates
>> the tape?  Surely that part is now written?  That way we'd know what
>> data structure you are using...
>>
>
> struct Tape
> {
>   unsigned int Tape_Head;
>   std::vector<unsigned char> Left;
>   std::vector<unsigned char> Right;
>   unsigned int move_left();
>   unsigned int move_right();
> };
>
> The part of mapping Tape_Head to a location in Left or Right needs more
> desk checking before I will implement it.
>
> We can add space with the efficiently of std::vector.
> Much more (time & space) efficient and far less clumsy of an
> implementation than std::deque. Seems to simply be a better std::deque.
>
>
>

Clearly you don't understand what was being talked about in the "two
stack" method, as the Tape Head is always the last element of a specifed
vector (I beleive traditionally the right).

Moving to the left is just taking the last element off the left vector
and putting it at the end of the right vector, and moving to the right,
is taking the last element off the right vector and putting it at the
end of the left vector.

(In eather case, if the source vector is empty, just put a 'blank tape'
symbol on the destination tape.

As an example, a tape with the symbols 1 to 9 in order (assending left
to right), with the tape head on the 5 would be

Left: 1 2 3 4

Right: 9 8 7 6 5

Note, the Right vector is storing its tape "reversed" from normal
reading order, so its 'businesss' end is the free end that is cheap to
add to and remove from.

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

<2eOdnW7GpMwx6OH_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 11 May 2022 21:49:16 -0500
Date: Wed, 11 May 2022 21:49:14 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com> <87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com> <87lev75zv6.fsf@bsb.me.uk>
<TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1v5xll.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <874k1v5xll.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <2eOdnW7GpMwx6OH_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 33
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-513wQ5yC6KpwmpYX+vOkhOTn01KofJEip3hMhgUjKtdadgVSf1UKlbXelg+keKERjIptwWkPpTYcep4!LpYFYzlQyYwc17uarJuEG6H2sYTcr1XnS/c8OfUed8GK9LGX9w/qlsTjhojuDQWKyi8TrTOfVbs=
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: 2978
 by: olcott - Thu, 12 May 2022 02:49 UTC

On 5/11/2022 8:49 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/11/2022 8:00 PM, Ben wrote:
>
>>> Can't you even post the code for the function that moves and/or updates
>>> the tape? Surely that part is now written? That way we'd know what
>>> data structure you are using...
>>
>> struct Tape
>> {
>> unsigned int Tape_Head;
>> std::vector<unsigned char> Left;
>> std::vector<unsigned char> Right;
>> unsigned int move_left();
>> unsigned int move_right();
>> };
>>
>> The part of mapping Tape_Head to a location in Left or Right needs
>> more desk checking before I will implement it.
>
> How long is that going to take?
>

Less than 8 labor hours, maybe 2 labor hours.
I only work on it for 5 minutes every 2 hours.

--
Copyright 2022 Pete Olcott

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

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

<t5htes$1hb4$1@gioia.aioe.org>

 copy mid

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

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

On 12/05/2022 01:05, olcott wrote:
> On 5/11/2022 6:01 PM, Mike Terry wrote:
>> On 11/05/2022 22:30, Malcolm McLean wrote:
>>> On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote:
>>>> On 11/05/2022 10:19, Malcolm McLean wrote:
>>>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>>>>>>
>>>>>> But what you suggest is quite workable...
>>>>>>
>>>>>> I think if I were interested in ultimate efficiency, I might go with Jeff's "chained blocks"
>>>>>> with a
>>>>>> comfortably large chosen page size. (But efficiency really isn't an issue for this task!)
>>>>>>
>>>>> The tape is unbounded. And even some very simple machines will fill it up to infinity.
>>>>> If you stop the machine when the process runs out of memory, which is a reasonable
>>>>> strategy, you don't want O(N) tape write operations.
>>>>>
>>>>> Chained blocks are probably the best model. They don't scale up, so a machine that was written
>>>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern desktop. If you know
>>>>> the approximate szie of your tape, however, then blocks are a good solution.
>>>>>
>>>> I don't get why you say a chained block approach doesn't scale up. Such a design works well until
>>>> the logical (user) address space is filled, which is absolutely huge on a modern 64-bit machine
>>>> with
>>>> page files etc.. When the tape gets very large, only a small portion of it needs to be in the
>>>> working set for the process to avoid paging.
>>>>
>>>> The only design I can think of that might scale up better would be one using an output device
>>>> larger
>>>> than the logical address space limit. Maybe you were just saying that a hard-coded small block size
>>>> (for a ZX81?) is not as efficient as big blocks if you've got lots of memory? I don't see that you
>>>> would use a chained block approach on such a tiny machine! Perhaps you meant to say the design
>>>> doesn't scale /down/ rather than up? (And the size of chained blocks can be dynamically decided at
>>>> run time if we like.)
>>>>
>>>> Other designs, e.g. using vector or strings will involve copying ever larger blocks of memory
>>>> around
>>>> when the vector/string is extended, so perhaps you meant to say that /those/ designs don't scale
>>>> up,
>>>> but the chained blocks scale up?
>>>>
>>> I was thinking that the chained block degenerates into effectively a linked list when block size
>>> becomes
>>> small in relation to tape length. However that isn't really a problem - it still works more
>>> effectively
>>> than a contiguous model.
>>
>> Yes, for a fixed block length it will be like a tape element linked list, but only some small
>> fraction of the allocation overhead.  Bigger blocks resulting in a smaller fraction.  Or we could
>> have some kind of exponential block size growth, so we start with, say, 1 allocation cost for the
>> first 50000 tape elements, then getting smaller as blocks get bigger - but 1 allocation per 50000
>> tape elements is already a pretty small overhead for most purposes.  E.g. writing/testing PO's
>> Even TM, we could make do with one single fixed block of just 20 tape elements!!! I'd think the
>> key thing for PO should be to get on with the exercise, rather than playing with TM emulator
>> efficiency.
>>
>> Mike.
>
> It is more cost-effective to make it right the first time rather than have to go back and fix it.
>
> My adaptation of David's approach to the TM tape also seems to be an objectively better way to
> implement std::deque.
>
> I can't possibly do the exercise until I see 100% exactly how the transition function works.
> Although it is exactly the same idea as a DFA state transition, its seems to not be working that way.

Yes the idea is the same but slightly more complicated. What seems not to be working that way?

You could think of a TM as a DFA that's been functionally enhanced to allow at each computation step
i) left/right (single) stepping of its input tape head
ii) rewriting of the symbol under the tape head
whereas a DFA is restricted to work with strictly right stepping of its "input tape head" so it only
sees each character once (and so no concept of rewriting anything because it couldn't be reread
anyway).

So compared to a DFA transition rule, a TM rule still takes the same input as a DFA (current state,
input character), but has to specify two additional data items:
i) the direction to move the tape head.
ii) the character to write back to the tape and

For completeness, if you're familiar with DFAs but TMs not so much, I'll add:

A) The DFA/TM termination conditions are a bit different. A DFA halts naturally at the end of the
input string, so it's fine (and typical) to have accept/reject states that are entered multiple
times during a computation, i.e. those states aren't "final" states in the TM sense. A TM clearly
needs some other way to explicitly indicate it's finished. Typically (e.g. Linz) some TM states are
designated "final" states that halt the TM - if it has accept/reject states those are final, so can
only be entered once. (If we converted a DFA to a TM, we would need some obvious fiddling when we
get to the DFA accept/reject states - simply designating them as TM final states wouldn't work...)

B) The TM input tape is /potentially infinite/ in extent so there needs to be the rule for what's on
the tape outside of its designated "input string" at the beginning of a computation. That's what
the TM BLANK symbol is for. (DFA's by design can't get "beyond their input string", so no concept
of a special BLANK symbol arises.)

Mike.

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

<IIadnewQP-K84uH_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 11 May 2022 22:29:37 -0500
Date: Wed, 11 May 2022 22:29:34 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
<t5gkl6$8og$1@gioia.aioe.org>
<0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
<t5hf7p$1kd4$1@gioia.aioe.org>
<aYadnaAI4O_Z0uH_nZ2dnUU7_83NnZ2d@giganews.com>
<t5htes$1hb4$1@gioia.aioe.org>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <t5htes$1hb4$1@gioia.aioe.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <IIadnewQP-K84uH_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 138
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-30znopB1imvS8q6zU99myD+zCd/CydlLTy7LlMlk9yqVxvmfTzsXWRJlcjUqxrw/V8jx9m1cEBJpLTM!seT/UESBJmh6KhObhOxzKk68o+Drn7P+NQLQFxQYnxj2nMCpcDcTIppacXBWDMiSPMVuGsBJJT0=
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: 8825
 by: olcott - Thu, 12 May 2022 03:29 UTC

On 5/11/2022 10:03 PM, Mike Terry wrote:
> On 12/05/2022 01:05, olcott wrote:
>> On 5/11/2022 6:01 PM, Mike Terry wrote:
>>> On 11/05/2022 22:30, Malcolm McLean wrote:
>>>> On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote:
>>>>> On 11/05/2022 10:19, Malcolm McLean wrote:
>>>>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>>>>>>>
>>>>>>> But what you suggest is quite workable...
>>>>>>>
>>>>>>> I think if I were interested in ultimate efficiency, I might go
>>>>>>> with Jeff's "chained blocks" with a
>>>>>>> comfortably large chosen page size. (But efficiency really isn't
>>>>>>> an issue for this task!)
>>>>>>>
>>>>>> The tape is unbounded. And even some very simple machines will
>>>>>> fill it up to infinity.
>>>>>> If you stop the machine when the process runs out of memory, which
>>>>>> is a reasonable
>>>>>> strategy, you don't want O(N) tape write operations.
>>>>>>
>>>>>> Chained blocks are probably the best model. They don't scale up,
>>>>>> so a machine that was written
>>>>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern
>>>>>> desktop. If you know
>>>>>> the approximate szie of your tape, however, then blocks are a good
>>>>>> solution.
>>>>>>
>>>>> I don't get why you say a chained block approach doesn't scale up.
>>>>> Such a design works well until
>>>>> the logical (user) address space is filled, which is absolutely
>>>>> huge on a modern 64-bit machine with
>>>>> page files etc.. When the tape gets very large, only a small
>>>>> portion of it needs to be in the
>>>>> working set for the process to avoid paging.
>>>>>
>>>>> The only design I can think of that might scale up better would be
>>>>> one using an output device larger
>>>>> than the logical address space limit. Maybe you were just saying
>>>>> that a hard-coded small block size
>>>>> (for a ZX81?) is not as efficient as big blocks if you've got lots
>>>>> of memory? I don't see that you
>>>>> would use a chained block approach on such a tiny machine! Perhaps
>>>>> you meant to say the design
>>>>> doesn't scale /down/ rather than up? (And the size of chained
>>>>> blocks can be dynamically decided at
>>>>> run time if we like.)
>>>>>
>>>>> Other designs, e.g. using vector or strings will involve copying
>>>>> ever larger blocks of memory around
>>>>> when the vector/string is extended, so perhaps you meant to say
>>>>> that /those/ designs don't scale up,
>>>>> but the chained blocks scale up?
>>>>>
>>>> I was thinking that the chained block degenerates into effectively a
>>>> linked list when block size becomes
>>>> small in relation to tape length. However that isn't really a
>>>> problem - it still works more effectively
>>>> than a contiguous model.
>>>
>>> Yes, for a fixed block length it will be like a tape element linked
>>> list, but only some small fraction of the allocation overhead.
>>> Bigger blocks resulting in a smaller fraction.  Or we could have some
>>> kind of exponential block size growth, so we start with, say, 1
>>> allocation cost for the first 50000 tape elements, then getting
>>> smaller as blocks get bigger - but 1 allocation per 50000 tape
>>> elements is already a pretty small overhead for most purposes.  E.g.
>>> writing/testing PO's Even TM, we could make do with one single fixed
>>> block of just 20 tape elements!!! I'd think the key thing for PO
>>> should be to get on with the exercise, rather than playing with TM
>>> emulator efficiency.
>>>
>>> Mike.
>>
>> It is more cost-effective to make it right the first time rather than
>> have to go back and fix it.
>>
>> My adaptation of David's approach to the TM tape also seems to be an
>> objectively better way to implement std::deque.
>>
>> I can't possibly do the exercise until I see 100% exactly how the
>> transition function works. Although it is exactly the same idea as a
>> DFA state transition, its seems to not be working that way.
>
> Yes the idea is the same but slightly more complicated.  What seems not
> to be working that way?
>
> You could think of a TM as a DFA that's been functionally enhanced to
> allow at each computation step
> i)  left/right (single) stepping of its input tape head
> ii) rewriting of the symbol under the tape head
> whereas a DFA is restricted to work with strictly right stepping of its
> "input tape head" so it only sees each character once (and so no concept
> of rewriting anything because it couldn't be reread anyway).
>
> So compared to a DFA transition rule, a TM rule still takes the same
> input as a DFA (current state, input character), but has to specify two
> additional data items:
> i)  the direction to move the tape head.
> ii) the character to write back to the tape and
>
> For completeness, if you're familiar with DFAs but TMs not so much, I'll
> add:
>
> A) The DFA/TM termination conditions are a bit different.  A DFA halts
> naturally at the end of the input string, so it's fine (and typical) to
> have accept/reject states that are entered multiple times during a
> computation, i.e. those states aren't "final" states in the TM sense.  A
> TM clearly needs some other way to explicitly indicate it's finished.
> Typically (e.g. Linz) some TM states are designated "final" states that
> halt the TM - if it has accept/reject states those are final, so can
> only be entered once.  (If we converted a DFA to a TM, we would need
> some obvious fiddling when we get to the DFA accept/reject states -
> simply designating them as TM final states wouldn't work...)
>
> B) The TM input tape is /potentially infinite/ in extent so there needs
> to be the rule for what's on the tape outside of its designated "input
> string" at the beginning of a computation.  That's what the TM BLANK
> symbol is for.  (DFA's by design can't get "beyond their input string",
> so no concept of a special BLANK symbol arises.)
>
>
> Mike.

I think that I already knew all that stuff. I have two patents on DFA's
so I know them well. They match screen pixels to recognized characters.
The second patent is a patentable memory optimization of the first.

I only got an very detailed looks at TM's in the last few days on the
basis of this system: http://www.lns.mit.edu/~dsw/turing/turing.html
I am rewriting it so that it has a three minute learning curve.

--
Copyright 2022 Pete Olcott

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

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

<XtydnWO7kvJnHeH_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 11 May 2022 22:37:30 -0500
Date: Wed, 11 May 2022 22:37:28 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
<t5gkl6$8og$1@gioia.aioe.org>
<0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
<t5hf7p$1kd4$1@gioia.aioe.org>
<aYadnaAI4O_Z0uH_nZ2dnUU7_83NnZ2d@giganews.com>
<t5htes$1hb4$1@gioia.aioe.org>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <t5htes$1hb4$1@gioia.aioe.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <XtydnWO7kvJnHeH_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 142
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-Gw4GW8FGNRGuEs7MrjYxnWNEViPqvZ9FDl0ems4r0jboOpqSmMslDTC/cJuXdWbAsTycdLVc4G8dWQd!oXDjxroyxZmTdCQE+MG9Hyb2ZGjmAPrKlCDDXv5ssuPM3Mzg0VVS9EBtGVS1Zrz0h4xHVbiG5KQ=
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: 8741
 by: olcott - Thu, 12 May 2022 03:37 UTC

On 5/11/2022 10:03 PM, Mike Terry wrote:
> On 12/05/2022 01:05, olcott wrote:
>> On 5/11/2022 6:01 PM, Mike Terry wrote:
>>> On 11/05/2022 22:30, Malcolm McLean wrote:
>>>> On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote:
>>>>> On 11/05/2022 10:19, Malcolm McLean wrote:
>>>>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>>>>>>>
>>>>>>> But what you suggest is quite workable...
>>>>>>>
>>>>>>> I think if I were interested in ultimate efficiency, I might go
>>>>>>> with Jeff's "chained blocks" with a
>>>>>>> comfortably large chosen page size. (But efficiency really isn't
>>>>>>> an issue for this task!)
>>>>>>>
>>>>>> The tape is unbounded. And even some very simple machines will
>>>>>> fill it up to infinity.
>>>>>> If you stop the machine when the process runs out of memory, which
>>>>>> is a reasonable
>>>>>> strategy, you don't want O(N) tape write operations.
>>>>>>
>>>>>> Chained blocks are probably the best model. They don't scale up,
>>>>>> so a machine that was written
>>>>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern
>>>>>> desktop. If you know
>>>>>> the approximate szie of your tape, however, then blocks are a good
>>>>>> solution.
>>>>>>
>>>>> I don't get why you say a chained block approach doesn't scale up.
>>>>> Such a design works well until
>>>>> the logical (user) address space is filled, which is absolutely
>>>>> huge on a modern 64-bit machine with
>>>>> page files etc.. When the tape gets very large, only a small
>>>>> portion of it needs to be in the
>>>>> working set for the process to avoid paging.
>>>>>
>>>>> The only design I can think of that might scale up better would be
>>>>> one using an output device larger
>>>>> than the logical address space limit. Maybe you were just saying
>>>>> that a hard-coded small block size
>>>>> (for a ZX81?) is not as efficient as big blocks if you've got lots
>>>>> of memory? I don't see that you
>>>>> would use a chained block approach on such a tiny machine! Perhaps
>>>>> you meant to say the design
>>>>> doesn't scale /down/ rather than up? (And the size of chained
>>>>> blocks can be dynamically decided at
>>>>> run time if we like.)
>>>>>
>>>>> Other designs, e.g. using vector or strings will involve copying
>>>>> ever larger blocks of memory around
>>>>> when the vector/string is extended, so perhaps you meant to say
>>>>> that /those/ designs don't scale up,
>>>>> but the chained blocks scale up?
>>>>>
>>>> I was thinking that the chained block degenerates into effectively a
>>>> linked list when block size becomes
>>>> small in relation to tape length. However that isn't really a
>>>> problem - it still works more effectively
>>>> than a contiguous model.
>>>
>>> Yes, for a fixed block length it will be like a tape element linked
>>> list, but only some small fraction of the allocation overhead.
>>> Bigger blocks resulting in a smaller fraction.  Or we could have some
>>> kind of exponential block size growth, so we start with, say, 1
>>> allocation cost for the first 50000 tape elements, then getting
>>> smaller as blocks get bigger - but 1 allocation per 50000 tape
>>> elements is already a pretty small overhead for most purposes.  E.g.
>>> writing/testing PO's Even TM, we could make do with one single fixed
>>> block of just 20 tape elements!!! I'd think the key thing for PO
>>> should be to get on with the exercise, rather than playing with TM
>>> emulator efficiency.
>>>
>>> Mike.
>>
>> It is more cost-effective to make it right the first time rather than
>> have to go back and fix it.
>>
>> My adaptation of David's approach to the TM tape also seems to be an
>> objectively better way to implement std::deque.
>>
>> I can't possibly do the exercise until I see 100% exactly how the
>> transition function works. Although it is exactly the same idea as a
>> DFA state transition, its seems to not be working that way.
>
> Yes the idea is the same but slightly more complicated.  What seems not
> to be working that way?
>
> You could think of a TM as a DFA that's been functionally enhanced to
> allow at each computation step
> i)  left/right (single) stepping of its input tape head
> ii) rewriting of the symbol under the tape head
> whereas a DFA is restricted to work with strictly right stepping of its
> "input tape head" so it only sees each character once (and so no concept
> of rewriting anything because it couldn't be reread anyway).
>
> So compared to a DFA transition rule, a TM rule still takes the same
> input as a DFA (current state, input character), but has to specify two
> additional data items:
> i)  the direction to move the tape head.
> ii) the character to write back to the tape and
>
> For completeness, if you're familiar with DFAs but TMs not so much, I'll
> add:
>
> A) The DFA/TM termination conditions are a bit different.  A DFA halts
> naturally at the end of the input string, so it's fine (and typical) to
> have accept/reject states that are entered multiple times during a
> computation, i.e. those states aren't "final" states in the TM sense.  A
> TM clearly needs some other way to explicitly indicate it's finished.
> Typically (e.g. Linz) some TM states are designated "final" states that
> halt the TM - if it has accept/reject states those are final, so can
> only be entered once.  (If we converted a DFA to a TM, we would need
> some obvious fiddling when we get to the DFA accept/reject states -
> simply designating them as TM final states wouldn't work...)
>
> B) The TM input tape is /potentially infinite/ in extent so there needs
> to be the rule for what's on the tape outside of its designated "input
> string" at the beginning of a computation.  That's what the TM BLANK
> symbol is for.  (DFA's by design can't get "beyond their input string",
> so no concept of a special BLANK symbol arises.)
>
>
> Mike.

These are the key details of the trasition function that I have been
focusing on:

A transition rule of a Turing machine has the following form
δ(p, X) = (q, Y, L).

This means that from state p, on reading the symbol X on the tape,
the machine moves to state q,
replaces X with Y and
moves the tape head to the left.

--
Copyright 2022 Pete Olcott

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

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

<t5i51b$5so$1@dont-email.me>

 copy mid

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

 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 [ best tape ]
Date: Wed, 11 May 2022 23:13:10 -0600
Organization: A noiseless patient Spider
Lines: 62
Message-ID: <t5i51b$5so$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me> <87a6btx9uz.fsf@bsb.me.uk>
<t5782u$1p6$1@dont-email.me> <878rrcuoj6.fsf@bsb.me.uk>
<t58tdr$93p$1@dont-email.me> <87tu9zubfs.fsf@bsb.me.uk>
<0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com> <87r152qrp2.fsf@bsb.me.uk>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
<t5gkl6$8og$1@gioia.aioe.org>
<0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 12 May 2022 05:13:15 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="899e9a5d00786fd64b8816dcd99a2663";
logging-data="6040"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+t1lnbXTAMevMeZ0UR5LYFTHL3Mu8jy2Y="
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Cancel-Lock: sha1:eEi183p28WzdNvezxZbMFyyE+RI=
In-Reply-To: <0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
Content-Language: en-US
 by: Jeff Barnett - Thu, 12 May 2022 05:13 UTC

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

Right. And by allocating these blocks in multiples of the page (least
common multiple of swap page and cache page size), you'll keep the
caches full of the right stuff. The time overhead is that you must check
if the +1 or -1 positioning to see if you are at a block boundary for
each increment; the storage penalty is that you must keep both a forward
and backward link pointer on each page. This approach can be adapted to
really, really long tapes (>> terabyte) and will be no uglier then other
approaches.

My (not so hidden) assumption are that nobody is really thinking of
dealing with such really, really long tapes, i.e., this whole project is
viewed more as a pedagogical exercise. A second assumption is that the
thing to optimize is cache hits given secondary assumptions that modern
user-level computers have wide and fewer cache "words" so you want
something that almost guarantees that you will "pound" each cache word
many times and that your program including your part of the memory
management will all stay in the cache.

What is really amazing to me is that Ben got such greater throughput
with what he described as a very casual approach! So maybe all of our
talk is rather premature until someone wants to do BB for new state size
bounds.
--
Jeff Barnett

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

<msudnevON-QSA-H_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 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: Thu, 12 May 2022 00:43:43 -0500
Date: Thu, 12 May 2022 00:43:40 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <t5782u$1p6$1@dont-email.me>
<878rrcuoj6.fsf@bsb.me.uk> <t58tdr$93p$1@dont-email.me>
<87tu9zubfs.fsf@bsb.me.uk> <0YCdnamQZ9xbreT_nZ2dnUU7_8zNnZ2d@giganews.com>
<87r152qrp2.fsf@bsb.me.uk> <rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com>
<87wneumegw.fsf@bsb.me.uk> <ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
<87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
<t5gkl6$8og$1@gioia.aioe.org>
<0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
<t5i51b$5so$1@dont-email.me>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <t5i51b$5so$1@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <msudnevON-QSA-H_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 92
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-un717ECk8pglnQux5k1+9N/RWu4Io3l5E+1UatND+VqwKRnrPmbP8hdLkvhOfRxoU6D81SVFCkSbLVG!TmHEk24EjpwB2uS0YlBNxpB7gdRzeXs+PpBjn3Xf3Je3yV/K5umCwA9+DSk1Z37jJmopTbScZYE=
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: 6514
 by: olcott - Thu, 12 May 2022 05:43 UTC

On 5/12/2022 12:13 AM, Jeff Barnett wrote:
> On 5/11/2022 3:30 PM, Malcolm McLean wrote:
>> On Wednesday, 11 May 2022 at 16:27:37 UTC+1, Mike Terry wrote:
>>> On 11/05/2022 10:19, Malcolm McLean wrote:
>>>> On Wednesday, 11 May 2022 at 03:05:37 UTC+1, Mike Terry wrote:
>>>>>
>>>>> But what you suggest is quite workable...
>>>>>
>>>>> I think if I were interested in ultimate efficiency, I might go
>>>>> with Jeff's "chained blocks" with a
>>>>> comfortably large chosen page size. (But efficiency really isn't an
>>>>> issue for this task!)
>>>>>
>>>> The tape is unbounded. And even some very simple machines will fill
>>>> it up to infinity.
>>>> If you stop the machine when the process runs out of memory, which
>>>> is a reasonable
>>>> strategy, you don't want O(N) tape write operations.
>>>>
>>>> Chained blocks are probably the best model. They don't scale up, so
>>>> a machine that was written
>>>> for a 16K ZX81 might struggle when ported to a 16GB typical modern
>>>> desktop. If you know
>>>> the approximate szie of your tape, however, then blocks are a good
>>>> solution.
>>>>
>>> I don't get why you say a chained block approach doesn't scale up.
>>> Such a design works well until
>>> the logical (user) address space is filled, which is absolutely huge
>>> on a modern 64-bit machine with
>>> page files etc.. When the tape gets very large, only a small portion
>>> of it needs to be in the
>>> working set for the process to avoid paging.
>>>
>>> The only design I can think of that might scale up better would be
>>> one using an output device larger
>>> than the logical address space limit. Maybe you were just saying that
>>> a hard-coded small block size
>>> (for a ZX81?) is not as efficient as big blocks if you've got lots of
>>> memory? I don't see that you
>>> would use a chained block approach on such a tiny machine! Perhaps
>>> you meant to say the design
>>> doesn't scale /down/ rather than up? (And the size of chained blocks
>>> can be dynamically decided at
>>> run time if we like.)
>>>
>>> Other designs, e.g. using vector or strings will involve copying ever
>>> larger blocks of memory around
>>> when the vector/string is extended, so perhaps you meant to say that
>>> /those/ designs don't scale up,
>>> but the chained blocks scale up?
>>>
>> I was thinking that the chained block degenerates into effectively a
>> linked list when block size becomes
>> small in relation to tape length. However that isn't really a problem
>> - it still works more effectively
>> than a contiguous model.
>
> Right. And by allocating these blocks in multiples of the page (least
> common multiple of swap page and cache page size), you'll keep the
> caches full of the right stuff. The time overhead is that you must check
> if the +1 or -1 positioning to see if you are at a block boundary for
> each increment; the storage penalty is that you must keep both a forward
> and backward link pointer on each page. This approach can be adapted to
> really, really long tapes (>> terabyte) and will be no uglier then other
> approaches.
>
> My (not so hidden) assumption are that nobody is really thinking of
> dealing with such really, really long tapes, i.e., this whole project is
> viewed more as a pedagogical exercise. A second assumption is that the
> thing to optimize is cache hits given secondary assumptions that modern
> user-level computers have wide and fewer cache "words" so you want
> something that almost guarantees that you will "pound" each cache word
> many times and that your program including your part of the memory
> management will all stay in the cache.
>
> What is really amazing to me is that Ben got such greater throughput
> with what he described as a very casual approach! So maybe all of our
> talk is rather premature until someone wants to do BB for new state size
> bounds.

I am basically making a std::deque based on std::vector that has all of
the speed and space efficiency of std::vector and the functionality of
std::deque. This provides the basis for a two-way TM 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 [ best tape ]

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

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function [ best tape ]
Date: Thu, 12 May 2022 14:45:05 +0100
Organization: A noiseless patient Spider
Lines: 38
Message-ID: <87y1z650gu.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com>
<87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com>
<87lev75zv6.fsf@bsb.me.uk>
<TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1v5xll.fsf@bsb.me.uk>
<2eOdnW7GpMwx6OH_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="b918120b717b1a0036d52ef1ce111b9c";
logging-data="14357"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX182+MN3ysK6KqiKZ5eNHXsm61VIMDzkPAA="
Cancel-Lock: sha1:zP+HvETXDmx4hJ5Iwd7KH5+I7KQ=
sha1:Rd20Sg++asHFBoRpkg5fUwLGubM=
X-BSB-Auth: 1.59d86e22ff8378fdd864.20220512144505BST.87y1z650gu.fsf@bsb.me.uk
 by: Ben - Thu, 12 May 2022 13:45 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/11/2022 8:49 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/11/2022 8:00 PM, Ben wrote:
>>
>>>> Can't you even post the code for the function that moves and/or updates
>>>> the tape? Surely that part is now written? That way we'd know what
>>>> data structure you are using...
>>>
>>> struct Tape
>>> {
>>> unsigned int Tape_Head;
>>> std::vector<unsigned char> Left;
>>> std::vector<unsigned char> Right;
>>> unsigned int move_left();
>>> unsigned int move_right();
>>> };
>>>
>>> The part of mapping Tape_Head to a location in Left or Right needs
>>> more desk checking before I will implement it.
>> How long is that going to take?
>
> Less than 8 labor hours, maybe 2 labor hours.

For just the tape? Surely not. I wanted to resolve what data structure
you are actually gong to be using.

> I only work on it for 5 minutes every 2 hours.

So may be another 12 days. Oh well, I'll see if I can apply the "tying
the knot" trick to my Haskell code...

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

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

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

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function [ best tape ]
Date: Thu, 12 May 2022 15:02:20 +0100
Organization: A noiseless patient Spider
Lines: 42
Message-ID: <87sfpe4zo3.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com>
<87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
<87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
<t5gkl6$8og$1@gioia.aioe.org>
<0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
<t5hf7p$1kd4$1@gioia.aioe.org>
<aYadnaAI4O_Z0uH_nZ2dnUU7_83NnZ2d@giganews.com>
<t5htes$1hb4$1@gioia.aioe.org>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="b918120b717b1a0036d52ef1ce111b9c";
logging-data="14357"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19Y22dKGWjYq+exQFFAjA7mqNcKcILL7z4="
Cancel-Lock: sha1:eYMvukjlllP3t/RKlVirgwPU79o=
sha1:RyMq+Lpee35w1WUZY2CuHhD/u58=
X-BSB-Auth: 1.4c17240909039a06c573.20220512150220BST.87sfpe4zo3.fsf@bsb.me.uk
 by: Ben - Thu, 12 May 2022 14:02 UTC

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

> You could think of a TM as a DFA that's been functionally enhanced to
> allow at each computation step
> i) left/right (single) stepping of its input tape head
> ii) rewriting of the symbol under the tape head whereas a DFA is
> restricted to work with strictly right stepping of its "input tape
> head" so it only sees each character once (and so no concept of
> rewriting anything because it couldn't be reread anyway).

Though one used to talk about "transducer" DFAs where each edge of the
graph also had an output symbol. This was not "written" anywhere but
the result was the concatenation of output after processing the input.

<cut>
> A) The DFA/TM termination conditions are a bit different. A DFA halts
> naturally at the end of the input string, so it's fine (and typical)
> to have accept/reject states that are entered multiple times during a
> computation, i.e. those states aren't "final" states in the TM sense.
> A TM clearly needs some other way to explicitly indicate it's
> finished. Typically (e.g. Linz) some TM states are designated "final"
> states that halt the TM - if it has accept/reject states those are
> final, so can only be entered once.

This is, as you say, typical. But it's horrid! Almost every author
seems to copy this ancient idea, but there's no need for the
complication. A TM halts "naturally" when in a state that has no
defined transition for the current input. If you want and accept/reject
notion, then one can use a simple convention that the TM accepts if it
halts in a state with no defined transitions at all, but rejects if it
halts in state with defined transitions, none of which apply for the
current input.

A few people prefer not to bother with accepting and rejecting states at
all, but instead just use the resulting tape. For example, the TM is
deemed to have rejected the input if the tape is empty (i.e. contains no
non-blank symbols).

Both of these make the presentation simpler for teaching this material.

--
Ben.

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

<XdadnZj8avjLteD_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

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

 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: Thu, 12 May 2022 10:31:34 -0500
Date: Thu, 12 May 2022 10:31: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 [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com> <87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com> <87lev75zv6.fsf@bsb.me.uk>
<TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1v5xll.fsf@bsb.me.uk>
<2eOdnW7GpMwx6OH_nZ2dnUU7_81g4p2d@giganews.com> <87y1z650gu.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87y1z650gu.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <XdadnZj8avjLteD_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 47
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-bXox4Zp9J3kIXZDuFKnbiP2ZF7L4OmET3t4I8JViWvb7Gmzg/9fGqcsN+xlXgrnk9E2B9p09MqjApEx!RoBVSQ+3dBe0MMzXGDY7DVnX6bgR2jO4P0mP07iEbPo8qvFWCYIcghPmG1IN/H+5vQU9aq8bYd0=
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: 3549
 by: olcott - Thu, 12 May 2022 15:31 UTC

On 5/12/2022 8:45 AM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/11/2022 8:49 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/11/2022 8:00 PM, Ben wrote:
>>>
>>>>> Can't you even post the code for the function that moves and/or updates
>>>>> the tape? Surely that part is now written? That way we'd know what
>>>>> data structure you are using...
>>>>
>>>> struct Tape
>>>> {
>>>> unsigned int Tape_Head;
>>>> std::vector<unsigned char> Left;
>>>> std::vector<unsigned char> Right;
>>>> unsigned int move_left();
>>>> unsigned int move_right();
>>>> };
>>>>
>>>> The part of mapping Tape_Head to a location in Left or Right needs
>>>> more desk checking before I will implement it.
>>> How long is that going to take?
>>
>> Less than 8 labor hours, maybe 2 labor hours.
>
> For just the tape? Surely not. I wanted to resolve what data structure
> you are actually gong to be using.
>
>> I only work on it for 5 minutes every 2 hours.
>
> So may be another 12 days. Oh well, I'll see if I can apply the "tying
> the knot" trick to my Haskell code...
>

I have it almost done. I staid up late working on it.
I got very enthused. This is lots of fun. It is also essentially
basically a significant improvement to how std::deque could be implemented.

--
Copyright 2022 Pete Olcott

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

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

<rNadnW2d0_Zm1uD_nZ2dnUU7-VfNnZ2d@brightview.co.uk>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 12 May 2022 13:03:39 -0500
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me>
<rY-dnR7-lJoiBeT_nZ2dnUU7_83NnZ2d@giganews.com> <87wneumegw.fsf@bsb.me.uk>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
<t5gkl6$8og$1@gioia.aioe.org>
<0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
<t5hf7p$1kd4$1@gioia.aioe.org>
<aYadnaAI4O_Z0uH_nZ2dnUU7_83NnZ2d@giganews.com>
<t5htes$1hb4$1@gioia.aioe.org> <87sfpe4zo3.fsf@bsb.me.uk>
From: news.dea...@darjeeling.plus.com (Mike Terry)
Date: Thu, 12 May 2022 19:03:39 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.7.1
MIME-Version: 1.0
In-Reply-To: <87sfpe4zo3.fsf@bsb.me.uk>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <rNadnW2d0_Zm1uD_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
Lines: 97
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-wcfSE3Hg790mCvoe0Cr9U/q2ZM0iKrdNZXbCyQey1TAV6af9H/8UUjq8o1fQvsjvWRdUFMzkYSACFOb!TxhxNhNzQXgKpyoJVerdHAKTIRY1MdRBVMEMIrsMO97p3gBfgQtfz9rgLEltKamuitK6h3yNhDyK!DehzqvwvKvJYvcoB6ajhZmRvqUM=
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: 8276
 by: Mike Terry - Thu, 12 May 2022 18:03 UTC

On 12/05/2022 15:02, Ben wrote:
> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>
>> You could think of a TM as a DFA that's been functionally enhanced to
>> allow at each computation step
>> i) left/right (single) stepping of its input tape head
>> ii) rewriting of the symbol under the tape head whereas a DFA is
>> restricted to work with strictly right stepping of its "input tape
>> head" so it only sees each character once (and so no concept of
>> rewriting anything because it couldn't be reread anyway).
>
> Though one used to talk about "transducer" DFAs where each edge of the
> graph also had an output symbol. This was not "written" anywhere but
> the result was the concatenation of output after processing the input.
>
> <cut>
>> A) The DFA/TM termination conditions are a bit different. A DFA halts
>> naturally at the end of the input string, so it's fine (and typical)
>> to have accept/reject states that are entered multiple times during a
>> computation, i.e. those states aren't "final" states in the TM sense.
>> A TM clearly needs some other way to explicitly indicate it's
>> finished. Typically (e.g. Linz) some TM states are designated "final"
>> states that halt the TM - if it has accept/reject states those are
>> final, so can only be entered once.
>
> This is, as you say, typical. But it's horrid! Almost every author
> seems to copy this ancient idea, but there's no need for the
> complication. A TM halts "naturally" when in a state that has no
> defined transition for the current input.

From a programming perspective, I can see how that's a bit more convenient, but I don't like the
idea that much - e.g. with an explicit halt state we can see it clearly on the state transition
diagram (as one of the destination circles pointed to by arrows). The alternative is having to
inspect all the circles and identify those which are lacking some transition rule - that's lacking
transparency in my opinion. (And if I identify such a state missing one or more arrows, am I to
assume that's deliberate to create a halt condition, or does the author simply know that those
conditions will never arise during execution, and was being "lazy"?)

I wouldn't mind some kind of "special arrow" which incorporates a stop sign, but that's hardly
different from having it lead to a proper state designated as a halt state. (The stop sign would be
part of the arrow, not an actual TM state.) But now, logically we have two valid candidates for a
transition rule: a normal one, or a special "stop arrow", which logically complicates the definition
slightly. (But it's ok)

So I'm thinking that an explicit halt state is maybe the most (conceptually) logical way to do it,
and I like "conceptually logical". To me the "no defined transition rule" seems like a kind of hack
invented by a programmer to save a few lines of code! (I've nothing against programmers of course,
and if you teach people to program TM simulators, I can see the appeal of the idea.)

> If you want and accept/reject
> notion, then one can use a simple convention that the TM accepts if it
> halts in a state with no defined transitions at all, but rejects if it
> halts in state with defined transitions, none of which apply for the
> current input.

That seems (conceptually) awful to me! I mean, where's the /logic/ in that, beyond making the
programming task well defined for someone building a TM simulator? It's like a programmer logically
needing some extra state info (a flag, say) to represent some program condition, but saying "hang on
- I don't need to create that flag, because I can use some other artificial setting of an existing
variable to indicate a special condition, and look - I save having to create the extra flag!!".
Well, perhaps the flag was the logical (and so IMO better) thing to do all along. (Thinks: file
readchar/readbyte returning EOF as a special character value in lieu of a genuine data byte. Simply
Not Logical IMO...)

Perhaps if I were more bold I might suggest your perspective could be overly shaped by your day to
day job experience of teaching the /simulation/ side of the subject... :)

For me, TMs are /mathematical/ constructs, used to discuss the nature of computation and limits of
algorithms etc.. So naturally I like logical mathematical definitions. For me, the weighting (out
of 10) I'd apply to "making a programmer's job easier when coding a TM simulator" would be 0. I
mean, it's not /that/ hard whichever way we go.

>
> A few people prefer not to bother with accepting and rejecting states at
> all, but instead just use the resulting tape. For example, the TM is
> deemed to have rejected the input if the tape is empty (i.e. contains no
> non-blank symbols).

Isn't there a problem here, in that now we can't actually tell when a computation is finished? Say
after 10^234829873473829 steps no output has been written - what does that signify? OK, "nothing"
is an answer, but then is this actually in line with our original intuitions which were concerning
/finite/ algorithms? This is a bit more like when TMs are /acceptors/ (recognisers?) rather than
deciders, but even then, if a non-blank is written to the tape, it could be subsequently blanked out
again, so its not really like an acceptor.

Perhaps something like "accept if 0 is ever written to the tape, reject if 1 is ever written"? That
would logially work I guess. I do understand that there are a million TM variations in play in the
literature, and that's before we get on to how they should be /used/ e.g. in defining computable
functions, which need further decisions on how inputs/outputs are to be representated.

OK it's only now occured to me that you didn't say "..not to bother with *final* states.." or "..not
to bother with *halting*..". So I'm sure you meant having some explicit HALT action, followed by
checking the tape to distinguish the halting reason - which makes perfect sense, and is maybe how I
would have invented TMs (Terry-machines of course) :)

Mike.

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

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

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function [ best tape ]
Date: Thu, 12 May 2022 19:30:16 +0100
Organization: A noiseless patient Spider
Lines: 130
Message-ID: <87h75u4n9j.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com>
<87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
<t5gkl6$8og$1@gioia.aioe.org>
<0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
<t5hf7p$1kd4$1@gioia.aioe.org>
<aYadnaAI4O_Z0uH_nZ2dnUU7_83NnZ2d@giganews.com>
<t5htes$1hb4$1@gioia.aioe.org> <87sfpe4zo3.fsf@bsb.me.uk>
<rNadnW2d0_Zm1uD_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="b918120b717b1a0036d52ef1ce111b9c";
logging-data="22426"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18STIGvxnAhDvtUDBLUP63d1ekM+3i/Dq4="
Cancel-Lock: sha1:sz29bL6oZHcKIx4uPRzRert0fkM=
sha1:I/Ehhz27yya69woxxf+0/WwmKGA=
X-BSB-Auth: 1.7978b80e3c2dae2417b3.20220512193016BST.87h75u4n9j.fsf@bsb.me.uk
 by: Ben - Thu, 12 May 2022 18:30 UTC

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:

> On 12/05/2022 15:02, Ben wrote:
>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>
>>> You could think of a TM as a DFA that's been functionally enhanced to
>>> allow at each computation step
>>> i) left/right (single) stepping of its input tape head
>>> ii) rewriting of the symbol under the tape head whereas a DFA is
>>> restricted to work with strictly right stepping of its "input tape
>>> head" so it only sees each character once (and so no concept of
>>> rewriting anything because it couldn't be reread anyway).
>> Though one used to talk about "transducer" DFAs where each edge of the
>> graph also had an output symbol. This was not "written" anywhere but
>> the result was the concatenation of output after processing the input.
>> <cut>
>>> A) The DFA/TM termination conditions are a bit different. A DFA halts
>>> naturally at the end of the input string, so it's fine (and typical)
>>> to have accept/reject states that are entered multiple times during a
>>> computation, i.e. those states aren't "final" states in the TM sense.
>>> A TM clearly needs some other way to explicitly indicate it's
>>> finished. Typically (e.g. Linz) some TM states are designated "final"
>>> states that halt the TM - if it has accept/reject states those are
>>> final, so can only be entered once.
>> This is, as you say, typical. But it's horrid! Almost every author
>> seems to copy this ancient idea, but there's no need for the
>> complication. A TM halts "naturally" when in a state that has no
>> defined transition for the current input.
>
> From a programming perspective, I can see how that's a bit more
> convenient, but I don't like the idea that much - e.g. with an
> explicit halt state we can see it clearly on the state transition
> diagram (as one of the destination circles pointed to by arrows). The
> alternative is having to inspect all the circles and identify those
> which are lacking some transition rule - that's lacking transparency
> in my opinion.
>
> (And if I identify such a state missing one or more arrows, am I to
> assume that's deliberate to create a halt condition, or does the
> author simply know that those conditions will never arise during
> execution, and was being "lazy"?)

When reasoning about termination, you have to consider halting in
non-final states, so I don't think it matters much.

> So I'm thinking that an explicit halt state is maybe the most
> (conceptually) logical way to do it, and I like "conceptually
> logical". To me the "no defined transition rule" seems like a kind of
> hack invented by a programmer to save a few lines of code! (I've
> nothing against programmers of course, and if you teach people to
> program TM simulators, I can see the appeal of the idea.)
>
>> If you want and accept/reject
>> notion, then one can use a simple convention that the TM accepts if it
>> halts in a state with no defined transitions at all, but rejects if it
>> halts in state with defined transitions, none of which apply for the
>> current input.
>
> That seems (conceptually) awful to me! I mean, where's the /logic/ in
> that, beyond making the programming task well defined for someone
> building a TM simulator?

The logic here that you have to consider the one case anyway (halting
because of no defined transition) and the second case is as explicit as
you'd like -- a state with no out-going arrows. You can even agree to
draw double circles of these.

> Perhaps if I were more bold I might suggest your perspective could be
> overly shaped by your day to day job experience of teaching the
> /simulation/ side of the subject... :)

That's possible. Though one almost always just does this as a sketch.
The full details of a UTM are messy and don't really add much.

> For me, TMs are /mathematical/ constructs, used to discuss the nature
> of computation and limits of algorithms etc.. So naturally I like
> logical mathematical definitions. For me, the weighting (out of 10)
> I'd apply to "making a programmer's job easier when coding a TM
> simulator" would be 0. I mean, it's not /that/ hard whichever way we
> go.

I don't see it like that at all. The reasoning about TMs is not made
any easier by the usual definitions unless, possibly, you insist that
the state transition function always maps every member of the tape
alphabet.

>> A few people prefer not to bother with accepting and rejecting states at
>> all, but instead just use the resulting tape. For example, the TM is
>> deemed to have rejected the input if the tape is empty (i.e. contains no
>> non-blank symbols).
>
> Isn't there a problem here, in that now we can't actually tell when a
> computation is finished? Say after 10^234829873473829 steps no output
> has been written - what does that signify? OK, "nothing" is an
> answer, but then is this actually in line with our original intuitions
> which were concerning /finite/ algorithms? This is a bit more like
> when TMs are /acceptors/ (recognisers?) rather than deciders, but even
> then, if a non-blank is written to the tape, it could be subsequently
> blanked out again, so its not really like an acceptor.

I don't see what you are getting at. How is this different with
explicit final states?

There's no "we watch and see" here because, as you say, TMs are
mathematical constructs and a TM/input pair either denotes a finite
sequence of configurations or it does not.

> Perhaps something like "accept if 0 is ever written to the tape,
> reject if 1 is ever written"? That would logially work I guess.

That would be weird.

> OK it's only now occured to me that you didn't say "..not to bother
> with *final* states.." or "..not to bother with *halting*..". So I'm
> sure you meant having some explicit HALT action, followed by checking
> the tape to distinguish the halting reason - which makes perfect
> sense, and is maybe how I would have invented TMs (Terry-machines of
> course) :)

I'm not sure I follow. Maybe you do see what I'm getting at? A
decider, D, for a set, L(D), is a TM that always halts. It therefore
computes a total function f_D: Σ* -> Σ*. The accept/reject notion is
just a convention that can just as easily be defined as f_D(s) = ""
(say). Similarly, a recogniser computes a partial function.

This is independent of the issue of how and when a TM halts, but my
preference is for both my suggestions.

--
Ben.

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

<z7SdnWv_pvw6w-D_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

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

 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: Thu, 12 May 2022 14:23:19 -0500
Date: Thu, 12 May 2022 14:23:18 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me>
<ZK-dnZTTk9IvIuT_nZ2dnUU7_8xh4p2d@giganews.com> <87fslhn0fj.fsf@bsb.me.uk>
<adebc02c-f8fc-429d-8fbd-6edbebac533an@googlegroups.com>
<874k1xmy1v.fsf@bsb.me.uk> <TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<eIGdnaUnGsd3hOb_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<d4a4f528-98d7-4203-97cc-c7c110b87dbbn@googlegroups.com>
<t5gkl6$8og$1@gioia.aioe.org>
<0b2409e1-6bc0-426d-9a9b-9f8ce84f1c0fn@googlegroups.com>
<t5hf7p$1kd4$1@gioia.aioe.org>
<aYadnaAI4O_Z0uH_nZ2dnUU7_83NnZ2d@giganews.com>
<t5htes$1hb4$1@gioia.aioe.org> <87sfpe4zo3.fsf@bsb.me.uk>
<rNadnW2d0_Zm1uD_nZ2dnUU7-VfNnZ2d@brightview.co.uk>
<87h75u4n9j.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87h75u4n9j.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <z7SdnWv_pvw6w-D_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 157
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-UOrv9cBFhVvg9pd7kZj40XBnd/RNcEO3DzrGSfCch2EY9RFxe2h93TxI4RragIi/XvgUDD5oED7s6K8!deKb7GFFyKT46P1YwkfhtgcgWnt/bRqUFbp47IfVuVdXjOpMYkhVB+vkF7Qwou6NHZSQ+erAX3I=
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: 9755
 by: olcott - Thu, 12 May 2022 19:23 UTC

On 5/12/2022 1:30 PM, Ben wrote:
> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>
>> On 12/05/2022 15:02, Ben wrote:
>>> Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
>>>
>>>> You could think of a TM as a DFA that's been functionally enhanced to
>>>> allow at each computation step
>>>> i) left/right (single) stepping of its input tape head
>>>> ii) rewriting of the symbol under the tape head whereas a DFA is
>>>> restricted to work with strictly right stepping of its "input tape
>>>> head" so it only sees each character once (and so no concept of
>>>> rewriting anything because it couldn't be reread anyway).
>>> Though one used to talk about "transducer" DFAs where each edge of the
>>> graph also had an output symbol. This was not "written" anywhere but
>>> the result was the concatenation of output after processing the input.
>>> <cut>
>>>> A) The DFA/TM termination conditions are a bit different. A DFA halts
>>>> naturally at the end of the input string, so it's fine (and typical)
>>>> to have accept/reject states that are entered multiple times during a
>>>> computation, i.e. those states aren't "final" states in the TM sense.
>>>> A TM clearly needs some other way to explicitly indicate it's
>>>> finished. Typically (e.g. Linz) some TM states are designated "final"
>>>> states that halt the TM - if it has accept/reject states those are
>>>> final, so can only be entered once.
>>> This is, as you say, typical. But it's horrid! Almost every author
>>> seems to copy this ancient idea, but there's no need for the
>>> complication. A TM halts "naturally" when in a state that has no
>>> defined transition for the current input.
>>
>> From a programming perspective, I can see how that's a bit more
>> convenient, but I don't like the idea that much - e.g. with an
>> explicit halt state we can see it clearly on the state transition
>> diagram (as one of the destination circles pointed to by arrows). The
>> alternative is having to inspect all the circles and identify those
>> which are lacking some transition rule - that's lacking transparency
>> in my opinion.
>>
>> (And if I identify such a state missing one or more arrows, am I to
>> assume that's deliberate to create a halt condition, or does the
>> author simply know that those conditions will never arise during
>> execution, and was being "lazy"?)
>
> When reasoning about termination, you have to consider halting in
> non-final states, so I don't think it matters much.

This is what I am going by:
The Turing machine halts if it is in a state for which there is no
quintuple telling it what to do for the symbol being read. The Turing
machine is said to 'halt in a final state' if there is no quintuple at
all on the list with the given state symbol as a first character. If a
Turing machine halts in a final state for a given tape it is said to
'accept' or 'recognize' the tape.
http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt

>
>> So I'm thinking that an explicit halt state is maybe the most
>> (conceptually) logical way to do it, and I like "conceptually
>> logical". To me the "no defined transition rule" seems like a kind of
>> hack invented by a programmer to save a few lines of code! (I've
>> nothing against programmers of course, and if you teach people to
>> program TM simulators, I can see the appeal of the idea.)
>>
>>> If you want and accept/reject
>>> notion, then one can use a simple convention that the TM accepts if it
>>> halts in a state with no defined transitions at all, but rejects if it
>>> halts in state with defined transitions, none of which apply for the
>>> current input.
>>
>> That seems (conceptually) awful to me! I mean, where's the /logic/ in
>> that, beyond making the programming task well defined for someone
>> building a TM simulator?
>
> The logic here that you have to consider the one case anyway (halting
> because of no defined transition) and the second case is as explicit as
> you'd like -- a state with no out-going arrows. You can even agree to
> draw double circles of these.
>

Seems to say that same as David S. Woodruff's text quoted above.

>> Perhaps if I were more bold I might suggest your perspective could be
>> overly shaped by your day to day job experience of teaching the
>> /simulation/ side of the subject... :)
>
> That's possible. Though one almost always just does this as a sketch.
> The full details of a UTM are messy and don't really add much.
>
>> For me, TMs are /mathematical/ constructs, used to discuss the nature
>> of computation and limits of algorithms etc.. So naturally I like
>> logical mathematical definitions. For me, the weighting (out of 10)
>> I'd apply to "making a programmer's job easier when coding a TM
>> simulator" would be 0. I mean, it's not /that/ hard whichever way we
>> go.
>
> I don't see it like that at all. The reasoning about TMs is not made
> any easier by the usual definitions unless, possibly, you insist that
> the state transition function always maps every member of the tape
> alphabet.
>
>>> A few people prefer not to bother with accepting and rejecting states at
>>> all, but instead just use the resulting tape. For example, the TM is
>>> deemed to have rejected the input if the tape is empty (i.e. contains no
>>> non-blank symbols).
>>
>> Isn't there a problem here, in that now we can't actually tell when a
>> computation is finished? Say after 10^234829873473829 steps no output
>> has been written - what does that signify? OK, "nothing" is an
>> answer, but then is this actually in line with our original intuitions
>> which were concerning /finite/ algorithms? This is a bit more like
>> when TMs are /acceptors/ (recognisers?) rather than deciders, but even
>> then, if a non-blank is written to the tape, it could be subsequently
>> blanked out again, so its not really like an acceptor.
>
> I don't see what you are getting at. How is this different with
> explicit final states?
>
> There's no "we watch and see" here because, as you say, TMs are
> mathematical constructs and a TM/input pair either denotes a finite
> sequence of configurations or it does not.
>

The ultimate measure of the behavior of the code is its correct
simulation or direct execution.

>> Perhaps something like "accept if 0 is ever written to the tape,
>> reject if 1 is ever written"? That would logially work I guess.
>
> That would be weird.
>

Final states named "N" or "Y" seem fine to me.

>> OK it's only now occured to me that you didn't say "..not to bother
>> with *final* states.." or "..not to bother with *halting*..". So I'm
>> sure you meant having some explicit HALT action, followed by checking
>> the tape to distinguish the halting reason - which makes perfect
>> sense, and is maybe how I would have invented TMs (Terry-machines of
>> course) :)
>
> I'm not sure I follow. Maybe you do see what I'm getting at? A
> decider, D, for a set, L(D), is a TM that always halts. It therefore
> computes a total function f_D: Σ* -> Σ*. The accept/reject notion is
> just a convention that can just as easily be defined as f_D(s) = ""
> (say). Similarly, a recogniser computes a partial function.
>
> This is independent of the issue of how and when a TM halts, but my
> preference is for both my suggestions.
>

--
Copyright 2022 Pete Olcott

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

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

<875yma4i6b.fsf@bsb.me.uk>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function [ best tape ]
Date: Thu, 12 May 2022 21:20:12 +0100
Organization: A noiseless patient Spider
Lines: 57
Message-ID: <875yma4i6b.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk> <20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com>
<87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com>
<87lev75zv6.fsf@bsb.me.uk>
<TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1v5xll.fsf@bsb.me.uk>
<2eOdnW7GpMwx6OH_nZ2dnUU7_81g4p2d@giganews.com>
<87y1z650gu.fsf@bsb.me.uk>
<XdadnZj8avjLteD_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="b918120b717b1a0036d52ef1ce111b9c";
logging-data="27725"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19TSRfWzPx0wnuKX7Kzi3iv2IqqhUDMx5c="
Cancel-Lock: sha1:RrhCd8zOK5H3GGfsUNgrCR1h2DA=
sha1:Eusz8+KWZ6Sf9A1ktyAcPkiLlkk=
X-BSB-Auth: 1.2bf1edde9a10d58765af.20220512212012BST.875yma4i6b.fsf@bsb.me.uk
 by: Ben - Thu, 12 May 2022 20:20 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/12/2022 8:45 AM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/11/2022 8:49 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/11/2022 8:00 PM, Ben wrote:
>>>>
>>>>>> Can't you even post the code for the function that moves and/or updates
>>>>>> the tape? Surely that part is now written? That way we'd know what
>>>>>> data structure you are using...
>>>>>
>>>>> struct Tape
>>>>> {
>>>>> unsigned int Tape_Head;
>>>>> std::vector<unsigned char> Left;
>>>>> std::vector<unsigned char> Right;
>>>>> unsigned int move_left();
>>>>> unsigned int move_right();
>>>>> };
>>>>>
>>>>> The part of mapping Tape_Head to a location in Left or Right needs
>>>>> more desk checking before I will implement it.
>>>> How long is that going to take?
>>>
>>> Less than 8 labor hours, maybe 2 labor hours.
>> For just the tape? Surely not. I wanted to resolve what data structure
>> you are actually gong to be using.
>>
>>> I only work on it for 5 minutes every 2 hours.
>> So may be another 12 days. Oh well, I'll see if I can apply the "tying
>> the knot" trick to my Haskell code...
>
> I have it almost done.

Not even the two tape movement functions?

> I staid up late working on it.
> I got very enthused. This is lots of fun.

A bit of programming is always fun.

> It is also essentially basically a significant improvement to how
> std::deque could be implemented.

This is ambiguous. It is easy to find an improvement over how
std::deque /could/ be implemented (since it /could/ be implemented
badly), but, on the other hand, I am sure you don't know all the ways
std::deque /could/ be implemented so you can't know you have an
improvement of that sort.

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

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

<oZadnf2QMLKV8uD_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

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

 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: Thu, 12 May 2022 15:33:12 -0500
Date: Thu, 12 May 2022 15:33:11 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com> <87sfphl7iv.fsf@bsb.me.uk>
<20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com> <87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com> <87lev75zv6.fsf@bsb.me.uk>
<TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1v5xll.fsf@bsb.me.uk>
<2eOdnW7GpMwx6OH_nZ2dnUU7_81g4p2d@giganews.com> <87y1z650gu.fsf@bsb.me.uk>
<XdadnZj8avjLteD_nZ2dnUU7_8zNnZ2d@giganews.com> <875yma4i6b.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <875yma4i6b.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <oZadnf2QMLKV8uD_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 75
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-A4aJxgnTX48F+A7EMRYccRHoIxmMC3N60CbHbUVyH1Zttwrjv231Q4zCJJpU5TAKRUGDpnN748tEtA3!E7RdsHDDJ2NmZahzoP8U57sm4FgMVurssHCBcaTjSAQMTdMCFFKp3rgarF56PDvuPfpRLcsWmTg=
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: 4615
 by: olcott - Thu, 12 May 2022 20:33 UTC

On 5/12/2022 3:20 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/12/2022 8:45 AM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/11/2022 8:49 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/11/2022 8:00 PM, Ben wrote:
>>>>>
>>>>>>> Can't you even post the code for the function that moves and/or updates
>>>>>>> the tape? Surely that part is now written? That way we'd know what
>>>>>>> data structure you are using...
>>>>>>
>>>>>> struct Tape
>>>>>> {
>>>>>> unsigned int Tape_Head;
>>>>>> std::vector<unsigned char> Left;
>>>>>> std::vector<unsigned char> Right;
>>>>>> unsigned int move_left();
>>>>>> unsigned int move_right();
>>>>>> };
>>>>>>
>>>>>> The part of mapping Tape_Head to a location in Left or Right needs
>>>>>> more desk checking before I will implement it.
>>>>> How long is that going to take?
>>>>
>>>> Less than 8 labor hours, maybe 2 labor hours.
>>> For just the tape? Surely not. I wanted to resolve what data structure
>>> you are actually gong to be using.
>>>
>>>> I only work on it for 5 minutes every 2 hours.
>>> So may be another 12 days. Oh well, I'll see if I can apply the "tying
>>> the knot" trick to my Haskell code...
>>
>> I have it almost done.
>
> Not even the two tape movement functions?
>
>> I staid up late working on it.
>> I got very enthused. This is lots of fun.
>
> A bit of programming is always fun.
>
>> It is also essentially basically a significant improvement to how
>> std::deque could be implemented.
>
> This is ambiguous. It is easy to find an improvement over how
> std::deque /could/ be implemented (since it /could/ be implemented
> badly), but, on the other hand, I am sure you don't know all the ways
> std::deque /could/ be implemented so you can't know you have an
> improvement of that sort.
>

The Tape_Type is almost done. It is ideal for a two-way TM tape. It has
the key benefit of being able to grow on both ends.

Unlike the messy overhead of the conventional std::deque implementation
it has all of the efficiently of std:vector because it is implemented as
a pair of std::vectors.

Left for growing left and Right for growing right. int Tape_Head >= 0
points to elements of Right, in order.

int Tape_Head < 0 points to elements of Left, such that -1 points to
Left[0] et cetera.

--
Copyright 2022 Pete Olcott

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

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

<20220512213658.0000325b@reddwarf.jmc>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!peer03.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx01.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 [ best tape ]
Message-ID: <20220512213658.0000325b@reddwarf.jmc>
References: <t541t8$upu$1@dont-email.me>
<874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com>
<87sfphl7iv.fsf@bsb.me.uk>
<20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com>
<87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com>
<87lev75zv6.fsf@bsb.me.uk>
<TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1v5xll.fsf@bsb.me.uk>
<2eOdnW7GpMwx6OH_nZ2dnUU7_81g4p2d@giganews.com>
<87y1z650gu.fsf@bsb.me.uk>
<XdadnZj8avjLteD_nZ2dnUU7_8zNnZ2d@giganews.com>
<875yma4i6b.fsf@bsb.me.uk>
<oZadnf2QMLKV8uD_nZ2dnUU7_8zNnZ2d@giganews.com>
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: 71
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Thu, 12 May 2022 20:36:58 UTC
Date: Thu, 12 May 2022 21:36:58 +0100
X-Received-Bytes: 4263
 by: Mr Flibble - Thu, 12 May 2022 20:36 UTC

On Thu, 12 May 2022 15:33:11 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/12/2022 3:20 PM, Ben wrote:
> > olcott <NoOne@NoWhere.com> writes:
> >
> >> On 5/12/2022 8:45 AM, Ben wrote:
> >>> olcott <NoOne@NoWhere.com> writes:
> >>>
> >>>> On 5/11/2022 8:49 PM, Ben wrote:
> >>>>> olcott <NoOne@NoWhere.com> writes:
> >>>>>
> >>>>>> On 5/11/2022 8:00 PM, Ben wrote:
> >>>>>
> >>>>>>> Can't you even post the code for the function that moves
> >>>>>>> and/or updates the tape? Surely that part is now written?
> >>>>>>> That way we'd know what data structure you are using...
> >>>>>>
> >>>>>> struct Tape
> >>>>>> {
> >>>>>> unsigned int Tape_Head;
> >>>>>> std::vector<unsigned char> Left;
> >>>>>> std::vector<unsigned char> Right;
> >>>>>> unsigned int move_left();
> >>>>>> unsigned int move_right();
> >>>>>> };
> >>>>>>
> >>>>>> The part of mapping Tape_Head to a location in Left or Right
> >>>>>> needs more desk checking before I will implement it.
> >>>>> How long is that going to take?
> >>>>
> >>>> Less than 8 labor hours, maybe 2 labor hours.
> >>> For just the tape? Surely not. I wanted to resolve what data
> >>> structure you are actually gong to be using.
> >>>
> >>>> I only work on it for 5 minutes every 2 hours.
> >>> So may be another 12 days. Oh well, I'll see if I can apply the
> >>> "tying the knot" trick to my Haskell code...
> >>
> >> I have it almost done.
> >
> > Not even the two tape movement functions?
> >
> >> I staid up late working on it.
> >> I got very enthused. This is lots of fun.
> >
> > A bit of programming is always fun.
> >
> >> It is also essentially basically a significant improvement to how
> >> std::deque could be implemented.
> >
> > This is ambiguous. It is easy to find an improvement over how
> > std::deque /could/ be implemented (since it /could/ be implemented
> > badly), but, on the other hand, I am sure you don't know all the
> > ways std::deque /could/ be implemented so you can't know you have an
> > improvement of that sort.
> >
>
> The Tape_Type is almost done. It is ideal for a two-way TM tape. It
> has the key benefit of being able to grow on both ends.
>
> Unlike the messy overhead of the conventional std::deque
> implementation it has all of the efficiently of std:vector because it
> is implemented as a pair of std::vectors.

You cannot meet the complexity and element referential integrity
guarantees that std::deque offers with a pair of std::vectors. You are
obviously a C++ n00b.

/Flibble

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

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

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function [ best tape ]
Date: Thu, 12 May 2022 22:02:12 +0100
Organization: A noiseless patient Spider
Lines: 25
Message-ID: <87tu9u31nv.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <87sfphl7iv.fsf@bsb.me.uk>
<20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com>
<871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com>
<87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com>
<87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com>
<87lev75zv6.fsf@bsb.me.uk>
<TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1v5xll.fsf@bsb.me.uk>
<2eOdnW7GpMwx6OH_nZ2dnUU7_81g4p2d@giganews.com>
<87y1z650gu.fsf@bsb.me.uk>
<XdadnZj8avjLteD_nZ2dnUU7_8zNnZ2d@giganews.com>
<875yma4i6b.fsf@bsb.me.uk>
<oZadnf2QMLKV8uD_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="b918120b717b1a0036d52ef1ce111b9c";
logging-data="24566"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19cuSc8FH7AZbDpnSLJWLeIwid3npASa3I="
Cancel-Lock: sha1:osuUyn7NcS2YBYViJRRyH+Vysoo=
sha1:UeP2/2BRgMFMYIY9uS2KxAM9Oog=
X-BSB-Auth: 1.2e9dcd2bae26263171de.20220512220212BST.87tu9u31nv.fsf@bsb.me.uk
 by: Ben - Thu, 12 May 2022 21:02 UTC

olcott <NoOne@NoWhere.com> writes:

> The Tape_Type is almost done.

How complicated are you making it? The two functions that would clear
up, once and for all, what you are really doing should be only a two or
three lines.

> Left for growing left and Right for growing right. int Tape_Head >= 0
> points to elements of Right, in order.
>
> int Tape_Head < 0 points to elements of Left, such that -1 points to
> Left[0] et cetera.

I see. So you are not using two stacks. And what you are implementing
is not a deque, though using two arrays is a standard what to implement
a deque.

I'm curious why this is taking so long. The tape functions will be a
couple of lines...

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

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

<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

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

 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: Thu, 12 May 2022 16:14:30 -0500
Date: Thu, 12 May 2022 16:14:29 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <87sfphl7iv.fsf@bsb.me.uk>
<20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com> <87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com> <87lev75zv6.fsf@bsb.me.uk>
<TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1v5xll.fsf@bsb.me.uk>
<2eOdnW7GpMwx6OH_nZ2dnUU7_81g4p2d@giganews.com> <87y1z650gu.fsf@bsb.me.uk>
<XdadnZj8avjLteD_nZ2dnUU7_8zNnZ2d@giganews.com> <875yma4i6b.fsf@bsb.me.uk>
<oZadnf2QMLKV8uD_nZ2dnUU7_8zNnZ2d@giganews.com> <87tu9u31nv.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87tu9u31nv.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 54
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-WQJ3eBfO2mXGR6rvKTYEj/s2moUKc0/ruViDeFQrfILwDeLzFg9Btr5Z7qRBoknfdT1rkwoLQG69pDh!nt5WmJNSSBmv8c5TCh8Xjwzb+D48VY3bR9SOVtmP2FDB4QSpkMQ2/JokvXRkfrTVbnND5qZzoes=
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: 4007
 by: olcott - Thu, 12 May 2022 21:14 UTC

On 5/12/2022 4:02 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> The Tape_Type is almost done.
>
> How complicated are you making it? The two functions that would clear
> up, once and for all, what you are really doing should be only a two or
> three lines.
>
>> Left for growing left and Right for growing right. int Tape_Head >= 0
>> points to elements of Right, in order.
>>
>> int Tape_Head < 0 points to elements of Left, such that -1 points to
>> Left[0] et cetera.
>
> I see. So you are not using two stacks. And what you are implementing
> is not a deque, though using two arrays is a standard what to implement
> a deque.
>

I am implementing a faster, smaller, cleaner, and simpler std::deque

> I'm curious why this is taking so long. The tape functions will be a
> couple of lines...
>

I hate to define code that is sub-optimal.
It has all of these features of a std::deque

deque (usually pronounced like "deck") is an irregular acronym of
double-ended queue. Double-ended queues are sequence containers with
dynamic sizes that can be expanded or contracted on both ends (either
its front or its back).

Specific libraries may implement deques in different ways, generally as
some form of dynamic array. But in any case, they allow for the
individual elements to be accessed directly through random access
iterators, with storage handled automatically by expanding and
contracting the container as needed.

Therefore, they provide a functionality similar to vectors, but with
efficient insertion and deletion of elements also at the beginning of
the sequence, and not only at its end.
https://www.cplusplus.com/reference/deque/deque/

I think that I have it nearly done now.
It needs more testing, code cleanup and simplification.

--
Copyright 2022 Pete Olcott

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

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

<ecqdnUEriPhi5uD_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

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

 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: Thu, 12 May 2022 16:28:31 -0500
Date: Thu, 12 May 2022 16:28:30 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <874k1xmy1v.fsf@bsb.me.uk>
<TKmdnVOs6o68z-f_nZ2dnUU7_83NnZ2d@giganews.com> <87sfphl7iv.fsf@bsb.me.uk>
<20220510190118.00006b59@reddwarf.jmc>
<f09ecbad-ecbf-4cfe-bdf9-648c30af5794n@googlegroups.com>
<ofSdneReTvjoYOf_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw4lx13.fsf@bsb.me.uk>
<QoCdnVAMjJzvkOb_nZ2dnUU7_83NnZ2d@giganews.com> <871qx0lqkn.fsf@bsb.me.uk>
<pq6dnZ2vEK9vXOb_nZ2dnUU7_81g4p2d@giganews.com> <87sfpf7th7.fsf@bsb.me.uk>
<nP-dnUv6yuQAheH_nZ2dnUU7_83NnZ2d@giganews.com> <87bkw37n1f.fsf@bsb.me.uk>
<Io-dnWGZncLBr-H_nZ2dnUU7_83NnZ2d@giganews.com> <87lev75zv6.fsf@bsb.me.uk>
<TpidnUev2PYi-eH_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1v5xll.fsf@bsb.me.uk>
<2eOdnW7GpMwx6OH_nZ2dnUU7_81g4p2d@giganews.com> <87y1z650gu.fsf@bsb.me.uk>
<XdadnZj8avjLteD_nZ2dnUU7_8zNnZ2d@giganews.com> <875yma4i6b.fsf@bsb.me.uk>
<oZadnf2QMLKV8uD_nZ2dnUU7_8zNnZ2d@giganews.com>
<20220512213658.0000325b@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220512213658.0000325b@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <ecqdnUEriPhi5uD_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 83
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-rx6fOYrnwYT8uBPebnI6141G9rcMeDC/9qTHzf+ZwzL5bOvTVRz9UzDSA4Lor0OJ3Tstp6RrGF0oYEC!OuDDBF46F1P19N9lgkPbeTapTa6fiSACx9NC/LQAJlSSAMhXs1bR9DBZGTvoMqVzRWjylQrSptU=
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: 5153
 by: olcott - Thu, 12 May 2022 21:28 UTC

On 5/12/2022 3:36 PM, Mr Flibble wrote:
> On Thu, 12 May 2022 15:33:11 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/12/2022 3:20 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/12/2022 8:45 AM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/11/2022 8:49 PM, Ben wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/11/2022 8:00 PM, Ben wrote:
>>>>>>>
>>>>>>>>> Can't you even post the code for the function that moves
>>>>>>>>> and/or updates the tape? Surely that part is now written?
>>>>>>>>> That way we'd know what data structure you are using...
>>>>>>>>
>>>>>>>> struct Tape
>>>>>>>> {
>>>>>>>> unsigned int Tape_Head;
>>>>>>>> std::vector<unsigned char> Left;
>>>>>>>> std::vector<unsigned char> Right;
>>>>>>>> unsigned int move_left();
>>>>>>>> unsigned int move_right();
>>>>>>>> };
>>>>>>>>
>>>>>>>> The part of mapping Tape_Head to a location in Left or Right
>>>>>>>> needs more desk checking before I will implement it.
>>>>>>> How long is that going to take?
>>>>>>
>>>>>> Less than 8 labor hours, maybe 2 labor hours.
>>>>> For just the tape? Surely not. I wanted to resolve what data
>>>>> structure you are actually gong to be using.
>>>>>
>>>>>> I only work on it for 5 minutes every 2 hours.
>>>>> So may be another 12 days. Oh well, I'll see if I can apply the
>>>>> "tying the knot" trick to my Haskell code...
>>>>
>>>> I have it almost done.
>>>
>>> Not even the two tape movement functions?
>>>
>>>> I staid up late working on it.
>>>> I got very enthused. This is lots of fun.
>>>
>>> A bit of programming is always fun.
>>>
>>>> It is also essentially basically a significant improvement to how
>>>> std::deque could be implemented.
>>>
>>> This is ambiguous. It is easy to find an improvement over how
>>> std::deque /could/ be implemented (since it /could/ be implemented
>>> badly), but, on the other hand, I am sure you don't know all the
>>> ways std::deque /could/ be implemented so you can't know you have an
>>> improvement of that sort.
>>>
>>
>> The Tape_Type is almost done. It is ideal for a two-way TM tape. It
>> has the key benefit of being able to grow on both ends.
>>
>> Unlike the messy overhead of the conventional std::deque
>> implementation it has all of the efficiently of std:vector because it
>> is implemented as a pair of std::vectors.
>
> You cannot meet the complexity and element referential integrity
> guarantees that std::deque offers with a pair of std::vectors. You are
> obviously a C++ n00b.
>
> /Flibble
>

It has the same Big-O complexity (with less overhead)
As far as referential integrity std::deque does not do very well.
https://www.geeksforgeeks.org/iterator-invalidation-cpp/

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