I am looking at an example Turing machine in my textbook, Automata and Computability by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. Here is the example:
"Here is a TM that accepts the non-context free set $\{a^nb^nc^n \mid > n\geq 0\}$. Informally, the machine starts in its start state s, then scans to the right over the input string, checking that it is of the form $a^* b^* c^*$. It doesn't write anything on the way across (formally, it writes the same symbol it reads). When it sees the first blank symbol _, it overwrites it with a right endmarker ]. Now it scans left, erasing the first c it sees, then the first b it sees, then the first a it sees, until it comes to the [. It then scans right, erasing one a, one b, and one c. It continues to sweep left and right over the input, erasing one occurrence of each letter in each pass. If on some pass it sees at least one occurrence of one of the letters and and no occurrences of another, it rejects. Otherwise, it eventually erases all the letters and makes one pass between [ and ] seeing only blanks, at which point it accepts.
Formally, this machine has $Q = \{s, q_1, ... , q_{10}, q_a, q_r\}, Σ > = \{a,b, c\}, Γ = \Sigma ∪ \{[, \_, ]\}$" (page 211, Example 28.1)
Are they simply creating states based on their informal definition? Or is there some methodology they are implementing that determines the number of states? If there is some sort of methodology, is it a general methodology that can be applied to other Turing machines? Any help regarding this would be greatly appreciated.
Asked By : tdark
Answered By : babou
I am afraid you cannot tell the number of states from an informal description. There may be states needed to handle trivial details or limit cases that are not obvious from that description. So the answer is usually: as many states as needed to actually implement the behavior described informally.
Better precision may be required when analyzing some complexity issues, though even then it may be up to some constant.
For simpler problems, people may give a detailed description of the TM where you can count the states. This may also happen when you study techniques for combining 2 TMs in some way. Then you may want a formula that gives you (a bound for) the number of states of the combination from the number of states of the 2 initial TM (and possibly some other parameters of the twp TM)
But describing TM in details is like programming in machine language: very tedious and highly prone to errors and bugs of all kinds. And usually you do not have a testing environent.
If there is a methodology, it is probably in combining TM that can perform some specific tasks. It is like library functions in programming languages, which implement specific algorithms that you combine to solve a problem.
So the informal description may also, to some extent, be understood as a high-level language that does not yet have a compiler. So you do not really know what machine code you will get. But do not take this last sentence too seriously.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/32145
0 comments:
Post a Comment
Let us know your responses and feedback