2.1 Decidable Languages

When is a language decidable (recursive)?

If it is accepted by some TM, M, that on every input it eventually reaches a halting configuration.

It is said that M decices L.

When is a string w ∈ Σ* in TM M?

If, when M is run on w, it reaches state h_a

True or false:

Every context-sensitive language is decidable?

True

True or false:

If a language L is decidable, then the complement Σ* − L (L with a line on the top) is also decidable.

True

Prove that, if a language L is decidable, its complement is decidable.

Let M be a TM that accepts L and halts on every input. Without loss of generality, we assume that M never crashes at the start of the tape. We modify M to a machine (M with a line on the top (complement)) by swapping the accept and reject state.

Then L(complement of M) = complement of L.

Complement of M halts on every input because M does so. Hence complement of L is decidable.

What is the complement of h_a?

h_r

What is the complement of h_r?

h_a

True or false:

If both a language L and its complement are semidecidable, then L is decidable

True

Prove that if a language L and its complement are semidecidable, then L is decidable.

Define crash avoidance in Turing Machines

For every Turing Machine M, there is a TM, M, such that L(M) = L(M’) and M’ does not crash on any input.

Prove that for every Turing Machine M, there is a TM, M, such that L(M) = L(M’) and M’ does not crash on any input.

We extend Γ with a new symbol #. Machine M’ write # on the first square, inserts ∆ on the 2nd square by shifting the input string one position to the right (left as an exercise), moves the tape head to the second square, and then executes the transitions of M.

→ We also define, for each q ∈ Q′ − {h_a, h_r}, δ′(q, #) = (h_r, #, S).

How do you find languages that are not decidable or even semidecidable?

By using TMs that take TMs as an input