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?

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:

• Start by scanning right until you hit the first blank cell.

• Go left once (you are now at the rightmost non-blank cell).

• Run your original machine.

StackExchange Computer Science Q#89885, answer score: 3