3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jon Mar 27 '18 at 23:53
  • $\begingroup$ @Jon. Just make it explicit: "If we begin at the rightmost non-blank cell, the following description will give a TM that ...". $\endgroup$ – Rick Decker Mar 28 '18 at 13:11
3
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.