On 5/6/2022 8:57 PM, Ben wrote:
> olcott <polcott2@gmail.com> writes:
>
>> On 5/6/2022 6:36 AM, Ben wrote:
>>> olcott <polcott2@gmail.com> writes:
>>>
>>>> On 5/5/2022 9:35 PM, Ben wrote:
>>>>> olcott <polcott2@gmail.com> writes:
>
>>>>>> struct Quintuple
>>>>>> {
>>>>>> u32 state;
>>>>>> u32 symbol;
>>>>>> u32 write_symbol;
>>>>>> u32 next_state;
>>>>>> u8 Tape_Head_Move;
>>>>>> }
>>>>>>
>>>>>> std::set<Quintuple> States;
>>>>> Why is a set of objects that are not states called "States"?
>>>>
>>>> They are states, what did you think that states are?
>
>>> Not quintuples. There are lots of ways to represent a TM's states, but
>>> states are not quintuples and quintuples are not states. This confusion
>>> will (as you can see below) make lots of the code read badly.
>>
>> What did you think that states are?
>
> Their only properties are that they are distinct and finite in number.

Ah so you are only seeing the mathematical abstraction that uses
directed graphs. That is not enough for an actual hardware machine to go
on.

> I have written an interpreter in which the states are instances of a
> class State, that holds all the information a TM might need when in that
> state. But there are a hundreds of other ways to represent the states.
>

In other words this:
struct Quintuple
{ int state;
int symbol;
int write_symbol;
int next_state;
char tape_head_move;
};

>> Do you think that they are raw integers?
>
> No, that's not what they are, though you could use integers to represent
> them. You could also use characters, strings and pointers to state
> objects.
>
> A key consideration, though, is that you might want to print information
> about the states to help the user of the interpreter so the states
> should be identifiable in some what that matches the way the user writes
> the TM. So I tend to favour labelling the sates with strings so that
> messages can report things like:
>

I am going to make it compatible with the TM interpreter files and I
will always output the full execution trace. I am aiming for a three
minute learning curve for everyone that knows TM's very well.

> In state 'open_(_seen': no transition for symbol '+'.
>
> If you are matching the input scheme for the implementation you posted a
> link to, then you should be able to report the state's name as the
> character the user will have entered.
>

full execution trace.

>>>> This is the first draft of my transition_function() its seems to exactly match this design on the first page of the docs.
>>>> http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt
>>>>
>>>> I am writing this in Open Office Writer not any compiler.
>>>> I don't even know that it compiles.
>>>>
>>>> This is going to be a member function.
>>>> bool transition_function(std::set<Quintuple>::iterator& current_state)
>>>
>>> There's no point in putting the quintuples into a std::set. And the
>>> parameter current_state is badly worded as it refers to a particular
>>> rule (quintuple) and not to a state.
>>
>> It is simpler than a linear or binary search scan through the whole
>> list every-time we need to make a transition from the current_state to
>> the (next_state + current_Input).
>
> Of course, but a set is not, in my opinion, the natural container for
> quintuples. Do you even know how to make it work in your case? It
> would involve what I would consider a bit of trickery.
>
>> std::set<Quintuple>::iterator
>> NextState(int next_state, int current_input)
>> {
>> Quintuple QT(next_state, current_input);
>> return States.find(QT);
>> };
>>
>> The above returns an iterator to state indexed by (state + symbol).
>
> It returns an iterator to a quintuple, not a state, so the name is bad.
> And why does the function take things called 'next_state' and
> 'current_input'? The next quintuple is determined by the current state
> and the current input.

It is specified by the TM interpreter specs.

For example, the quintuple 'SCcsm' is executed by the machine:

If it is in state 'S' and is reading the symbol 'C' on the tape then
(a) make a transition to state 's'.

(b) overwrite the symbol 'C' on the tape with the symbol 'c'.
// Must do this before transition to state 's' or we lose 'c' from S.

(c) move the tape reading head one symbol to the left or right
according to whether 'm' is 'l' or 'r'.
http://www.lns.mit.edu/~dsw/turing/doc/tm_manual.txt

