4. Encoding TMs & Undecidable Languages

How do you identify languages that are not decidable or semidecidable?

Use TMs that have TMs as a string

How do you turn a TM into a string?

Encode it

What is an assumption made to encoding arbitrary TMs?

All tape symbols come from a universe of symbols, and all states come from a universe of states.

If there is an algorithm for which every string ∈ {0, 1}* decides whether w is the code of some TM, what happens?

Constructs a machine M such that e(M) = w

What happens if M and M’ are TMs such that e(M) = e(M’), them M = M’

Different machines get different codes

Why would a TM be ambiguous?

Because it forgets the input alphabet Σ, and TMs with different languages may get th esame code

Define SA ⊆ {0, 1}* (“self-accepting”) by

SA = {e(M) | M is a TM and e(M) ∈ L(M)},

and let NSA = SA (“non-self-accepting”).

What does SA and NSA consist of?

→ SA consists of the codes of all TMs that accept their own codes.

→ NSA consists of the codes of all TMs that do not accept their own codes, and of all strings in {0,1}* that are not codes of TMs

Prove NSA is not semidecidable?

By contradiction.

Suppose NSA is semidecidable, then there is a TM M such that: L(M) = NSA. Consider the code e(M).

Case 1: e(M) ∈ L(M). Then, by assumption, e(M) ∈ NSA. Hence, by definition of NSA, e(M) !∈ L(M). A contradiction.

Case 2: e(M) !∈ L(M). Then, by the definition of NSA, e(M) ∈ NSA. A contradiction.

Hence, NSA is not semidecidable.

Prove SA is not decidable?

Since NSA = (complement of) SA is not decidable, (complement of SA) is in particular not decidable. We proved before that the complement of a decidable language is decidable, thus SA cannot be decidable.

Prove SA is decidable?

A Turing machine TSA which accepts SA works as follows. It first checks whether its input w is the code of some Turing machine. If this is not the case, then TSA rejects w . If w is a TM code, then TSA constructs a Turing machine M such that e(M) = w. If{0, 1} is not a subset of M’s input alphabet, then TSA rejects w. Otherwise TSA executes M on w and accepts w if and only if M accepts w. Thus L(TSA) = SA.

What is a Universal TM?

Takes inputs of the form e(M)e(w), where M is a TM and w is a string over M’s input alphabet. Machine U simulates M on input w, where it:

→ Accepts e(M)e(w) if M accepts w,

→ Rejects e(M)e(w) if M rejects w, and

→ Diverges (’loops’) on e(M)e(w) if M diverges on w.