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

[olcott]

On 5/10/2022 9:05 PM, Mike Terry wrote:
> On 11/05/2022 02:12, olcott wrote:
>> On 5/10/2022 7:42 PM, Ben wrote:
>>> olcott <No...@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.
>>
>> 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.
>>
>
> I think you've misunderstood DK's and Ben's approaches.  I think what
> you're suggesting is that Left handles all the "negative" tape head
> positions, and Right all the "positive" ones, while Tape_Head contains
> the tape head index (positive or negative) which changes by 1 each time
> the head moves?
>

Not in the least little bit. Please wait until you see my full
implementation before passing judgement. David's solution is optimal.

> DK and Ben propose two stacks, and with this approach the tape head is
> effectively always in a fixed place "in between the two stacks", or
> (with Ben's) at the top of [say] the left stack.  So there is no
> Tape_Head index to track.
>
> But what you suggest is quite workable...
>
> I think if I were interested in ultimate efficiency, I might go with
> Jeff's "chained blocks" with a comfortably large chosen page size.  (But
> efficiency really isn't an issue for this task!)
>
>
> Mike.
>

My implementation of David's solution essentially redefines the whole
notion of std::deque with std:vector's (memory and speed) efficiency and
none of std::deque's limitations: (such as invalidating iterators).


--
Copyright 2022 Pete Olcott

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