Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

If God had a beard, he'd be a UNIX programmer.


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 ]

<20220512223343.000062bd@reddwarf.jmc>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!ecngs!feeder2.ecngs.de!178.20.174.213.MISMATCH!feeder1.feed.usenet.farm!feed.usenet.farm!peer02.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: <20220512223343.000062bd@reddwarf.jmc>
References: <t541t8$upu$1@dont-email.me>
<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>
<ecqdnUEriPhi5uD_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: 92
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Thu, 12 May 2022 21:33:42 UTC
Date: Thu, 12 May 2022 22:33:43 +0100
X-Received-Bytes: 5277
 by: Mr Flibble - Thu, 12 May 2022 21:33 UTC

On Thu, 12 May 2022 16:28:30 -0500
olcott <NoOne@NoWhere.com> wrote:

> 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/
You are wrong on both counts:
* referential integrity and iterator invalidation are different
things: when you add or remove elements to either end of a
std::deque iterators are indeed invalidated however references to
existing elements remain valid
* If you do 1000 push_fronts followed by 1000 push_backs followed by
1000 pop_fronts all is good however your next pop_front will have
linear complexity, O(n), as it will necessitate removal of the first
element of the right std::vector.

/Flibble

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

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

 copy mid

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

 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: Fri, 13 May 2022 00:18:48 +0100
Organization: A noiseless patient Spider
Lines: 60
Message-ID: <874k1u2vc7.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me>
<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>
<X9mdnVTySoUr5eD_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="9d7070da1378146bf8b2ebf4ad06ac0b";
logging-data="5242"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+hUvl1m4jyJ6XYK9NYZbHwaIRJYd5wNvo="
Cancel-Lock: sha1:+us6c4gfI/wM4bpID7NDImrjFsc=
sha1:OJfqplOwSvS8xFLXT8Ir9X3hlzM=
X-BSB-Auth: 1.fb18cc97968cd987ba60.20220513001848BST.874k1u2vc7.fsf@bsb.me.uk
 by: Ben - Thu, 12 May 2022 23:18 UTC

olcott <NoOne@NoWhere.com> writes:

> 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

From your description you are not implementing a deque at all, though as
I say, using two arrays is one well-known way to do that.

If you decide to make it an actual deque, what will it be faster,
smaller, cleaner and simpler than? Surely it will be just about the
same speed, no smaller, no cleaner and no simpler than any other deque
implemented with two arrays.

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

Since you are not a data structures or algorithms expert, how can you
possibly tell what is or is not sub-optimal?

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

This is beginning to look like procrastination. First you have the
mountain to climb of reading the documentation for the TM interpreter
you'd chosen. But then you decided you had to implement it all
yourself. And then you got sidetracked by the two stacks idea. And now
you don't like to write code if it's sub-optimal (a hopelessly
indeterminate measure).

Software engineering is about getting the job done on time and in
budget. I've written four interpreters since you started. I'm quite
pleased with the latest Haskell one in that it builds an actual linked
graph of states, something that's not trivial in a functional language.
It runs at 30 million "typical" transitions a second compared with 200
for the C++ one. That's surprisingly in the same ball park. The
Glasgow Haskell compiler is a magnificent achievement.

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

<fCgfK.7814$pqKf.3074@fx12.iad>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!ecngs!feeder2.ecngs.de!178.20.174.213.MISMATCH!feeder1.feed.usenet.farm!feed.usenet.farm!peer03.ams4!peer.am4.highwinds-media.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx12.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>
<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: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <87h75u4n9j.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 146
Message-ID: <fCgfK.7814$pqKf.3074@fx12.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: Thu, 12 May 2022 19:19:41 -0400
X-Received-Bytes: 9544
 by: Richard Damon - Thu, 12 May 2022 23:19 UTC

On 5/12/22 2: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.
>
>> 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.
>

