0
$\begingroup$

Lets say there is a turing machine $M$ where
\begin{align*} M &= (Q, \Sigma, \Gamma, \delta, q_1, q_{accept}, q_{reject}) \\ Q &= \{q_1, q_2, q_3, q_{accept}, q_{reject} \} \\ Σ &= \{0, 1\} \\ Γ &= \{0, 1, U\} \end{align*}

with transition functions \begin{align*} \delta (q_1, U) &= (q_1, U, R)\\ \delta (q_1, 0) &= (q_1, 0, R)\\ \delta (q_1, 1) &= (q_2, 1, R)\\ \delta (q_2, U) &= (q_{accept}, U, R)\\ \delta (q_2, 0) &= (q_3, 0, R)\\ \delta (q_2, 1) &= (q_2, 1, R)\\ \delta (q_3, U) &= (q_3, U, R)\\ \delta (q_3, 0) &= (q_3, 0, R)\\ \delta (q_3, 1) &= (q_3, 1, R) \end{align*}

If I input a string and it reaches the $q_{accept}$ state while there are still letters remaining in the string, would it count as accepting the string, rejecting the string, something else?

$\endgroup$
  • $\begingroup$ Depends on the exact definition of what a TM is resp. when it accepts. Which one are you using? $\endgroup$ – Raphael May 12 '16 at 5:43
  • $\begingroup$ Sorry im not exactly sure what "resp" means but im assuming you are asking whether it is a decider or a recogniser etc. in this question it is a tm recogniser $\endgroup$ – zeek May 12 '16 at 6:03
  • $\begingroup$ And what is the exact definition of "recognizer" you are using? $\endgroup$ – Raphael May 12 '16 at 6:18
  • $\begingroup$ M is able to recognise the inputed string? so it needs to halt when it is accepted or rejected and dont halt at all other wise $\endgroup$ – zeek May 12 '16 at 6:33
  • 1
    $\begingroup$ Was does "accept" mean? Enter a final state? What is the output? The tape may factor into either of the answers so the formal definition is important here! $\endgroup$ – Raphael May 12 '16 at 7:35
1
$\begingroup$

As per the general definition Turing machine halts when it enters the reject or accept state.At this point there can be an arbitrary string present on the tape of the Turing machine. This is how you expect the Turing machine to compute a function of the type say $\{0,1\}^m \to \{0,1\}^n$.

$\endgroup$
  • 2
    $\begingroup$ That is one possible definition, yes. There are others. $\endgroup$ – Raphael May 12 '16 at 7:35
3
$\begingroup$

In the nominal TM definition, the machine is a 7-tuple, $M=(Q,\Sigma,\Gamma,b,\delta,q_0,F)$, where $F$ denotes a set of final states. Wheneven the TM transitions to a state in $F$ it immediately halts, no matter what it did or didn't do beforehand.

From the way you wrote your TM, I believe you meant that your final states are $F=\{q_{accept},q_{reject}\}$, thus once one of them is reached, the TM halts.


Once the above is clear, there is the question of "what happens if the input string isn't fully consumed". Well, this question is a bit misleading, since it implies that the TM consumes the input string symbol-by-symbol (like a DFA or PDA), which is not the case for the nominal TM.

In a Turing machine, the input string appears on the tape at the start of the computation. It is fully there, and needs not be "consumed". Besides of the input string, the tape is empty, i.e., it contains the blank $b$ symbol (where $b\in \Gamma \setminus \Sigma$, so the input cannot contain blanks). Since the input is already there on the tape, there is no question of "consuming" it. The alternative question is reading the input - it is perfectly fine if the TM moves to a final state ($q\in F$) before "reading" the entire input, i.e, when the head of the TM never visits all the tape slots in which the input resides. Again, this is perfectly allowed.

A Note: Sometimes the input is given on a separate tape (which is usually, a read-only tape). This helps to count the memory actually used for processing the computation without counting the space used to hold the input. Such machines are especially relevant for computations that take sub-linear space. Yet again, the machine is allowed to terminate without reading the entire input.

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