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. The example (Example 28.1, page 211) reads as follows:

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 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 ∪ \{[, \_, ]\}$

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?

  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – FrankW
    Oct 21 '14 at 5:13
  • $\begingroup$ plz cite the book. no the formal representation does not seem to match the informal representation in particular its not clear what $q_1, ..., q_{10}$ refer to. the problem would seem to require fewer states related to the 3 characters being scanned. $\endgroup$
    – vzn
    Oct 21 '14 at 15:17
  • $\begingroup$ @vzn Citations fixed. $\endgroup$
    – tdark
    Oct 21 '14 at 15:52

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.

  • $\begingroup$ So do you have an idea as to how the author was able to determine that states $q_1, ..., q_{10}$ was all that was necessary to decide this particular machine? $\endgroup$
    – tdark
    Oct 21 '14 at 15:50
  • $\begingroup$ @tdark My guess is that they actually described the machine in details. There is a reference to a figure that may contain a complete description (I do not have access to that book). It may also be a plausible random choice. The problem given is not very hard, even to program a TM. I suspect it may be possible to save on the number of state by erasing only in one direction. End markers may not be needed. Some details may depend on the specific brand of TM used in the book. And another comment says that the machine given in the book does not match the informal description. This is just training. $\endgroup$
    – babou
    Oct 21 '14 at 16:11

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.