CS21 Decidability and Tractability
Lecture 11
January 29, 2024
Examples of basic operations
Copyright By PowCoder代写 加微信 powcoder
• Convince yourself that the following types of operations are easy to implement as part of TM “program”
(but perhaps tedious to write out…)
– incrementing/decrementing – arithmetic operations +, -, *, /
January 29, 2024 CS21 Lecture 11 2
Universal TMs and encoding
• the input to a TM is always a string in Σ* • often we want to interpret the input as
representing another object • examples:
– tuple of strings (x, y, z)
– 0/1 matrix
– graph in adjacency-list format – Context-Free Grammar
January 29, 2024 CS21 Lecture 11 3
Universal TMs and encoding
• the input to a TM is always a string in Σ*
• we must encode our input as such a string • examples:
– tuples separated by #: #x#y#z
– 0/1 matrix given by: #n#x# where x ∈ {0,1}n2
• any reasonable encoding is OK
• emphasize “encoding of X” by writing
January 29, 2024 CS21 Lecture 11 4
Universal TMs and encoding
• some strings not valid encodings and these are not in the language
make sure TM can recognize invalid encodings and reject them
January 29, 2024 CS21 Lecture 11 5
“yes” “no”
Universal TMs and encoding
• We can easily construct a Universal TM that recognizes the language:
ATM ={
• this is a remarkable feature of TMs (not possessed by FA or NPDAs…)
• means there is a general purpose TM whose input can be a “program” to run
January 29, 2024 CS21 Lecture 11 6
Church-Turing Thesis
• manyothermodelsofcomputation
– we saw multitape TM, nondeterministic TM – others don’t resemble TM at all
– common features:
• unrestricted access to unlimited memory • finite amount of work in a single step
• everysingleonecanbesimulatedbyTM
• manyareequivalenttoaTM
• problemsthatcanbesolvedbycomputerdoes
not depend on details of model!
January 29, 2024 CS21 Lecture 11 7
Church-Turing Thesis
• the belief that TMs formalize our intuitive notion of an algorithm is:
• Note: this is a belief, not a theorem.
January 29, 2024 CS21 Lecture 11 8
The Church-Turing Thesis
everything we can compute on a physical computer
can be computed on a Turing Machine
Recursive Enumerability
• Why is “Turing-recognizable” called RE?
• Definition: a language L ⊆ Σ* is recursively enumerable if there is exists a TM (an “enumerator”) that writes on its output tape
#x1#x2#x3#…
and L = {x1, x2, x3, …}.
• The output may be infinite
January 29, 2024 CS21 Lecture 11 9
Recursive Enumerability
Theorem: A language is Turing-recog- nizable iff some enumerator enumerates it.
(⇐) Let E be the enumerator. On input w:
– Simulate E. Compare each string it outputs with w.
– If w matches a string output by E, accept.
January 29, 2024 CS21 Lecture 11 10
Recursive Enumerability
Theorem: A language is Turing-recog- nizable iff some enumerator enumerates it.
(⇒) Let M recognize language L ⊆ Σ*.
– let s1, s2, s3, … be enumeration of Σ* in
lexicographic order. – for i = 1,2,3,4,…
• simulate M for i steps on s1, s2, s3, …, si
– if any simulation accepts, print out that sj
January 29, 2024 CS21 Lecture 11 11
context free languages
all languages
Undecidability
regular languages
decidable ⊆ RE ⊆ all languages
our goal: prove these containments proper
January 29, 2024 CS21 Lecture 11 12
Countable and Uncountable Sets
• the natural numbers
N = {1,2,3,…} are
• Definition: a set S is countable if it is finite, or it is infinite and there is a bijection
January 29, 2024 CS21 Lecture 11 13
Countable and Uncountable Sets • Theorem: the positive rational numbers
Q = {m/n : m, n ∈ • Proof:
N } are countable. …
January 29, 2024 CS21 Lecture 11
1/1 1/2 1/3 1/4 1/5 1/6 … 2/1 2/2 2/3 2/4 2/5 2/6 … 3/1 3/2 3/3 3/4 3/5 3/6 … 4/1 4/2 4/3 4/4 4/5 4/6 … 5/1 …
Countable and Uncountable Sets
Theorem: the real numbers countable (they are “uncountable”).
• How do you prove such a statement?
– assume countable (so there exists bijection f)
– derive contradiction (some element not mapped to by f)
– technique is called diagonalization (Cantor) January 29, 2024 CS21 Lecture 11 15
Countable and Uncountable Sets
January 29, 2024
R is countable
R according to the bijection f: n f(n) _
3.14159… 5.55555… 0.12345… 0.50000…
CS21 Lecture 11 16
Countable and Uncountable Sets
R is countable
R according to the bijection f:
January 29, 2024
3.14159… 5.55555… 0.12345… 0.50000…
set x = 0.a1a2a3a4…
where digit ai ≠ ith digit after decimal point of f(i) (not 0, 9)
e.g. x = 0.2312…
x cannot be in the list!
CS21 Lecture 11 17
non-RE languages
Theorem: there exist languages that are not Recursively Enumerable.
Proof outline:
– the set of all TMs is countable
– the set of all languages is uncountable
– the function L:{TMs} →{languages} cannot be
January 29, 2024 CS21 Lecture 11 18
non-RE languages
• Lemma: the set of all TMs is countable. • Proof:
– each TM M can be described by a finite- length string
– can enumerate these strings, and give the
natural bijection with
January 29, 2024 CS21 Lecture 11 19
non-RE languages • Lemma: the set of all languages is
uncountable
– fix an enumeration of all strings s1, s2, s3, … (for example, lexicographic order)
– a language L is described by its characteristic
vector 𝜒! whose ith element is 0 if si is not in L and1ifsi isinL
January 29, 2024 CS21 Lecture 11 20
non-RE languages
– suppose the set of all languages is countable
– list characteristic vectors of all languages according to the bijection f:
January 29, 2024
f(n) _ 0101010… 1010011… 1110001… 0100011…
CS21 Lecture 11 21
non-RE languages
– suppose the set of all languages is countable
– list characteristic vectors of all languages according to the bijection f:
January 29, 2024
f(n) _ 0101010… 1010011… 1110001… 0100011…
set x = 1101…
where ith digit ≠ ith digit of f(i) x cannot be in the list!
therefore, the language with characteristic vector x is not in the list
CS21 Lecture 11 22
{anbn : n ≥ 0 }
regular languages
context free languages
some language
all languages
{anbncn : n ≥ 0 }
• This language might be an esoteric, artificially constructed one. Do we care?
• We will show a natural undecidable L next. January 29, 2024 CS21 Lecture 11 23
The Halting Problem • Definition of the “Halting Problem”:
HALT = {
• HALT is recursively enumerable.
• Is HALT decidable?
January 29, 2024 CS21 Lecture 11 24
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com