3
$\begingroup$

I have couple of questions about Turing machines:

  1. What is the definition of the "reject" state in TM? If the input was very small and, after one step, the machine gets to the end of the input, but it stands on regular state, it counts as "reject"? Or there is a special "reject" state, and if it won't get to this/those states, it doesn't count as a reject? (I know that in DFA, the reject states are just all the states that aren't "accept".)
  2. I know that in aDFA, if we swap the reject and the accept states, we get the complement language. Does this work on TMs?
  3. If I use only the TM's input cell (including changing their content), does it means I used $\mathrm{SPACE}(1)$ or $\mathrm{SPACE}(n)$?

Thanks a lot!

$\endgroup$
4
$\begingroup$
  1. There's a special reject state. Unlike a DFA, which is terminated by the definition when it reaches the end of the input, the machine decides when it stops, by jumping to one of the halting states (depending on exactly what definition you're using, there might be just one "halt" state, or there might be separate "accept" and "reject" states).

  2. Almost. If the Turing machine accepts or rejects every input, then swapping accept and reject does indeed compute the complement, since you reject every string that you would have accepted, and vice-versa. However, we can also define languages in a weaker way, where the Turing machine accepts all strings in the language but, for a string not in the language, it might reject or it might just get stuck in an infinite loop (this is called "accepting", "recognizing" or "semi-deciding" a language). In this case, just swapping the accept and reject states doesn't complement the language, since the inputs that loop forever don't reach either state, so you'd conclude that such a string is neither in the language nor it's complement, which can't possibly be right.

  3. No. Normally, when defining space classes, we use a slightly different model. When considering space-bounded computations, we Turing machines with three tapes: a read-only input tape, a write-only output tape and a read/write working tape. In this model, we only count the space used on the working tape. Because the input tape is read-only, you're not allowed to write to its input, unless you first copy the input to the working tape, in which case you're using space $n$.

$\endgroup$
  • $\begingroup$ 1 - So what happen if the machine reads an empty cell? Does it means that it will automatically move to reject or it will stay with the "undefined" (neither accept/reject) state? $\endgroup$ – Dvir Jan 19 '17 at 16:35
  • $\begingroup$ "empty" cells contain the special "blank" character. The Turing machine reads that just as it reads any other character, and does whatever the transition function tells it to do. $\endgroup$ – David Richerby Jan 19 '17 at 16:37
  • $\begingroup$ So actually you say that by definition - turing machine have to take care of all of the cases, in any state - so It's not possible to read a "blank" and not knowing what to do? => If turing machine halts, and there is an accept and reject states - it must be on one of them...? $\endgroup$ – Dvir Jan 19 '17 at 16:51
  • $\begingroup$ @Dvir That's what I'm saying. The transition function is a total function: it defines what the machine does for every combination of the state it's in and the character (including blank) that it finds under the head. $\endgroup$ – David Richerby Jan 19 '17 at 16:59
3
$\begingroup$
  1. There is a special reject state, and since the transition function is total, if after one step the machine finds an empty cell, and there are no moves for the current state reading an empty cell, the machine goes to the reject state (you don't have to explicitly write that in the transition function, it's implied).
  2. If the TM M decides the language L - which means that the union between the accepted and the rejected words covers all the strings on the alphabet - you can swap the states and obtain a TM M' that decides not-L. If M only recognizes L - some input exists on which M doesn't stop - you can't swap.
  3. It means you used SPACE(n). In fact the space complexity of a TM M on an input of length x is always >= x. However there is an alternative definition of space complexity for TMs which counts only the "work tape" ignoring the "input tape". This version allows to define a class of problems which use sublinear space (see L and NL).
$\endgroup$
  • $\begingroup$ As far as I'm aware, your "alternative" definition in part 3 is the only one that's actually used. Sublinear space classes such as L and NL are very important and a model of space complexity that didn't include them doesn't seem to have much use. $\endgroup$ – David Richerby Jan 19 '17 at 15:52
3
$\begingroup$

(1) depends on how you define the machine. The most natural way is to augment the set of the machine's states with two special states to indicate that the machine halts accepting or rejecting, respectively. You may as well use a single halting state (or no halting state at all, having the machine halt the first time the transition function is undefined) and read the output from a tape. All those definitions are equivalent.

(2) yes, given a Turing machine $T$, you can certainly build another machine $T'$ that accepts whenever $T$ rejects and vice-versa. However, bear in mind that a generic machine could not halt on some inputs.

(3) in complexity theory, a different model, the $k-$IO T.M. is generally used. In such a machine, you have $k$ tapes, where the first and the $k$-th are reserved for input and are read-only, meaning that you can never move backwards on those tapes. Only tapes $2$ through $k-1$ count towards the space complexity. Therefore, you are simply not allowed to write over the 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.