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.

--
Copyright 2022 Pete Olcott

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