>> bool Transition_to_State_0(std::set<Quintuple>::iterator& current_state)
>> {
>> it = NextState(0, Tape[Tape_Head]);
>> if (it == States.end())
>> return false;
>> current_state = it;
>> return true;
>> }
>
> This looks all messed up but mainly because I don't think you are using
> the right names.
>
> And it's still a very loose sketch. Setting current_state is
> essentially pointless.
>

It performs ALL of the steps of transitioning to the start state.

>>>> {
>>>> u32 next_state = current_state->next_state;
>>> States, as you make clear here are just unsigned integers (in your
>>> implementation).
>>>
>>
>> OK then I will use Quintuple_List as my designer implemented.
>>
>>>> u32 current_input = Tape[Tape_Head];
>>> Why reference the tape here? If Tape[Tape_Head] != current_state.symbol
>>> then something has gone very wrong already. Note how confusing my
>>> writing the condition is since current_state.symbol should not make
>>> sense.
>>
>> Although after successful find current_state->symbol would have the
>> same value as Tape[Tape_Head] it is more clear that we are referring
>> to the current input with the latter.
>>
>>> (By all means reference the tape to put in a run-time assertion that
>>> tape.head() == current_rule.symbol or some such but there's no need to
>>> get the symbol from the tape as you will already have done this in order
>>> to pass the right quintuple to this function.)
>>
>> My way is clearer.
>
> I think the best way to judge that will be to compare code. At the
> moment you only have a very rough sketch.

The "rough sketch" is fully operational code.
I am adding parse capability.

>>>> std::set<Quintuple>::iterator it;
>>>>
>>>> Tape[Tape_Head] = current_state->write_symbol;
>>> current_state.write_symbol
>>> But if the parameter were correctly named it would make more sense:
>>> Tape[Tape_Head] = current_rule.write_symbol
>>>
>>>> if (toupper(current_state->tape_head_move) == “L”;
>>>> Tape_Head--; // Left
>>>> else
>>>> Tape_Head++; // Right
>>> Since the tape has a very limited number of operations, I'd abstract it
>>> out into a class with a move member function (or a left and a right
>>> function).
>>
>> I think that it is more clear the way it is.
>
> Let's see how it turns out in the end.
>
>> Since the current state must refer to every element of its related
>> Quintuple and current_state is actually current_state + current_input,
>> this a single integer does not uniquely identify a Quintuple it seems
>> to make the most sense to call each Quintuple a state.
>>
>> It may be more conventional to have a two layered system where an
>> integer indexes into a list of states each one having a list of inputs
>> that they respond to. The ads extraneous complexity.
>>
>> I could call current_state current_quintuple.
>
> I think a lot of the problems a down to your uses state when you mean
> quintuple. NextState seems all wrong, but maybe it makes more sense if
> it does not find the next state but the next quintuple.
>

NextState does this:
(a) make a transition to state 's'.

>> bool transition_function(std::set<Quintuple>::iterator& current_state)
>> {
>> u32 next_state = current_state->next_state;
>> u32 current_input = Tape[Tape_Head];
>> std::set<Quintuple>::iterator it;
>>
>> Tape[Tape_Head] = current_state->write_symbol;
>> if (toupper(current_state->tape_head_move) == “L”;
>> Tape_Head--; // Left
>> else
>> Tape_Head++; // Right
>>
>> it = NextState(next_state, current_input);
>> if (it == States.end())
>> return false;
>> current_state = it;
>> return true;
>> }
>
> With proper renaming this sketch makes a bit more sense. You take a
> current rule (I am getting tired typing quintuple) and NextState really
> finds the next rule, not state.
>

I will work out best naming later on after the code works.

> But the details are still all wrong. NextRule (as I'd call it) needs to
> use next_state and the new current_input, not the input you find at the
> top of the function. And setting current_state (which should be called
> current_rule) is pointless since it's about to be thrown away.
>

That is the part that is ambiguous in the spec.

Do you know a source that confirms that next_state is a function of
current_state and next_input?

>> You didn't point out any actual errors, you simply critiqued my design
>> aesthetics.
>
> You take my remarks how you like. When you show this code to a
> compiler, you'll see more problems.
>

It already compiles.

--
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer