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?