Some general classes of problems

Section 4.1 introduces several broad classes of languages. I am going to give a quick overview of these classes here.

The first class of problems is the accepting problem: given a description of a machine <M> and an input string x, does the machine accept its input? Depending on the type of machine, this class of problem breaks into subclasses A_DFA, A_PDA, and A_TM.

The second class of problems is the emptyness problem: given a description of a machine <M> we have to determine whether or not the machine will accept none of its inputs. This class of problem breaks into subclasses E_DFA, E_PDA, and E_TM.

The third class of problems is the equality problem: given descriptions of two machines <M₁> and <M₂> we have to determine whether or not the two machines accepts the same languages. This class of problem breaks into subclasses EQ_DFA, EQ_PDA, and EQ_TM.

Solving some of these problems

The next five sections below show five examples of these types of problems. Each of the examples I am going to show is decidable by a Turing machine. In each case I will give a description of the language followed by a description of the Turing machine that decides the language.

A_DFA

A_DFA = {<<A>,w> | <A> describes a DFA A and A accepts w }

On input <<A>,w>:

1. Simulate w running on A.
2. If A accepts w, accept; otherwise, reject.

E_DFA

E_DFA = {<A> | <A> describes a DFA A and A accepts no inputs }

On input <A>:

1. If the starting state of A is an accepting state, stop and reject.
2. Mark the start state of A.
3. Repeat until no new states can be marked:
1. Find a transition going from a marked state to an unmarked state.
2. Mark the unmarked state.
3. If the state you just marked is an accepting state, stop and reject.
4. Stop and accept.

EQ_DFA

EQ_DFA = {<<A>,<B>> | <A> describes a DFA A and <B> describes a DFA B and A and B accept the same language. }

The symmetric difference of two sets X and Y is (X∩Y)∪(Y∩X).

On input <<A>,<B>>:

1. Construct the machine that accepts the symmetric difference of the sets L(A) and L(B).
2. Run the algorithm for E_DFA on this machine and return what it does.

A_CFG

A_CFG = {<<G>,w> | <G> is a CFG, w is a string, and G generates w }

On input <<G>,w>:

1. Convert G to Chomsky Normal form, G.
2. Generate all derivations for G that produce strings of length ≤ |w|.
3. If w appears as the result of any of those derivations, stop and accept.
4. Otherwise, stop and reject.

E_CFG

E_CFG = {<G> | <G> is a CFG that generates no strings. }

On input <G>:

1. If the grammar contains any rules whose right hand sides contain only terminals, mark the variables on the left hand side of that rule.
2. Repeat until no new variables can be marked:
1. If the grammar contains any rule all of whose right hand side symbols have been marked, mark the variable on the left hand side of the rule.
3. If the start symbol has been marked, stop and reject.
4. Otherwise, stop and accept.

Decidable and undecidable problems

The table below summarizes the major results of chapters 4 and 5. Section 4.1 presents algorithms that can be used to decide a number of these problems, while sections 4.2 and parts of chapter 5 present proofs that others of these problems can not be decided by any algorithm.

Problem	DFA	PDA	TM
A	Decidable	Decidable	Undecidable
E	Decidable	Decidable	Undecidable
EQ	Decidable	Undecidable	Undecidable

The universal Turing machine

In the lecture notes for section 3.2 I mentioned the idea of a universal Turing machine. This is a Turing machine that is designed to take the description of any other Turing machine as its input, along with an input string x. The universal Turing machine can read this input and then simulate the input string running on the other machine.

Once we have established the existence of such a machine, we will be free to use this machine as a subroutine in other machines that we build. Thus, many of the machines described below feature steps where we simulate running an input on another machine. From this point forward this will always be considered a legitimate step for a Turing machine to do.

A first undecidable language

The textbook presents a proof in section 4.2 that the problem A_TM is undecidable. The strategy that the author uses is to assume that the problem is decidable and then show that this assumption leads to a contradiction. I encourage you to read this proof.

For the sake of variety, I am going to present a similar proof for another important problem in the theory of computation, the halting problem. One unique feature of Turing machines is that they have the ability to get stuck in infinite loops. This means that some machines will never halt when given certain inputs. This then becomes a general problem, called the halting program. Given a description of any Turing machine <M> and any input w, determine whether or not the machine M will eventually halt in an accepting or rejecting state when given this input.

The proof begins by assuming that there is a Turing machine H that can decide the halting problem. We then produce a contradiction in a couple of steps.

First, we construct the following machine, D.

On any input <M>:

1. Run H on the input pair <M>, <M>.
2. If H accepts, drop into an infinite loop and run forever.
3. Otherwise, stop and accept.

The contradiction arises when we run D on the input <D>.

If H predicts that D will halt when run on its own description, D goes ahead and runs forever.

If H predicts that D will run forever when run on its own description, D stops.

In both cases the actual behavior that D exhibits is the opposite of what H predicts will happen. This is a contradiction. The only way out of this contradiction is to drop our original assumption that the halting problem is decidable.