# How do we define if a Turing machine goes to the right or left?

In my college course notes, we are given two examples.

Example 9.1.1: $$M(K, \Sigma, \delta, s)$$ where

• $K = \{q_0, q_1\}$
• $\Sigma = \{a, \# \}$
• $s = q_0$
• $\delta = \begin{array}{|c|c|c|c|} \hline q & \sigma & \delta(q, \sigma) \\ \hline q_0 & a & (q_1, \#) \\ q_0 & \# & (h, \#) \\ q_1 & a & (q_0, a) \\ q_1 & \# & (q_0, R) \\ \hline \end{array}$

Note that state $(q_1, a)$ cannot happen if the start state is $q_0$. This is included only for completeness (to make $\delta$ a total function).

This machine will scan right, changing any $a$ that sees to a $\#$. When it first hits a $\#$, it will halt.

Example 9.1.2: $$M(K, \Sigma, \delta, s)$$ where

• $K = \{q_0\}$
• $\Sigma = \{a, \# \}$
• $s = q_0$
• $\delta = \begin{array}{|c|c|c|c|} \hline q & \sigma & \delta(q, \sigma) \\ \hline q_0 & a & (q_0, L) \\ q_0 & \# & (h, \#) \\ \hline \end{array}$

This machine will scan left until it encounters $\#$, then halt.

One TM goes to the right while the other goes to the left. Obviously this is determined by the transition rules, but how do we explicitly know/define where to start (either on the left of the string or right?).

I am asking because I have a Turing machine that works for a problem I have, but I must start from the right of the string and scan left... How do I define this?

It's not specified in the description you gave, but absent directions to the contrary, a TM is generally understood to start at the leftmost non-blank cell.

• Thanks. However, in the second example. it scans left, so therefore it must start on the rightmost non-blank cell. How do we define this if we make our Turing machine like this? – Jon Mar 27 '18 at 23:53
• @Jon. Just make it explicit: "If we begin at the rightmost non-blank cell, the following description will give a TM that ...". – Rick Decker Mar 28 '18 at 13:11

so therefore it must start on the rightmost non-blank cell

That doesn't follow. It can start on any cell, including the left-most one, in which case it'll just go left once and stop.

I am asking because I have a Turing machine that works for a problem I have, but I must start from the right of the string and scan left... How do I define this?

If you have such a machine, that you can easily create one which does the same starting on any non-blank cell. Namely:

1. Start by scanning right until you hit the first blank cell.
2. Go left once (you are now at the rightmost non-blank cell).