TM - reject definition and complement

Question

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!

Answer 1

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

Answer 2

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).

Answer 3

(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.