The two views, Halting ONLY in "Final States" or Halting in any state
that doesn't have a Rule defined for the current tape character are
really equivalent (unless you are doing Turing Machine Golf, where the
"size" of the machine is important. A Machine defined by the "Final
State" rule automatically meets the requirements for a "No Rule"
machine, as the Final States, by definition, have no rules leaving them.

If you have a machine defined by the "No Rule" condition, you can
convert it to a "Final State" description by filling in all the states
with some but not all inputs, to transition on the undefined inputs to a
final state (either unique if the end state matters, or one common Final
State).

The "No Rule" termination condition allows for slightly more compact
machines in some cases, but unless you are actually counting states,
(like Busy Beaver) it doesn't really matter.

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

<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com>

 copy mid

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

 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 18:22:59 -0500
Date: Thu, 12 May 2022 18:22:58 -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>
<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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <874k1u2vc7.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com>
Lines: 66
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-dsH5/YLmnk2XHlWuKYAYlrc7ohJkh5sWiMlDRdAncHAh92YIM/7XO2qBmN5EjXOeQyUc8cIA1d40vJp!WdKIt94PKo9rAbWfyzLBkCwRPbWBmVWTmSHxRe2Qnl0ceQobrsLI/LNHvPIfK4Cu9v/uA2MAwyM=
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: 4735
 by: olcott - Thu, 12 May 2022 23:22 UTC

On 5/12/2022 6:18 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> 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
>
> From your description you are not implementing a deque at all, though as
> I say, using two arrays is one well-known way to do that.
>
> If you decide to make it an actual deque, what will it be faster,
> smaller, cleaner and simpler than? Surely it will be just about the
> same speed, no smaller, no cleaner and no simpler than any other deque
> implemented with two arrays.
>
>>> 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.
>
> Since you are not a data structures or algorithms expert, how can you
> possibly tell what is or is not sub-optimal?
>
>> I think that I have it nearly done now.
>> It needs more testing, code cleanup and simplification.
>
> This is beginning to look like procrastination. First you have the
> mountain to climb of reading the documentation for the TM interpreter
> you'd chosen. But then you decided you had to implement it all
> yourself. And then you got sidetracked by the two stacks idea. And now
> you don't like to write code if it's sub-optimal (a hopelessly
> indeterminate measure).
>
> Software engineering is about getting the job done on time and in
> budget. I've written four interpreters since you started. I'm quite
> pleased with the latest Haskell one in that it builds an actual linked
> graph of states, something that's not trivial in a functional language.
> It runs at 30 million "typical" transitions a second compared with 200
> for the C++ one. That's surprisingly in the same ball park. The
> Glasgow Haskell compiler is a magnificent achievement.
>

Its done see my new post.

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

<t5k765$1qcu$1@gioia.aioe.org>

 copy mid

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

 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: Fri, 13 May 2022 01:02:13 +0100
Organization: Aioe.org NNTP Server
Message-ID: <t5k765$1qcu$1@gioia.aioe.org>
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>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: gioia.aioe.org; logging-data="59806"; posting-host="CC3uK9WYEoa7s1kzH7komw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:60.0) Gecko/20100101
Firefox/60.0 SeaMonkey/2.53.7.1
X-Notice: Filtered by postfilter v. 0.9.2
 by: Mike Terry - Fri, 13 May 2022 00:02 UTC

On 12/05/2022 19:30, 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.
>
>> 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.

(ok, but I don't like the "halt because of missing rule" idea either! :) )

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

I'd be ok with insisting that the function is complete rather than partial. Actually, that seems
mathematically most "natural" to me, but I get that it's a /pain/ for a TM programmer, so an
emulator design could relax that requiremnent.

But mainly my point was just that I feel (my preference) is for halting to be totally explicit,
rather than a kind of default/fall back when no transition rule is found. A consequence is that NOT
having a transition rule to apply must simply be not allowed. [Either the transition map is
complete, or in the case of a practical TM simulator it's the TM builder's responsibility to always
have a rule when not in a final state.]

It's not to do with ease of use, but just my desire for the TM definition to match my intuition of
"algorithm" as closely as it can. That intuition is basically the (ancient, pre-TM) flow-chart
which in TM terms becomes the state transition graph, and it seems more natural to have a "STOP"
box, like in a flow-chart. If a flow-chart led to a box that had no arrows readers would say
WTF???, not think "aha, that must mean I've reached the end". But all this is just my preference,
no big deal. Of course I understand they're all equivalent mathematically.

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

Um, at this point I thought you were suggesting the TMs /didn't/ halt, but somehow just used what
was written to the tape to indicate accept/reject!! See final remalks.

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

Agreed! (at this point I was under a misapprehension - see final remarks.)

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


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

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

 copy mid

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

 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: Fri, 13 May 2022 01:10:31 +0100
Organization: A noiseless patient Spider
Lines: 11
Message-ID: <87pmki1edk.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="9d7070da1378146bf8b2ebf4ad06ac0b";
logging-data="29118"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18iBcZxNkZGGAxZYw//mTUhomZlcb6+5ag="
Cancel-Lock: sha1:uwZJeQQl9p3tA7OqA/PjkS8V3Zk=
sha1:gSGLyNBqT1ZswC5/Q3ZkVLHTTSo=
X-BSB-Auth: 1.63f6e9fca49f9873d62c.20220513011032BST.87pmki1edk.fsf@bsb.me.uk
 by: Ben - Fri, 13 May 2022 00:10 UTC

olcott <NoOne@NoWhere.com> writes:

> Its done see my new post.

Apart from the bug/typo it's a perfectly good way to implement a TM
tape. It's not a deque though.

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

<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com>

 copy mid

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

 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 19:58:02 -0500
Date: Thu, 12 May 2022 19:58:01 -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> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87pmki1edk.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com>
Lines: 18
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-dBYSZKNOXUVU21tvUlzlGByfuP3GBn0x56Eb0BEXuRd64cC62kUyM4Qw4Dy7gK1BCPyX5avjcufm4j7!55RNQMI7TdO93eM9GcjNkzUPkPtXILdXT4Z3B0cEUCSE7yn/RhxKgMm02k1Xbw9GbcyiiKQ4MGg=
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: 2482
 by: olcott - Fri, 13 May 2022 00:58 UTC

On 5/12/2022 7:10 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> Its done see my new post.
>
> Apart from the bug/typo it's a perfectly good way to implement a TM
> tape. It's not a deque though.
>

I think that it is a better way to implement a std::deque.
It can be extended to a full 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 ]

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

 copy mid

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

 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: Fri, 13 May 2022 02:54:31 +0100
Organization: A noiseless patient Spider
Lines: 28
Message-ID: <87wneqyz6w.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com>
<87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="9d7070da1378146bf8b2ebf4ad06ac0b";
logging-data="29579"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/TNZ327F+br7G9bMOSh2s2vCC5vrIMspI="
Cancel-Lock: sha1:n1Wib8EVamLa3TAo36ADVxWvPHs=
sha1:HGW+JmlPMNQNIvo3QskLt0P3abw=
X-BSB-Auth: 1.b35f966c9f8577c82a17.20220513025431BST.87wneqyz6w.fsf@bsb.me.uk
 by: Ben - Fri, 13 May 2022 01:54 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/12/2022 7:10 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> Its done see my new post.
>> Apart from the bug/typo it's a perfectly good way to implement a TM
>> tape. It's not a deque though.
>
> I think that it is a better way to implement a std::deque.

Better than what? There are lots of ways to implement a deque and they
all have advantages and disadvantages. Of course, since you have not
implemented any of the deque interface, I can't tell what method might
be thinking of using. Other than it will probably use two vectors.

> It can be extended to a full deque.

It implements exactly none of the functions that make a deque a deque.

Of course is could be extended to be a deque by (a) implementing all of
the member function that a deque should provide and, (b) removing all of
the functions that a deque should not provide.

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

<_4jfK.2551$x1Wf.724@fx10.iad>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx10.iad.POSTED!not-for-mail
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0)
Gecko/20100101 Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com> <87wneqyz6w.fsf@bsb.me.uk>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <87wneqyz6w.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Lines: 32
Message-ID: <_4jfK.2551$x1Wf.724@fx10.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Thu, 12 May 2022 22:09:01 -0400
X-Received-Bytes: 2891
 by: Richard Damon - Fri, 13 May 2022 02:09 UTC

On 5/12/22 9:54 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/12/2022 7:10 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> Its done see my new post.
>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>> tape. It's not a deque though.
>>
>> I think that it is a better way to implement a std::deque.
>
> Better than what? There are lots of ways to implement a deque and they
> all have advantages and disadvantages. Of course, since you have not
> implemented any of the deque interface, I can't tell what method might
> be thinking of using. Other than it will probably use two vectors.
>
>> It can be extended to a full deque.
>
> It implements exactly none of the functions that make a deque a deque.
>
> Of course is could be extended to be a deque by (a) implementing all of
> the member function that a deque should provide and, (b) removing all of
> the functions that a deque should not provide.
>

Which just shows Peter's problem with understanding REQUIREENTS.

Apparently a LONG standing problem, since he didn't get his CS degree
due to failing to meet some of the "minor" requirements.

This failing colors so much of his work.

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

<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com>

 copy mid

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

 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 21:41:17 -0500
Date: Thu, 12 May 2022 21:41:15 -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> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com> <87wneqyz6w.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87wneqyz6w.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com>
Lines: 53
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-qzlpOxmKmY9U1IqGvxhgtbevZudTFu4DxL8M6am08fllrEQE48k/9LLndkSPTSus1tVxlzbBxZJJMYW!fEsnJZjNB/eBvo4tztUwzc5SnDUkdBO5e/TlzsaCygG3NzLQK0Oe892+mdkPgSCTevod/YIjWW8=
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: 3816
 by: olcott - Fri, 13 May 2022 02:41 UTC

On 5/12/2022 8:54 PM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/12/2022 7:10 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> Its done see my new post.
>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>> tape. It's not a deque though.
>>
>> I think that it is a better way to implement a std::deque.
>
> Better than what?

The complex mess of the conventional way to implement std::deque

> There are lots of ways to implement a deque and they
> all have advantages and disadvantages.

If you get maximum
(a) simplicity (b) speed and (c) minimum space what more could you want?

> Of course, since you have not
> implemented any of the deque interface, I can't tell what method might
> be thinking of using. Other than it will probably use two vectors.
>

public:
tape_element& front( ) { return Left.back(); }
tape_element& back() { return Right.back(); }
void pop_front() { Left.pop_back(); }
void pop_back() { Right.pop_back(); }
void push_front(tape_element& E) { Left.push_back(E); }
void push_back(tape_element& E) { Right.push_back(E); }
void reserve(unsigned int N)
{ Left.reserve(N); Right.reserve(N); }

>> It can be extended to a full deque.
>
> It implements exactly none of the functions that make a deque a deque.
>
> Of course is could be extended to be a deque by (a) implementing all of
> the member function that a deque should provide and, (b) removing all of
> the functions that a deque should not provide.
>

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

