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

The specified Tape_Head increments/decrements for move_right/move_left.
The tricky part of this is mapping this to integer subscripts of
Left/Right when both Left/Right can dynamically grow in size.

> (I.e. exactly like I suggested in my earlier post, when
> you replied "not in the least little bit"?)    THAT IS NOT DK/BEN'S TWO
> STACK DESIGN.
>
> Mike.

--
Copyright 2022 Pete Olcott

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