In Chapter 4 in Computational Complexity by Arora and Barak it states, regarding the configuration graph of a Turing Machine, that

If M is deterministic, then the graph has out-degree one, and if M is nondeterministic, then the graph has out-degree at most two.

In the configuration graph, a directed edge is placed from the configurations $C$ to $C'$ if we can obtain $C'$ from $C$ via a single transition. Also, the authors assume we are working with two tape Turing machine with one read-only input tape and one read-write work tape. Here, the authors define a configuration by

A configuration of a TM M consists of the contents of all nonblank entries of M’s tapes, along with its state and head position, at a particular point in its execution.

I understand that the out-degree for a deterministic machine must be 1, but I do not see why the out-degree for the non-deterministic machine can be at most 2. Given that the authors assume that $\Gamma= \{0,1\}$, I would assume that the number of possible configurations reachable from any given configuration would be $|\Gamma||Q||\{L,R\}^2|$ for a two tape Turing machine, where $Q$ is the set of states and one head is on a read-only input tape. Why would the out-degree of this graph be at most $2$ instead?


1 Answer 1


Based on some research into other things related to TMs, I discovered that any NDTM that has at most $k$ possible branches at each step can be modified into an NDTM that has at most $2$ possible branches at each step at the cost of a $\log_2(k)$ slowdown. Though I can not find any mention of this anywhere in the textbook, I assume this is what the authors are assuming.

  • $\begingroup$ Exactly. However, even if we do not assume this, a constant bound on the out-degree of the configuration graph seems good enough for most purposes (such as, as a minor detail in the proof of Savitch's Theorem). $\endgroup$ May 30, 2022 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.