# CS代考计算机代写 Computational Complexity and Computability

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 ∈SDD.

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.