<t5kvo6$vr1$1@dont-email.me>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: mikko.le...@iki.fi (Mikko)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function [ best tape ]
Date: Fri, 13 May 2022 10:01:26 +0300
Organization: -
Lines: 48
Message-ID: <t5kvo6$vr1$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me> <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> <X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk> <2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk> <MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com> <87wneqyz6w.fsf@bsb.me.uk> <IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="deb0c1ab1dbd645a2fa955a8eccc17da";
logging-data="32609"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+KA/cQnDBcr7Ovi1ZmzE73"
User-Agent: Unison/2.2
Cancel-Lock: sha1:9IC5cf1lHDolXUpELgMN+HK0f6U=
 by: Mikko - Fri, 13 May 2022 07:01 UTC

On 2022-05-13 02:41:15 +0000, olcott said:

> On 5/12/2022 8:54 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> Its done see my new post.
>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>> tape. It's not a deque though.
>>>
>>> I think that it is a better way to implement a std::deque.
>>
>> Better than what?
>
> The complex mess of the conventional way to implement std::deque

Every implementation of a deque is more complex than you need because
a deque and in particular std::deque provides functionality that you
don't need. They also lack functionality that you do need, forcing
additional complexity elsewhere in your code. The missing part is the
tape head position.

...

> public:
> tape_element& front( ) { return Left.back(); }
> tape_element& back() { return Right.back(); }
> void pop_front() { Left.pop_back(); }
> void pop_back() { Right.pop_back(); }
> void push_front(tape_element& E) { Left.push_back(E); }
> void push_back(tape_element& E) { Right.push_back(E); }
> void reserve(unsigned int N)
> { Left.reserve(N); Right.reserve(N); }

You only need three functions:

tape_symbol current_symbol()
void write_symbol(tape_symbol)
void move(direction)

Anything more complex than this would be like killing a fly
with a cannon.

Mikko

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

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

 copy mid

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

 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: Fri, 13 May 2022 11:54:49 +0100
Organization: A noiseless patient Spider
Lines: 48
Message-ID: <87y1z5zoqu.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com>
<87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com>
<87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_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="9d7070da1378146bf8b2ebf4ad06ac0b";
logging-data="2511"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1981ydachRsrRYKnCcOeKKULah/GDvM0Bo="
Cancel-Lock: sha1:j5CmldV1/aUr+roFUh1LCQ4AIjA=
sha1:Vow2iT4IsctH/oSq5Oe+wRmThQs=
X-BSB-Auth: 1.bc49b8f81b1fdaaad506.20220513115449BST.87y1z5zoqu.fsf@bsb.me.uk
 by: Ben - Fri, 13 May 2022 10:54 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/12/2022 8:54 PM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> Its done see my new post.
>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>> tape. It's not a deque though.
>>>
>>> I think that it is a better way to implement a std::deque.
>> Better than what?
>
> The complex mess of the conventional way to implement std::deque
>
>> There are lots of ways to implement a deque and they
>> all have advantages and disadvantages.
>
> If you get maximum
> (a) simplicity (b) speed and (c) minimum space what more could you
> want?

Correctness.

>> Of course, since you have not
>> implemented any of the deque interface, I can't tell what method might
>> be thinking of using. Other than it will probably use two vectors.
>>
>
> public:
> tape_element& front( ) { return Left.back(); }
> tape_element& back() { return Right.back(); }
> void pop_front() { Left.pop_back(); }
> void pop_back() { Right.pop_back(); }
> void push_front(tape_element& E) { Left.push_back(E); }
> void push_back(tape_element& E) { Right.push_back(E); }
> void reserve(unsigned int N)
> { Left.reserve(N); Right.reserve(N); }

This is not correct. Please read a book. Or at least write a test
program and compare with std::deque.

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

<20220513133840.0000732f@reddwarf.jmc>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!feeder1.feed.usenet.farm!feed.usenet.farm!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx03.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: <20220513133840.0000732f@reddwarf.jmc>
References: <t541t8$upu$1@dont-email.me>
<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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com>
<87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com>
<87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com>
<87y1z5zoqu.fsf@bsb.me.uk>
Organization: Jupiter Mining Corp
X-Newsreader: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-w64-mingw32)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Lines: 54
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 13 May 2022 12:38:39 UTC
Date: Fri, 13 May 2022 13:38:40 +0100
X-Received-Bytes: 3430
 by: Mr Flibble - Fri, 13 May 2022 12:38 UTC

On Fri, 13 May 2022 11:54:49 +0100
Ben <ben.usenet@bsb.me.uk> wrote:

> olcott <NoOne@NoWhere.com> writes:
>
> > On 5/12/2022 8:54 PM, Ben wrote:
> >> olcott <NoOne@NoWhere.com> writes:
> >>
> >>> On 5/12/2022 7:10 PM, Ben wrote:
> >>>> olcott <NoOne@NoWhere.com> writes:
> >>>>
> >>>>> Its done see my new post.
> >>>> Apart from the bug/typo it's a perfectly good way to implement a
> >>>> TM tape. It's not a deque though.
> >>>
> >>> I think that it is a better way to implement a std::deque.
> >> Better than what?
> >
> > The complex mess of the conventional way to implement std::deque
> >
> >> There are lots of ways to implement a deque and they
> >> all have advantages and disadvantages.
> >
> > If you get maximum
> > (a) simplicity (b) speed and (c) minimum space what more could you
> > want?
>
> Correctness.
>
> >> Of course, since you have not
> >> implemented any of the deque interface, I can't tell what method
> >> might be thinking of using. Other than it will probably use two
> >> vectors.
> >
> > public:
> > tape_element& front( ) { return Left.back(); }
> > tape_element& back() { return Right.back(); }
> > void pop_front() { Left.pop_back(); }
> > void pop_back() { Right.pop_back(); }
> > void push_front(tape_element& E) { Left.push_back(E); }
> > void push_back(tape_element& E) { Right.push_back(E); }
> > void reserve(unsigned int N)
> > { Left.reserve(N); Right.reserve(N); }
>
> This is not correct. Please read a book. Or at least write a test
> program and compare with std::deque.
Even if we ignore complexity requirements and element reference
stability it is still wrong: what happens if `Left` is empty, `Right` is
non-empty and `pop_front` is called? It simply does not conform to
the std::deque interface.

/Flibble

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

<zdmdnV_tirtr4uP_nZ2dnUU7_8zNnZ2d@giganews.com>

 copy mid

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

 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: Fri, 13 May 2022 10:57:42 -0500
Date: Fri, 13 May 2022 10:57:41 -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> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com> <87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com> <t5kvo6$vr1$1@dont-email.me>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <t5kvo6$vr1$1@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <zdmdnV_tirtr4uP_nZ2dnUU7_8zNnZ2d@giganews.com>
Lines: 101
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-ZBRCzY8pTutwpnR4xInsnbexO/Vgw+iB3ym6luyRzjVDeJ9guifmxg0QOtrS6dY0hx9xczO6gqQMXsq!+FlLD4chDm4FAilkngyCKucEWVWIlTtduwpap6fJz8WagtfpGPxcEcOLxUCMyW7XIexOeCGb22o=
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: 5328
 by: olcott - Fri, 13 May 2022 15:57 UTC

