in conjunctive normal form.
5. Determine whether or not the expression
is satisfiable.
6. Generalize Theorem 14.1 for k tapes, showing that n moves on a k-tape
machine can be simulated on a standard machine in O(n 2 ) moves.
7. In the proof of Theorem 14.2 we ignored one fine point. When a
configuration grows, the rest of the tape's contents have to be moved. Does
this oversight affect the conclusion?
14.3 Language Families and Complexity Classes
In the Chomsky hierarchy for language classification, we associate language
families with classes of automata, where each class of automata is defined by the
nature of its temporary storage. Another possibility for classifying languages is
to use a Turing machine and consider time-complexity a distinguishing factor. To
do so, we first define the time-complexity of a language.
Definition 14.1
We say that a Turing machine M decides a language L in time T(n) if every w in
L with |w| = n is decided in T(n) moves. If M is nondeterministic, this implies
that for every w ∈ L, there is at least one sequence of moves of length less than
or equal to T (|w|) that leads to acceptance, and that the Turing machine halts on
all inputs in time T (|w|).
Definition 14.2
A language L is said to be a member of the class DTIME (T(n)) if there exists a
deterministic multitape Turing machine that decides L in time O(T(n)).
5. Determine whether or not the expression
is satisfiable.
6. Generalize Theorem 14.1 for k tapes, showing that n moves on a k-tape
machine can be simulated on a standard machine in O(n 2 ) moves.
7. In the proof of Theorem 14.2 we ignored one fine point. When a
configuration grows, the rest of the tape's contents have to be moved. Does
this oversight affect the conclusion?
14.3 Language Families and Complexity Classes
In the Chomsky hierarchy for language classification, we associate language
families with classes of automata, where each class of automata is defined by the
nature of its temporary storage. Another possibility for classifying languages is
to use a Turing machine and consider time-complexity a distinguishing factor. To
do so, we first define the time-complexity of a language.
Definition 14.1
We say that a Turing machine M decides a language L in time T(n) if every w in
L with |w| = n is decided in T(n) moves. If M is nondeterministic, this implies
that for every w ∈ L, there is at least one sequence of moves of length less than
or equal to T (|w|) that leads to acceptance, and that the Turing machine halts on
all inputs in time T (|w|).
Definition 14.2
A language L is said to be a member of the class DTIME (T(n)) if there exists a
deterministic multitape Turing machine that decides L in time O(T(n)).