Computational Complexity and Computability
Lecture 6 – UTM & Diagonalization
Koushik Pal
University of Toronto
January 27, 2021
Turing-recognizable and Turing-decidable
Definition
A language is called Turing-recognizable / semi-decidable / recursively enumerable if some TM recognizes it.
A TM is called a decider if it halts on all inputs x ∈ Σ∗.
A language is called Turing-decidable / decidable / recursive if
some TM decides it.
Notation
D={A⊆Σ∗ |Aisdecidable}
SD = {A ⊆ Σ∗ | A is semi-decidable}
Decidability vs NTM
Theorem
A language L is decidable iff some NTM N decides it.
Proof.
(−→)
If L is decidable, it is decided by some TM, and since any TM is by default an NTM, L is decided by an NTM as well.
Decidability vs NTM
(←−)
Construct a TM M from N as before, with the additional requirement: Reject an input w if all branches are exhausted.
If N accepts w, it is accepted by some branch of N and consequently by M.
If N rejects w, it is rejected by all branches of N since N is a decider. Consequently, each branch has finitely many nodes. Moreover, since each node has finitely many children as well, the whole tree is finite. As a result, M can run an exhaustive search and finally reject w.
Remark
Similar results hold for other TM variants.
Universal Turing Machine (UTM)
Definition
A UTM is a reprogrammable machine that can simulate any other TM M.
The input to a UTM is a description of transitions of M, states of M and initial tape contents of M. UTM tracks these three things on three tapes:
Tape 1 : Tape 2 : Tape 3 :
Description of M States of M
Tape content of M
To track these things, we need some mechanism for encoding a TM. We use the alphabet {, } for encoding a TM.
Encoding of a TM
Alphabet Encoding
Encode Γ = {a,a,a,…,am} as {,,,…,…}.
m Encode Q = {q,q,q,…,qn} as {,,,…,…}.
State Encoding
Head Move Encoding
Encode {L, R} as {, }.
Transition Encoding
Encode δ(q, a) = (q, a, R) as , with as delimiter.
Machine Encoding
Encode multiple transition rules by separating their individual encodings by the delimiter . For example,
{δ(q, a) = (q, a, R), δ(q, a) = (q, a, L)} is encoded as .
n
Encoding of a TM
A TM is, therefore, described as a string over the alphabet Σ = {, }.
Consequently, the set of TMs forms a language LT M over the alphabet {, }, each string of which is the binary encoding of some TM.
Countable Sets Definition
A set S is countable iff there is a surjective function f : N → S. Example
1. Any
2. The
3. The
4. The
finite set is countable.
set of odd numbers is countable. (f(n) = n + )
set of multiples of is countable. (f(n) = n)
set of integers is countable. (f(n) = (−)n⌊n+⌋)
5. The …
…
… √
wherex=⌈−+ +n⌉.
…
set of (positive) rational numbers is countable.
x(+x) −n+ f(n)= ,
x(−x) +n
SD is countable
Fact
If Σ is a finite set, then Σ∗ is countable. Proof.
Exercise!
Corollary
The set of all TMs is countable. Consequently, SD is countable as well.
Cantor’s Diagonalization Theorem
[, ] is uncountable. Consequently, R is uncountable.
Proof.
Assume for a contradiction that [, ] is countable. Consider an enumeration as follows:
. a a a a a … . a a a a a … . a a a a a … . a a a a a … . a a a a a …
.
Consider the number x = .lllll · · · where li ̸= aii for all i. Clearly, x ∈ [, ], but x is not in the above enumeration.
Cantor’s Diagonalization
A very similar proof shows that
Theorem
P(S) is uncountable for any countably infinite set S.
Corollary
The set of languages over any nonempty finite alphabet Σ (e.g., Σ = {, }) is uncountable.
Proof.
Since Σ is nonempty and finite, Σ∗ is countably infinite. Since a language L is an arbitrary subset of Σ∗, the set of all
languages is P(Σ∗).
By the above theorem, the set of languages over Σ is uncountable.
Existence of a non-semi-decidable language
Theorem
Given a nonempty finite alphabet Σ, there is a language over Σ that is not semi-decidable.
Proof.
We have already shown that the number of TMs, and hence the number of semi-decidable languages over Σ, is countable.
We have also shown that the number of languages over Σ is uncountable.
Hence, there is at least one language over Σ that is not semi-decidable. In fact, there are uncountably many such languages.
Encoding
Goal : Represent objects as strings to feed to a TM.
Fact
Strings can easily represent polynomials, graphs, grammars, automata, and any combination of these objects.
A TM may be programmed to decode the representation so that it can be interpreted in the way we intend.
Notation
We use the notation ⟨O⟩ to denote an encoding into a string representation of the object O. For several objects O, . . . , On, we denote their encoding into a single string as ⟨O, . . . , On⟩.
Example of a non-semi-decidable language Definition
DIAG:={⟨M⟩|M isaTMand⟨M⟩̸∈L(M)}.
Theorem
DIAG ̸∈ SD.
Proof.
Assume for a contradiction that there exists a TM M such that L(M) = DIAG. Then
⟨M⟩∈L(M) ⇐⇒ ⟨M⟩∈DIAG ⇐⇒ ⟨M⟩̸∈L(M).
Example of a semi-decidable but not decidable language Definition
ATM := {⟨M,w⟩ | M accepts w}. Theorem
ATM ∈SD\D.
Proof.
ATM ∈ SD because ATM = L(U) where U is a UTM that simulates M on w.
ATM ̸∈ D because otherwise DIAG ∈ D which yields the required contradiction:
⟨M⟩ ∈ DIAG ⇐⇒ ⟨M⟩ ̸∈ L(M) ⇐⇒ ⟨M,⟨M⟩⟩ ̸∈ ATM.
Corollary
D SD.