On 5/13/2022 2:01 AM, Mikko wrote:
> On 2022-05-13 02:41:15 +0000, olcott said:
>
>> On 5/12/2022 8:54 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> Its done see my new post.
>>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>>> tape.  It's not a deque though.
>>>>
>>>> I think that it is a better way to implement a std::deque.
>>>
>>> Better than what?
>>
>> The complex mess of the conventional way to implement std::deque
>
> Every implementation of a deque is more complex than you need because
> a deque and in particular std::deque provides functionality that you
> don't need. They also lack functionality that you do need, forcing
> additional complexity elsewhere in your code. The missing part is the
> tape head position.
>

// Tape_Type implements a two-way Turing machine tape.
// Right contains Tape_Head >= 0 values (right expansion)
// Left contains Tape_Head < 0 values (left expansion)
//
// Grows with Right.push_back() as Tape_Head increases above 0.
// Grows with Left.push_back() as Tape_Head decreases below 0.
//
// Tape_Type has functionality very simular to std::deque
// yet implements this functionality much more simply.
// This saves time and space.
//
class Tape_Type
{ public:
typedef unsigned char tape_element;

private:
int Tape_Head = 0; // Can be negative
std::vector<tape_element> Left; // Stores left expansion
std::vector<tape_element> Right; // Stores right expansion

>  ...
>
>> public:
>>    tape_element& front( )      { return Left.back();       }
>>    tape_element& back()        { return Right.back();      }
>>    void pop_front()                  { Left.pop_back();    }
>>    void pop_back()                   { Right.pop_back();   }
>>    void push_front(tape_element& E)  { Left.push_back(E);  }
>>    void push_back(tape_element& E)   { Right.push_back(E); }
>>    void reserve(unsigned int N)
>>                       { Left.reserve(N); Right.reserve(N); }
>
> You only need three functions:
>
>  tape_symbol current_symbol()
>  void write_symbol(tape_symbol)
>  void move(direction)
>
> Anything more complex than this would be like killing a fly
> with a cannon.
>
> Mikko

I took an hour or so to add some std::deque member functions to prove
that they could be added cleanly.

void Write(tape_element Y){ (*this)[Tape_Head] = Y; };
tape_element Read() { return (*this)[Tape_Head]; };

void move_left()
{
Tape_Head--;
int Left_Index = ((Tape_Head * -1) -1);
if (Left_Index == Left.size())
Left.push_back('_');
}

void move_right()
{
Tape_Head++;
if (Tape_Head == Right.size())
Right.push_back('_');
}

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

<zdmdnVjtirshHeP_nZ2dnUU7_8xh4p2d@giganews.com>

 copy mid

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

 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: Fri, 13 May 2022 11:01:00 -0500
Date: Fri, 13 May 2022 11:00:59 -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> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com> <87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com> <87y1z5zoqu.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87y1z5zoqu.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <zdmdnVjtirshHeP_nZ2dnUU7_8xh4p2d@giganews.com>
Lines: 66
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-Kd0fHUvLYyUjy3ZzBI5lIRiURcyHatCWXr1pah5gqmmJ9crq97TYCXddW4M2J1prCIrxmhw6I32H+Y1!28AMi8ORC0V7D2egEv+lnvH20KuaosumLb4V3bWNtQA9ClToLzvDE/jGhFETXHGEWtq5p/bED3I=
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: 4277
 by: olcott - Fri, 13 May 2022 16:00 UTC

On 5/13/2022 5:54 AM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/12/2022 8:54 PM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> Its done see my new post.
>>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>>> tape. It's not a deque though.
>>>>
>>>> I think that it is a better way to implement a std::deque.
>>> Better than what?
>>
>> The complex mess of the conventional way to implement std::deque
>>
>>> There are lots of ways to implement a deque and they
>>> all have advantages and disadvantages.
>>
>> If you get maximum
>> (a) simplicity (b) speed and (c) minimum space what more could you
>> want?
>
> Correctness.
>
>>> Of course, since you have not
>>> implemented any of the deque interface, I can't tell what method might
>>> be thinking of using. Other than it will probably use two vectors.
>>>
>>
>> public:
>> tape_element& front( ) { return Left.back(); }
>> tape_element& back() { return Right.back(); }
>> void pop_front() { Left.pop_back(); }
>> void pop_back() { Right.pop_back(); }
>> void push_front(tape_element& E) { Left.push_back(E); }
>> void push_back(tape_element& E) { Right.push_back(E); }
>> void reserve(unsigned int N)
>> { Left.reserve(N); Right.reserve(N); }
>
> This is not correct. Please read a book. Or at least write a test
> program and compare with std::deque.
>

It is correct within this design:

// Tape_Type implements a two-way Turing machine tape.
// Right contains Tape_Head >= 0 values (right expansion)
// Left contains Tape_Head < 0 values (left expansion)
//
// Grows with Right.push_back() as Tape_Head increases above 0.
// Grows with Left.push_back() as Tape_Head decreases below 0.
//
// Tape_Type has functionality very similar to std::deque
// yet implements this functionality much more simply.
// This saves time and space.
//

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

<t5lvmn$5b2$1@dont-email.me>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: mikko.le...@iki.fi (Mikko)
Newsgroups: comp.theory
Subject: Re: Validating that the implementation meets the spec for TM transition function [ best tape ]
Date: Fri, 13 May 2022 19:06:47 +0300
Organization: -
Lines: 24
Message-ID: <t5lvmn$5b2$1@dont-email.me>
References: <t541t8$upu$1@dont-email.me> <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> <X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk> <2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk> <MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com> <87wneqyz6w.fsf@bsb.me.uk> <IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com> <t5kvo6$vr1$1@dont-email.me> <zdmdnV_tirtr4uP_nZ2dnUU7_8zNnZ2d@giganews.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="bbe16b94f7bb4f08fb64429bb39e7f82";
logging-data="5474"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18+PuDiR3DdxgmV4+fRviTL"
User-Agent: Unison/2.2
Cancel-Lock: sha1:ErSumXD7+bGmd2uVrRdvCjv4zTo=
 by: Mikko - Fri, 13 May 2022 16:06 UTC

On 2022-05-13 15:57:41 +0000, olcott said:

> void Write(tape_element Y){ (*this)[Tape_Head] = Y; };
> tape_element Read() { return (*this)[Tape_Head]; };
>
> void move_left()
> {
> Tape_Head--;
> int Left_Index = ((Tape_Head * -1) -1);
> if (Left_Index == Left.size())
> Left.push_back('_');
> }
>
> void move_right()
> {
> Tape_Head++;
> if (Tape_Head == Right.size())
> Right.push_back('_');
> }

Looks good but needs testing.

Mikko

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

<U8ydnRBPtq-gH-P_nZ2dnUU7_8xh4p2d@giganews.com>

