CS21 Decidability and Tractability
Lecture 12 January 31, 2024
{anbn : n ≥ 0 }
regular languages
Copyright By PowCoder代写 加微信 powcoder
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 31, 2024 CS21 Lecture 12 2
The Halting Problem • Definition of the “Halting Problem”:
HALT = {
• HALT is recursively enumerable.
• Is HALT decidable?
January 31, 2024 CS21 Lecture 12 3
The Halting Problem
Theorem: HALT is not decidable (undecidable).
– Suppose TM H decides HALT
– Define new TM H’: on input
• if H accepts
January 31, 2024 CS21 Lecture 12 4
The Halting Problem
– define new TM H’: on input
• if H accepts
• if H rejects
• if it halts, then H rejects
• if it loops, then H accepts
– contradiction.
January 31, 2024 CS21 Lecture 12 5
The Halting Problem
Turing Machines
H’: n Y n Y Y n Y
January 31, 2024 CS21 Lecture 12
box (M, x): does M halt on x?
The existence of H which tells us yes/no for each box allows us to construct a TM H’ that cannot be in the table.
{anbn : n ≥ 0 }
regular languages
context free languages
some language
all languages
{anbncn : n ≥ 0 }
• Can we exhibit a natural language that is non-RE?
January 31, 2024 CS21 Lecture 12 7
RE and co-RE
• The complement of a RE language is called a co-RE language
{anbn : n ≥ 0 } decidable co-RE regular
some language
all languages
context free languages
January 31, 2024
{anbncn:n≥0} HALT
CS21 Lecture 12
RE and co-RE
Theorem: a language L is decidable if and only if L is RE and L is co-RE.
(⇒) we already know decidable implies RE – if L is decidable, then complement of L is
decidable by flipping accept/reject. – so L is in co-RE.
January 31, 2024 CS21 Lecture 12 9
RE and co-RE
Theorem: a language L is decidable if and only if L is RE and L is co-RE.
(⇐) we have TM M that recognizes L, and TM
M’ recognizes complement of L.
– on input x, simulate M, M’ in parallel
– if M accepts, accept; if M’ accepts, reject.
January 31, 2024 CS21 Lecture 12 10
A natural non-RE language
Theorem: the complement of HALT is not recursively enumerable.
– we know that HALT is RE
– suppose complement of HALT is RE
– then HALT is co-RE
– implies HALT is decidable. Contradiction.
January 31, 2024 CS21 Lecture 12 11
{anbn : n ≥ 0 }
co-HALT some language
all languages
decidable co-RE
regular languages
context free languages
{anbncn:n≥0} HALT
Main point: some problems have no algorithms, HALT in particular.
January 31, 2024 CS21 Lecture 12 12
Reductions
• Given a new problem NEW, want to determine if it is easy or hard
– right now, easy typically means decidable
– right now, hard typically means undecidable
• One option:
– prove from scratch that the problem is
decidable, or
– prove from scratch that the problem is
undecidable (dream up a diag. argument)
January 31, 2024 CS21 Lecture 12 13
Reductions
• A better option:
– to prove NEW is decidable, show how to transform it into a known decidable problem OLD so that solution to OLD can be used to solve NEW.
– to prove NEW is undecidable, show how to transform a known undecidable problem OLD into NEW so that solution to NEW can be used to solve OLD.
• called a reduction
January 31, 2024 CS21 Lecture 12 14
Reductions
Reductions are one of the most important and widely used techniques in theoretical
Computer Science.
• especially for proving problems “hard”
– often difficult to do “from scratch”
– sometimes not known how to do from scratch – reductions allow proof by giving an algorithm
to perform the transformation
January 31, 2024 CS21 Lecture 12 15
Example reduction
• Try to prove undecidable:
ATM ={
• We know this language is undecidable:
HALT = {
– suppose ATM is decidable –showthatwecanuseATM todecideHALT – conclude HALT is decidable. Contradiction.
January 31, 2024 CS21 Lecture 12 16
Example reduction
• How could we use procedure that decides ATM to decide HALT?
– given input to HALT:
• Some things we can do:
– check if
– construct another TM M’ and check if
January 31, 2024 CS21 Lecture 12 17
Example reduction
• Deciding HALT using a procedure that decides ATM (“reducing HALT to ATM”).
– on input
– check if
• if yes, the M halts on w; ACCEPT
• if no, then M either rejects w or it loops on w
– construct M’ by swapping qaccept/qreject in M – check if
• if yes, then M’ accepts w, so M rejects w; ACCEPT • if no, then M neither accepts nor rejects w; REJECT
January 31, 2024 CS21 Lecture 12 18
Example reduction • Preceding reduction proved:
Theorem: ATM is undecidable.
Proof (recap):
– suppose ATM is decidable –weshowedhowtouseATM todecideHALT – conclude HALT is decidable. Contradiction.
January 31, 2024 CS21 Lecture 12 19
Another example
• Try to prove undecidable:
ETM ={
• which problem should we reduce from? – HALT = {
–ATM ={
• Some things we can do:
– check if
– construct another TM M’ and check if
January 31, 2024 CS21 Lecture 12 20
Another example
• We are given input
• We want to use a procedure that decides
ETM to decide if
– check if
– helpful if could make M reject everything except possibly w.
January 31, 2024 CS21 Lecture 12 21
Another example
Is this OK? finite # of states?
• Construct TM M’:
– on input x, if x ≠ w, then reject
– else simulate M on x, and accept if M does.
• on input
– construct M’ from description of M
– check if M’ ∈ ETM
• if no, M must accept w; ACCEPT
• if yes, M cannot accept w; REJECT
January 31, 2024 CS21 Lecture 12 22
Another example • Preceding reduction proved:
Theorem: ETM is undecidable.
Proof (recap):
– suppose ETM is decidable –weshowedhowtouseETM todecideATM – conclude ATM is decidable. Contradiction.
January 31, 2024 CS21 Lecture 12 23
Example reduction
• We proved
ATM ={
undecidable, by reduction from
HALT = {
• We proved
undecidable by reduction from ATM
January 31, 2024 CS21 Lecture 12 24
ETM ={
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com