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