 copy mid

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

 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: Fri, 13 May 2022 11:07:25 -0500
Date: Fri, 13 May 2022 11:07:24 -0500
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
Thunderbird/91.9.0
Subject: Re: Validating that the implementation meets the spec for TM
transition function [ best tape ]
Content-Language: en-US
Newsgroups: comp.theory
References: <t541t8$upu$1@dont-email.me> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com> <87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com> <87y1z5zoqu.fsf@bsb.me.uk>
<20220513133840.0000732f@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220513133840.0000732f@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <U8ydnRBPtq-gH-P_nZ2dnUU7_8xh4p2d@giganews.com>
Lines: 65
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-Z0BTWCo55+utFM1benUaiOsXCO1T+F4bFu8ph40G4dSEuF3Oe7fNOMo/MYtcKXATxI47W2FAJeR8xyv!yYW2+GDUt0XUDtDdlGeejiOeK4u3NndrIqpvjE2Iprq9ead+7LHqN5lMEKr2vnNWrZHhBuKu3dU=
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: 4332
 by: olcott - Fri, 13 May 2022 16:07 UTC

On 5/13/2022 7:38 AM, Mr Flibble wrote:
> On Fri, 13 May 2022 11:54:49 +0100
> Ben <ben.usenet@bsb.me.uk> wrote:
>
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/12/2022 8:54 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> Its done see my new post.
>>>>>> Apart from the bug/typo it's a perfectly good way to implement a
>>>>>> TM tape. It's not a deque though.
>>>>>
>>>>> I think that it is a better way to implement a std::deque.
>>>> Better than what?
>>>
>>> The complex mess of the conventional way to implement std::deque
>>>
>>>> There are lots of ways to implement a deque and they
>>>> all have advantages and disadvantages.
>>>
>>> If you get maximum
>>> (a) simplicity (b) speed and (c) minimum space what more could you
>>> want?
>>
>> Correctness.
>>
>>>> Of course, since you have not
>>>> implemented any of the deque interface, I can't tell what method
>>>> might be thinking of using. Other than it will probably use two
>>>> vectors.
>>>
>>> public:
>>> tape_element& front( ) { return Left.back(); }
>>> tape_element& back() { return Right.back(); }
>>> void pop_front() { Left.pop_back(); }
>>> void pop_back() { Right.pop_back(); }
>>> void push_front(tape_element& E) { Left.push_back(E); }
>>> void push_back(tape_element& E) { Right.push_back(E); }
>>> void reserve(unsigned int N)
>>> { Left.reserve(N); Right.reserve(N); }
>>
>> This is not correct. Please read a book. Or at least write a test
>> program and compare with std::deque.
>
> Even if we ignore complexity requirements and element reference
> stability it is still wrong: what happens if `Left` is empty, `Right` is
> non-empty and `pop_front` is called? It simply does not conform to
> the std::deque interface.
>
> /Flibble
>

Oh, now I see what Ben was saying.
Simply extend my definition of pop_front() to account for this.

--
Copyright 2022 Pete Olcott

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

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

<6ovfK.217$hAre.157@fx08.iad>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!ecngs!feeder2.ecngs.de!178.20.174.213.MISMATCH!feeder1.feed.usenet.farm!feed.usenet.farm!peer01.ams4!peer.am4.highwinds-media.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx08.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> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com> <87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com> <87y1z5zoqu.fsf@bsb.me.uk>
<zdmdnVjtirshHeP_nZ2dnUU7_8xh4p2d@giganews.com>
From: Rich...@Damon-Family.org (Richard Damon)
In-Reply-To: <zdmdnVjtirshHeP_nZ2dnUU7_8xh4p2d@giganews.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Lines: 67
Message-ID: <6ovfK.217$hAre.157@fx08.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: Fri, 13 May 2022 12:08:37 -0400
X-Received-Bytes: 4298
 by: Richard Damon - Fri, 13 May 2022 16:08 UTC

On 5/13/22 12:00 PM, olcott wrote:
> On 5/13/2022 5:54 AM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/12/2022 8:54 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> Its done see my new post.
>>>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>>>> tape.  It's not a deque though.
>>>>>
>>>>> I think that it is a better way to implement a std::deque.
>>>> Better than what?
>>>
>>> The complex mess of the conventional way to implement std::deque
>>>
>>>> There are lots of ways to implement a deque and they
>>>> all have advantages and disadvantages.
>>>
>>> If you get maximum
>>> (a) simplicity (b) speed and (c) minimum space what more could you
>>> want?
>>
>> Correctness.
>>
>>>> Of course, since you have not
>>>> implemented any of the deque interface, I can't tell what method might
>>>> be thinking of using.  Other than it will probably use two vectors.
>>>>
>>>
>>> public:
>>>    tape_element& front( )      { return Left.back();       }
>>>    tape_element& back()        { return Right.back();      }
>>>    void pop_front()                  { Left.pop_back();    }
>>>    void pop_back()                   { Right.pop_back();   }
>>>    void push_front(tape_element& E)  { Left.push_back(E);  }
>>>    void push_back(tape_element& E)   { Right.push_back(E); }
>>>    void reserve(unsigned int N)
>>>                       { Left.reserve(N); Right.reserve(N); }
>>
>> This is not correct.  Please read a book.  Or at least write a test
>> program and compare with std::deque.
>>
>
> It is correct within this design:
>
> // Tape_Type implements a two-way Turing machine tape.
> // Right contains Tape_Head >= 0 values (right expansion)
> // Left  contains Tape_Head  < 0 values (left  expansion)
> //
> // Grows with Right.push_back() as Tape_Head increases above 0.
> // Grows with Left.push_back() as Tape_Head decreases below 0.
> //
> // Tape_Type has functionality very similar to std::deque
> // yet implements this functionality much more simply.
> // This saves time and space.
> //
>

But that isn't the requirements of std:deque, that you claimed you were
improving on.

You seem to not understand the meaning of *a requirement*

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

<20220513171452.00007ddd@reddwarf.jmc>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!news.neodome.net!feeder1.feed.usenet.farm!feed.usenet.farm!peer01.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx14.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: <20220513171452.00007ddd@reddwarf.jmc>
References: <t541t8$upu$1@dont-email.me>
<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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com>
<87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com>
<87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com>
<87y1z5zoqu.fsf@bsb.me.uk>
<20220513133840.0000732f@reddwarf.jmc>
<U8ydnRBPtq-gH-P_nZ2dnUU7_8xh4p2d@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: 67
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 13 May 2022 16:14:51 UTC
Date: Fri, 13 May 2022 17:14:52 +0100
X-Received-Bytes: 4042
 by: Mr Flibble - Fri, 13 May 2022 16:14 UTC

On Fri, 13 May 2022 11:07:24 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/13/2022 7:38 AM, Mr Flibble wrote:
> > On Fri, 13 May 2022 11:54:49 +0100
> > Ben <ben.usenet@bsb.me.uk> wrote:
> >
> >> olcott <NoOne@NoWhere.com> writes:
> >>
> >>> On 5/12/2022 8:54 PM, Ben wrote:
> >>>> olcott <NoOne@NoWhere.com> writes:
> >>>>
> >>>>> On 5/12/2022 7:10 PM, Ben wrote:
> >>>>>> olcott <NoOne@NoWhere.com> writes:
> >>>>>>
> >>>>>>> Its done see my new post.
> >>>>>> Apart from the bug/typo it's a perfectly good way to implement
> >>>>>> a TM tape. It's not a deque though.
> >>>>>
> >>>>> I think that it is a better way to implement a std::deque.
> >>>> Better than what?
> >>>
> >>> The complex mess of the conventional way to implement std::deque
> >>>
> >>>> There are lots of ways to implement a deque and they
> >>>> all have advantages and disadvantages.
> >>>
> >>> If you get maximum
> >>> (a) simplicity (b) speed and (c) minimum space what more could you
> >>> want?
> >>
> >> Correctness.
> >>
> >>>> Of course, since you have not
> >>>> implemented any of the deque interface, I can't tell what method
> >>>> might be thinking of using. Other than it will probably use two
> >>>> vectors.
> >>>
> >>> public:
> >>> tape_element& front( ) { return Left.back(); }
> >>> tape_element& back() { return Right.back(); }
> >>> void pop_front() { Left.pop_back(); }
> >>> void pop_back() { Right.pop_back(); }
> >>> void push_front(tape_element& E) { Left.push_back(E); }
> >>> void push_back(tape_element& E) { Right.push_back(E); }
> >>> void reserve(unsigned int N)
> >>> { Left.reserve(N); Right.reserve(N); }
> >>
> >> This is not correct. Please read a book. Or at least write a test
> >> program and compare with std::deque.
> >
> > Even if we ignore complexity requirements and element reference
> > stability it is still wrong: what happens if `Left` is empty,
> > `Right` is non-empty and `pop_front` is called? It simply does not
> > conform to the std::deque interface.
> >
> > /Flibble
> >
>
> Oh, now I see what Ben was saying.
> Simply extend my definition of pop_front() to account for this.
I will be interested to see how you account for this without
introducing linear, O(n), complexity for that operation.

/Flibble

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

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

