patternMinor
TM - reject definition and complement
Viewed 0 times
definitionrejectcomplementand
Problem
I have couple of questions about Turing machines:
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".)
Thanks a lot!
- 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".)
- I know that in aDFA, if we swap the reject and the accept states, we get the complement language. Does this work on TMs?
- 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!
Solution
-
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).
-
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.
-
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$.
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).
-
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.
-
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$.
Context
StackExchange Computer Science Q#68983, answer score: 4
Revisions (0)
No revisions yet.