On 5/14/2022 1:38 PM, Malcolm McLean wrote:
> On Saturday, 14 May 2022 at 14:52:01 UTC+1, olcott wrote:
>> On 5/14/2022 5:30 AM, Malcolm McLean wrote:
>>> On Saturday, 14 May 2022 at 10:13:40 UTC+1, olcott wrote:
>>>> On 5/14/2022 3:54 AM, Malcolm McLean wrote:
>>>>> On Saturday, 14 May 2022 at 01:09:20 UTC+1, olcott wrote:
>>>>>> On 5/13/2022 7:00 PM, Ben wrote:
>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>
>>>>>>>> On 5/13/2022 5:57 PM, Ben wrote:
>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>
>>>>>>>>>> On 5/13/2022 3:58 PM, Ben wrote:
>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>
>>>>>>>>>>>> On 5/13/2022 2:12 PM, Ben wrote:
>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>
>>>>>>>>>>>>>> On 5/13/2022 1:45 PM, Ben wrote:
>>>>>>>>>>>>>>> olcott <No...@NoWhere.com> writes:
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>> 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.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> As did everyone who glanced at the code for more than a few seconds. Or
>>>>>>>>>>>>>>> at least I sincerely hope they did. It's not hard to see that your code
>>>>>>>>>>>>>>> was wrong.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> The details of std::deque is almost brand new to me.
>>>>>>>>>>>>>
>>>>>>>>>>>>> I guessed as much. Yet you claimed to have done better than the teams
>>>>>>>>>>>>> of experienced programmers who've worked on various C++ standard
>>>>>>>>>>>>> libraries after writing only a few lines of code? That level of
>>>>>>>>>>>>> delusion might lead someone to think they can solve the halting problem.
>>>>>>>>>>>>
>>>>>>>>>>>> None-the-less my version does perform better and is much simpler on
>>>>>>>>>>>> the operations that I need.
>>>>>>>>>>> What new delusion is this? Your "version" is not a deque. What is it a
>>>>>>>>>>> version of? What does it perform better than?
>>>>>>>>>>>
>>>>>>>>>>>>>> None-the-less my Tape_Type does seem optimal for a TM tape as long as
>>>>>>>>>>>>>> the speed with Tape_Type::reserve() beats some and matches the rest of
>>>>>>>>>>>>>> the speed of every operation of your std::string, otherwise I would go
>>>>>>>>>>>>>> for the simpler std::string version.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Using reserve has no effect on the one test case I have for timing.
>>>>>>>>>>>>
>>>>>>>>>>>> What is the speed difference?
>>>>>>>>>>>
>>>>>>>>>>> Not reliably measurable. I could do more robust tests but that's not
>>>>>>>>>>> what I want to do today.
>>>>>>>>>>
>>>>>>>>>> This always works well for me.
>>>>>>>>>> https://www.tutorialspoint.com/c_standard_library/c_function_clock.htm
>>>>>>>>> It's not a method I like. When yours program is working, you can
>>>>>>>>> do timings any way you like. (And since the code is C++ you might want
>>>>>>>>> to look at std::chrono::high_resolution_clock.)
>>>>>>>>>
>>>>>>>>>> I want to know if your version is better than mine.
>>>>>>>>>> When I am all done I want to have the best version.
>>>>>>>>> Well, it's better because it's finished. It may be worse in other ways,
>>>>>>>>> but you don't say what "best" means to you.
>>>>>>>>
>>>>>>>> Mine is certainly designed to scale so on this basis I will keep mine.
>>>>>>>
>>>>>>> You don't have a TM interpreter yet! So presumably you mean you'll keep
>>>>>>> your design even though you don't know if mine scales. You have always
>>>>>>> stated strong opinions based on little knowledge.
>>>>>>>
>>>>>> Because of the simplicity that you claimed it probably could not quite
>>>>>> have the scalability that mine has.
>>>>>>
>>>>> You're using C++, so you need a class with the function to read the tape
>>>>> at the current head position, a function to write a symbol to the tape at
>>>>> the current head position, a function to move the head one place left,
>>>>> and a function to move the head one place right.
>>>>>
>>>>> Also you are going to need a function to read a "window" round the tape
>>>>> head, for visualisation purposes. That will be the hardest part, because the
>>>>> "window" can extend beyond the tape's physical bounds.
>>>>>
>>>>> You might also need copy and "move" constructors, and maybe a constructor
>>>>> to create a tape with initial contents (you could do this on top of the move
>>>>> and write functions). You'll need a default constructor to create an
>>>>> initially blank tape. Depending on your model, you might also have to write
>>>>> an explicit destructor.
>>>>>
>>>>> Good software engineering practice is to write the interface first, then write
>>>>> a simple implementation that doesn't have to be efficient or to scale up
>>>>> to long tapes. You then write a more efficient implementation later, if it is
>>>>> required.
>>>>>
>>>>> For an even odd decider, you won't need a very efficient tape at all. A human
>>>>> can count values up to maybe 20 in unary notation, reliably. So you can really
>>>>> only test for tapes with less than 20 symbols on them. That's tiny, even for a
>>>>> ZX81.
>>>> typedef unsigned char tape_element;
>>>> // 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.
>>>> //
>>>> class Tape_Type
>>>> {
>>>>
>>>> private:
>>>> int Tape_Head = 0; // Can be negative
>>>> std::vector<tape_element> Left; // Stores left expansion
>>>> std::vector<tape_element> Right; // Stores right expansion
>>>>
>>>> tape_element& operator[](int index)
>>>> {
>>>> return index >= 0 ? Right[index] : Left[-index - 1];
>>>> }
>>>>
>>>> public:
>>>> tape_element& front( ) { return Left.back(); }
>>>> tape_element& back() { return Right.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); }
>>>>
>>> All above this should be "private". The tape only has move one space left / right
>>> (either one function or two, it doesn't matter), Read() and Write() as public
>>> members. That's for the strict Turing machine.
>>> You'll also want an output function for visualisation, testing, and debugging,
>>> which you've written.
>>>> void Write(tape_element Y){ (*this)[Tape_Head] = Y; };
>>>> tape_element Read() { return (*this)[Tape_Head]; };
>>>>
>>>> void move_head(char E)
>>>> {
>>>> if (E == 'L')
>>>> move_left();
>>>> else
>>>> move_right();
>>>> }
>>>>
>>>> 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('_');
>>>> }
>>>>
>>>> void Output()
>>>> {
>>>> printf("Tape_Type::Output()\n");
>>>> if (Left.size())
>>>> {
>>>> int Last_One = Left.size() - 1;
>>>> for (int N = Last_One; N >= 0; N--)
>>>> {
>>>> int TH = (N + 1) * -1; // determine Tape_Head from N
>>>> printf("[%04d]:%c Left[%02d]\n", TH, Left[N], N);
>>>> }
>>>> }
>>>> if (Right.size())
>>>> for (int N = 0; N < Right.size(); N++)
>>>> printf("[%04d]:%c Right[%02d]\n", N, Right[N], N);
>>>> }
>>>> };
>>>>
>>> A model with two vectors which grow form the initial zero position in opposite
>>> directions is fine. The current tape position is the Tape_Head.variable, which is
>>> a signed integer giving offset form the initial zero position. Again, that's fine.
>>>
>>> I'll think you'll find you need a less wordy "Output()" function, however.
>>> One advantage of Turing machines is that the symbols on the tape can be
>>> made human-readable. It's easy to scan a string of ascii characters which
>>> represents the current tape.
>>>
>>> Write some tests and see if this tape works.
>> It works.
>>
> Excellent.
> Now we need to construct the rest of the machine.

Most of the machine was the tape actions, now we are back to the state
transitions.

--
Copyright 2022 Pete Olcott

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