# Thread: Turing machine notation for not on multiple symbols

1. ## Turing machine notation for not on multiple symbols

I am trying to draw a Turing Machine diagram where I have a state and I go to one state if the current symbol pointed to by the head is an a or b, so I have (a, b) on that edge. I need another transition for when it's not a AND not b to go to another state. I don't want to label the edge as (!a, !b) as I think this makes my machine non-deterministic since technically a would be !b and could follow this transition, same with b and !a. I am not able to find common notation for something like this. All the examples I find show a single symbol transition of something like a and then !a, but not multiple symbols like my case. Thanks for any advice.

2. ## Re: Turing machine notation for not on multiple symbols

There is no general accepted format for turing machine state notation, so you will need to consult your book or notes for the course (if this is for a course).

One typical method is to denote the transition from one state to another with an arrow labeled by one or more conditions which cause that state transition: 0/1,R would mean it only transitions on zero, and when it does, it changes 0 to 1 and moves right on the tape. I would list them separately on the arrow or draw two arrows, as a/X,Y and b/X,Y, where X,Y are the new symbol and motion of the scanner.

If you need to limit space and your instructor doesn't care about formatting, I guess you could do it like this:

Arrow 1 label: $\displaystyle (A$ $\displaystyle \vee$ $\displaystyle B)/X,Y$
Arrow 2 label: $\displaystyle \neg$$\displaystyle (A \displaystyle \vee \displaystyle B)/X,Y Alternative arrow 2 label: \displaystyle ($$\displaystyle \neg$$\displaystyle A \displaystyle \wedge \displaystyle \neg$$\displaystyle B)/X,Y$

These are mutually exclusive so it is still deterministic. (Though non-determinism is not your only problem; you define the wrong machine the way you describe.)

EDIT: Note that if you're not changing the symbol on the tape to the same thing each time you pass it, you'll want to write those transitions separately or come up with a way to express "no change" as a symbol, maybe using a dash, or something else not in (alphabet $\displaystyle \cup$ blank).

3. ## Re: Turing machine notation for not on multiple symbols

I agree that there are no standard notations for Turing Machines. I would denote a transition corresponding to not $\displaystyle a$ and not $\displaystyle b$ as $\displaystyle \overline{\{a,b\}}$ or just $\displaystyle \overline{a,b}$. You could also use proper set-theoretic notations like $\displaystyle \Sigma-\{a,b\}$. But in any case I would add a note explaining the notation.