 copy mid

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

 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: Fri, 13 May 2022 17:26:02 +0100
Organization: A noiseless patient Spider
Lines: 60
Message-ID: <875ym9z9et.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com>
<87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com>
<87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com>
<87y1z5zoqu.fsf@bsb.me.uk> <20220513133840.0000732f@reddwarf.jmc>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org; posting-host="9d7070da1378146bf8b2ebf4ad06ac0b";
logging-data="12938"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18JIIG4DUz943ZGl5jjd8IOQM7hsKTMCvY="
Cancel-Lock: sha1:P/u7fWToRYbppPx9llfqonH9WgI=
sha1:XQlUzk6ZnyX4doyOWl5qSnCGlX8=
X-BSB-Auth: 1.cac9cc4fc40e9ea59e91.20220513172602BST.875ym9z9et.fsf@bsb.me.uk
 by: Ben - Fri, 13 May 2022 16:26 UTC

Mr Flibble <flibble@reddwarf.jmc> writes:

> On Fri, 13 May 2022 11:54:49 +0100
> Ben <ben.usenet@bsb.me.uk> wrote:
>
>> olcott <NoOne@NoWhere.com> writes:
>>
>> > On 5/12/2022 8:54 PM, Ben wrote:
>> >> olcott <NoOne@NoWhere.com> writes:
>> >>
>> >>> On 5/12/2022 7:10 PM, Ben wrote:
>> >>>> olcott <NoOne@NoWhere.com> writes:
>> >>>>
>> >>>>> Its done see my new post.
>> >>>> Apart from the bug/typo it's a perfectly good way to implement a
>> >>>> TM tape. It's not a deque though.
>> >>>
>> >>> I think that it is a better way to implement a std::deque.
>> >> Better than what?
>> >
>> > The complex mess of the conventional way to implement std::deque
>> >
>> >> There are lots of ways to implement a deque and they
>> >> all have advantages and disadvantages.
>> >
>> > If you get maximum
>> > (a) simplicity (b) speed and (c) minimum space what more could you
>> > want?
>>
>> Correctness.
>>
>> >> Of course, since you have not
>> >> implemented any of the deque interface, I can't tell what method
>> >> might be thinking of using. Other than it will probably use two
>> >> vectors.
>> >
>> > public:
>> > tape_element& front( ) { return Left.back(); }
>> > tape_element& back() { return Right.back(); }
>> > void pop_front() { Left.pop_back(); }
>> > void pop_back() { Right.pop_back(); }
>> > void push_front(tape_element& E) { Left.push_back(E); }
>> > void push_back(tape_element& E) { Right.push_back(E); }
>> > void reserve(unsigned int N)
>> > { Left.reserve(N); Right.reserve(N); }
>>
>> This is not correct. Please read a book. Or at least write a test
>> program and compare with std::deque.
>
> Even if we ignore complexity requirements and element reference
> stability it is still wrong: what happens if `Left` is empty, `Right` is
> non-empty and `pop_front` is called? It simply does not conform to
> the std::deque interface.

Yes, I know. You are inclined to help by pointing this out, but it's so
easy to see that this class is wrong, but I hoped that PO would be
inclined to find out for himself what a deque should do.

--
Ben.

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

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

 copy mid

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

 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: Fri, 13 May 2022 17:27:11 +0100
Organization: A noiseless patient Spider
Lines: 67
Message-ID: <87zgjlxusg.fsf@bsb.me.uk>
References: <t541t8$upu$1@dont-email.me> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com>
<87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com>
<87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com>
<87y1z5zoqu.fsf@bsb.me.uk>
<zdmdnVjtirshHeP_nZ2dnUU7_8xh4p2d@giganews.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader02.eternal-september.org; posting-host="9d7070da1378146bf8b2ebf4ad06ac0b";
logging-data="12938"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/VsPzAJUzNxBmUxI3VfskZ9N6Mg76orhM="
Cancel-Lock: sha1:CST74p2T8HVJl1ejteFbazrxNXo=
sha1:nlxQGeKhOap+zbSLi5y9hoQ8Qd0=
X-BSB-Auth: 1.6f6ec3d5d1911dbd2d70.20220513172711BST.87zgjlxusg.fsf@bsb.me.uk
 by: Ben - Fri, 13 May 2022 16:27 UTC

olcott <NoOne@NoWhere.com> writes:

> On 5/13/2022 5:54 AM, Ben wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/12/2022 8:54 PM, Ben wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> Its done see my new post.
>>>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>>>> tape. It's not a deque though.
>>>>>
>>>>> I think that it is a better way to implement a std::deque.
>>>> Better than what?
>>>
>>> The complex mess of the conventional way to implement std::deque
>>>
>>>> There are lots of ways to implement a deque and they
>>>> all have advantages and disadvantages.
>>>
>>> If you get maximum
>>> (a) simplicity (b) speed and (c) minimum space what more could you
>>> want?
>> Correctness.
>>
>>>> Of course, since you have not
>>>> implemented any of the deque interface, I can't tell what method might
>>>> be thinking of using. Other than it will probably use two vectors.
>>>>
>>>
>>> public:
>>> tape_element& front( ) { return Left.back(); }
>>> tape_element& back() { return Right.back(); }
>>> void pop_front() { Left.pop_back(); }
>>> void pop_back() { Right.pop_back(); }
>>> void push_front(tape_element& E) { Left.push_back(E); }
>>> void push_back(tape_element& E) { Right.push_back(E); }
>>> void reserve(unsigned int N)
>>> { Left.reserve(N); Right.reserve(N); }
>> This is not correct. Please read a book. Or at least write a test
>> program and compare with std::deque.
>>
>
> It is correct within this design:
>
> // Tape_Type implements a two-way Turing machine tape.
> // Right contains Tape_Head >= 0 values (right expansion)
> // Left contains Tape_Head < 0 values (left expansion)
> //
> // Grows with Right.push_back() as Tape_Head increases above 0.
> // Grows with Left.push_back() as Tape_Head decreases below 0.
> //
> // Tape_Type has functionality very similar to std::deque
> // yet implements this functionality much more simply.
> // This saves time and space.

For goodness sake, find out what a deque is and then test our code. Do
you post in the hope that someone will point out all the bugs and the
tell you how to fit it?

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

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

<44CdnVIP0pbtEuP_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!rocksolid2!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 13 May 2022 12:03:44 -0500
Date: Fri, 13 May 2022 12:03:43 -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> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com> <87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com> <87y1z5zoqu.fsf@bsb.me.uk>
<20220513133840.0000732f@reddwarf.jmc>
<U8ydnRBPtq-gH-P_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513171452.00007ddd@reddwarf.jmc>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <20220513171452.00007ddd@reddwarf.jmc>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <44CdnVIP0pbtEuP_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 78
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-Cu87qYa/M75cdzbMYmkQgHThwNfTsEivCyAoX5mgI2dnyLR7rU6g0MIom0V/5BatexJKoWZKmdQoq3r!sVRvE/sGeF9lYrK2xqrwRJPoKbxE1hOLjZVMbo/FcEEKow6wJjYX5p9SqQQjT6dDX5P4O7pI2eI=
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: 4937
 by: olcott - Fri, 13 May 2022 17:03 UTC

On 5/13/2022 11:14 AM, Mr Flibble wrote:
> On Fri, 13 May 2022 11:07:24 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 5/13/2022 7:38 AM, Mr Flibble wrote:
>>> On Fri, 13 May 2022 11:54:49 +0100
>>> Ben <ben.usenet@bsb.me.uk> wrote:
>>>
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 5/12/2022 8:54 PM, Ben wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>
>>>>>>>>> Its done see my new post.
>>>>>>>> Apart from the bug/typo it's a perfectly good way to implement
>>>>>>>> a TM tape. It's not a deque though.
>>>>>>>
>>>>>>> I think that it is a better way to implement a std::deque.
>>>>>> Better than what?
>>>>>
>>>>> The complex mess of the conventional way to implement std::deque
>>>>>
>>>>>> There are lots of ways to implement a deque and they
>>>>>> all have advantages and disadvantages.
>>>>>
>>>>> If you get maximum
>>>>> (a) simplicity (b) speed and (c) minimum space what more could you
>>>>> want?
>>>>
>>>> Correctness.
>>>>
>>>>>> Of course, since you have not
>>>>>> implemented any of the deque interface, I can't tell what method
>>>>>> might be thinking of using. Other than it will probably use two
>>>>>> vectors.
>>>>>
>>>>> public:
>>>>> tape_element& front( ) { return Left.back(); }
>>>>> tape_element& back() { return Right.back(); }
>>>>> void pop_front() { Left.pop_back(); }
>>>>> void pop_back() { Right.pop_back(); }
>>>>> void push_front(tape_element& E) { Left.push_back(E); }
>>>>> void push_back(tape_element& E) { Right.push_back(E); }
>>>>> void reserve(unsigned int N)
>>>>> { Left.reserve(N); Right.reserve(N); }
>>>>
>>>> This is not correct. Please read a book. Or at least write a test
>>>> program and compare with std::deque.
>>>
>>> Even if we ignore complexity requirements and element reference
>>> stability it is still wrong: what happens if `Left` is empty,
>>> `Right` is non-empty and `pop_front` is called? It simply does not
>>> conform to the std::deque interface.
>>>
>>> /Flibble
>>>
>>
>> Oh, now I see what Ben was saying.
>> Simply extend my definition of pop_front() to account for this.
>
> I will be interested to see how you account for this without
> introducing linear, O(n), complexity for that operation.
>
> /Flibble
>

It requires linear, O(n), complexity for that operation.
Tape_Type never needs to do that.

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

<44CdnUwP0pbxDeP_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

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

 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: Fri, 13 May 2022 12:07:56 -0500
Date: Fri, 13 May 2022 12:07:55 -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> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com> <87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com> <87y1z5zoqu.fsf@bsb.me.uk>
<20220513133840.0000732f@reddwarf.jmc> <875ym9z9et.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <875ym9z9et.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <44CdnUwP0pbxDeP_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 69
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-HER+d39iEnpy7s1Wfe7TzghviydOkex5bUshBGKwVte9JwZWXcEuw7wBbPPLK1o1BdtMrGLL5Rru3gF!QYXLd3CBAMaSe/eBeYGNU2wOe6Ftq19GmM6xp9G26P5NKjkvJtV4r+MApMTmf8ifeuZLgN54Hm0=
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: 4605
 by: olcott - Fri, 13 May 2022 17:07 UTC

On 5/13/2022 11:26 AM, Ben wrote:
> Mr Flibble <flibble@reddwarf.jmc> writes:
>
>> On Fri, 13 May 2022 11:54:49 +0100
>> Ben <ben.usenet@bsb.me.uk> wrote:
>>
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/12/2022 8:54 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> Its done see my new post.
>>>>>>> Apart from the bug/typo it's a perfectly good way to implement a
>>>>>>> TM tape. It's not a deque though.
>>>>>>
>>>>>> I think that it is a better way to implement a std::deque.
>>>>> Better than what?
>>>>
>>>> The complex mess of the conventional way to implement std::deque
>>>>
>>>>> There are lots of ways to implement a deque and they
>>>>> all have advantages and disadvantages.
>>>>
>>>> If you get maximum
>>>> (a) simplicity (b) speed and (c) minimum space what more could you
>>>> want?
>>>
>>> Correctness.
>>>
>>>>> Of course, since you have not
>>>>> implemented any of the deque interface, I can't tell what method
>>>>> might be thinking of using. Other than it will probably use two
>>>>> vectors.
>>>>
>>>> public:
>>>> tape_element& front( ) { return Left.back(); }
>>>> tape_element& back() { return Right.back(); }
>>>> void pop_front() { Left.pop_back(); }
>>>> void pop_back() { Right.pop_back(); }
>>>> void push_front(tape_element& E) { Left.push_back(E); }
>>>> void push_back(tape_element& E) { Right.push_back(E); }
>>>> void reserve(unsigned int N)
>>>> { Left.reserve(N); Right.reserve(N); }
>>>
>>> This is not correct. Please read a book. Or at least write a test
>>> program and compare with std::deque.
>>
>> Even if we ignore complexity requirements and element reference
>> stability it is still wrong: what happens if `Left` is empty, `Right` is
>> non-empty and `pop_front` is called? It simply does not conform to
>> the std::deque interface.
>
> Yes, I know. You are inclined to help by pointing this out, but it's so
> easy to see that this class is wrong, but I hoped that PO would be
> inclined to find out for himself what a deque should do.
>

Flibble found a case where my member functions would need to be extended
and this extension may have a worse Big-O than std::deque in some cases.

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

<20220513180900.00003005@reddwarf.jmc>

 copy mid

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

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!news.uzoreto.com!npeer.as286.net!npeer-ng0.as286.net!peer02.ams1!peer.ams1.xlned.com!news.xlned.com!peer02.ams4!peer.am4.highwinds-media.com!news.highwinds-media.com!fx14.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: <20220513180900.00003005@reddwarf.jmc>
References: <t541t8$upu$1@dont-email.me>
<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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com>
<874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com>
<87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com>
<87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com>
<87y1z5zoqu.fsf@bsb.me.uk>
<20220513133840.0000732f@reddwarf.jmc>
<U8ydnRBPtq-gH-P_nZ2dnUU7_8xh4p2d@giganews.com>
<20220513171452.00007ddd@reddwarf.jmc>
<44CdnVIP0pbtEuP_nZ2dnUU7_81g4p2d@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: 81
X-Complaints-To: abuse@eweka.nl
NNTP-Posting-Date: Fri, 13 May 2022 17:08:58 UTC
Date: Fri, 13 May 2022 18:09:00 +0100
X-Received-Bytes: 4733
 by: Mr Flibble - Fri, 13 May 2022 17:09 UTC

On Fri, 13 May 2022 12:03:43 -0500
olcott <NoOne@NoWhere.com> wrote:

> On 5/13/2022 11:14 AM, Mr Flibble wrote:
> > On Fri, 13 May 2022 11:07:24 -0500
> > olcott <NoOne@NoWhere.com> wrote:
> >
> >> On 5/13/2022 7:38 AM, Mr Flibble wrote:
> >>> On Fri, 13 May 2022 11:54:49 +0100
> >>> Ben <ben.usenet@bsb.me.uk> wrote:
> >>>
> >>>> olcott <NoOne@NoWhere.com> writes:
> >>>>
> >>>>> On 5/12/2022 8:54 PM, Ben wrote:
> >>>>>> olcott <NoOne@NoWhere.com> writes:
> >>>>>>
> >>>>>>> On 5/12/2022 7:10 PM, Ben wrote:
> >>>>>>>> olcott <NoOne@NoWhere.com> writes:
> >>>>>>>>
> >>>>>>>>> Its done see my new post.
> >>>>>>>> Apart from the bug/typo it's a perfectly good way to
> >>>>>>>> implement a TM tape. It's not a deque though.
> >>>>>>>
> >>>>>>> I think that it is a better way to implement a std::deque.
> >>>>>> Better than what?
> >>>>>
> >>>>> The complex mess of the conventional way to implement std::deque
> >>>>>
> >>>>>> There are lots of ways to implement a deque and they
> >>>>>> all have advantages and disadvantages.
> >>>>>
> >>>>> If you get maximum
> >>>>> (a) simplicity (b) speed and (c) minimum space what more could
> >>>>> you want?
> >>>>
> >>>> Correctness.
> >>>>
> >>>>>> Of course, since you have not
> >>>>>> implemented any of the deque interface, I can't tell what
> >>>>>> method might be thinking of using. Other than it will
> >>>>>> probably use two vectors.
> >>>>>
> >>>>> public:
> >>>>> tape_element& front( ) { return Left.back(); }
> >>>>> tape_element& back() { return Right.back(); }
> >>>>> void pop_front() { Left.pop_back(); }
> >>>>> void pop_back() { Right.pop_back(); }
> >>>>> void push_front(tape_element& E) { Left.push_back(E); }
> >>>>> void push_back(tape_element& E) { Right.push_back(E); }
> >>>>> void reserve(unsigned int N)
> >>>>> { Left.reserve(N); Right.reserve(N); }
> >>>>
> >>>> This is not correct. Please read a book. Or at least write a
> >>>> test program and compare with std::deque.
> >>>
> >>> Even if we ignore complexity requirements and element reference
> >>> stability it is still wrong: what happens if `Left` is empty,
> >>> `Right` is non-empty and `pop_front` is called? It simply does not
> >>> conform to the std::deque interface.
> >>>
> >>> /Flibble
> >>>
> >>
> >> Oh, now I see what Ben was saying.
> >> Simply extend my definition of pop_front() to account for this.
> >
> > I will be interested to see how you account for this without
> > introducing linear, O(n), complexity for that operation.
> >
> > /Flibble
> >
>
> It requires linear, O(n), complexity for that operation.
> Tape_Type never needs to do that.
So your class isn't a better version of std::deque then because
std::deque::pop_front() is constant time not linear. Feel free to
apologize for your mistake.

/Flibble

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

<44CdnU8P0pZjDeP_nZ2dnUU7_81g4p2d@giganews.com>

 copy mid

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

 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: Fri, 13 May 2022 12:10:22 -0500
Date: Fri, 13 May 2022 12:10: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> <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>
<X9mdnVTySoUr5eD_nZ2dnUU7_8zNnZ2d@giganews.com> <874k1u2vc7.fsf@bsb.me.uk>
<2e-dnTfLY8FJC-D_nZ2dnUU7_8xh4p2d@giganews.com> <87pmki1edk.fsf@bsb.me.uk>
<MeOdncVeZaeHMOD_nZ2dnUU7_8xh4p2d@giganews.com> <87wneqyz6w.fsf@bsb.me.uk>
<IsSdnaQ2qJzQWOD_nZ2dnUU7_83NnZ2d@giganews.com> <87y1z5zoqu.fsf@bsb.me.uk>
<zdmdnVjtirshHeP_nZ2dnUU7_8xh4p2d@giganews.com> <87zgjlxusg.fsf@bsb.me.uk>
From: NoO...@NoWhere.com (olcott)
In-Reply-To: <87zgjlxusg.fsf@bsb.me.uk>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <44CdnU8P0pZjDeP_nZ2dnUU7_81g4p2d@giganews.com>
Lines: 78
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-vz4PhZ6iBmTUErs/8OUTzpajLXAZCir2Ha7lm1LewkpPRyf3dfoaD68qOr5Kg85XubxvaK5BFxfoe7o!OWwb/UUncPDrbNG4rHGtCURSpsccGC8OJA1Qv0yjojyIo0AXilut0Gm5C8Z6HKEOn9dZ9MuvW4M=
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: 4853
 by: olcott - Fri, 13 May 2022 17:10 UTC

On 5/13/2022 11:27 AM, Ben wrote:
> olcott <NoOne@NoWhere.com> writes:
>
>> On 5/13/2022 5:54 AM, Ben wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 5/12/2022 8:54 PM, Ben wrote:
>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> On 5/12/2022 7:10 PM, Ben wrote:
>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>
>>>>>>>> Its done see my new post.
>>>>>>> Apart from the bug/typo it's a perfectly good way to implement a TM
>>>>>>> tape. It's not a deque though.
>>>>>>
>>>>>> I think that it is a better way to implement a std::deque.
>>>>> Better than what?
>>>>
>>>> The complex mess of the conventional way to implement std::deque
>>>>
>>>>> There are lots of ways to implement a deque and they
>>>>> all have advantages and disadvantages.
>>>>
>>>> If you get maximum
>>>> (a) simplicity (b) speed and (c) minimum space what more could you
>>>> want?
>>> Correctness.
>>>
>>>>> Of course, since you have not
>>>>> implemented any of the deque interface, I can't tell what method might
>>>>> be thinking of using. Other than it will probably use two vectors.
>>>>>
>>>>
>>>> public:
>>>> tape_element& front( ) { return Left.back(); }
>>>> tape_element& back() { return Right.back(); }
>>>> void pop_front() { Left.pop_back(); }
>>>> void pop_back() { Right.pop_back(); }
>>>> void push_front(tape_element& E) { Left.push_back(E); }
>>>> void push_back(tape_element& E) { Right.push_back(E); }
>>>> void reserve(unsigned int N)
>>>> { Left.reserve(N); Right.reserve(N); }
>>> This is not correct. Please read a book. Or at least write a test
>>> program and compare with std::deque.
>>>
>>
>> It is correct within this design:
>>
>> // Tape_Type implements a two-way Turing machine tape.
>> // Right contains Tape_Head >= 0 values (right expansion)
>> // Left contains Tape_Head < 0 values (left expansion)
>> //
>> // Grows with Right.push_back() as Tape_Head increases above 0.
>> // Grows with Left.push_back() as Tape_Head decreases below 0.
>> //
>> // Tape_Type has functionality very similar to std::deque
>> // yet implements this functionality much more simply.
>> // This saves time and space.
>
> For goodness sake, find out what a deque is and then test our code. Do
> you post in the hope that someone will point out all the bugs and the
> tell you how to fit it?
>

The std::deque stuff was a side issue.

The key issue is how it performs as Tape_Type compared to your
std::string method.

Tape_Type::reserve() may make mine much faster for you test code.

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