Is it allowed to transit between two states $q$, $q'$ by more than one condition? Thank you in advance.

e.g. coming from state $q$, the conditions $(0,0,L)$ and $(1,0,L)$ would lead to the same state $q'$. Is this formally allowed?


Yes, it's allowed.

I guess the underlying problem here is that you're not familiar with reading mathematical definitions. Properly written definitions state exactly the criteria that apply. So, for example, if you read the definition "An integer is even if it is divisible by two" you should assume that divisibility by two is the only criterion that applies. The definition says nothing about divisibility by three, for example, so divisibility by three doesn't matter.

In our case, the transition function of a Turing machine is defined as a function whose arguments are a state and a tape character, and whose outputs are a state, a tape character and a direction to move the head. No further restrictions (such as "you can't get the same output from two different inputs") are mentioned in the definition, so no further restrictions apply.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.