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

Question

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?

Answer 1

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.

Answer 2

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).
3. Run your original machine.