CS计算机代考程序代写 algorithm COMP30026 Models of Computation - Reducibility

COMP30026 Models of Computation – Reducibility

COMP30026 Models of Computation
Reducibility

Bach Le / Anna Kalenkova

Lecture Week 12. Part 1

Semester 2, 2021

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 1 / 24

Undecidable Languages

In the last lecture we saw that

ATM = {〈M ,w〉 | M is a TM and M accepts w}

is undecidable.

Tute exercise T12.1 asks you to prove that it follows that

HaltTM =

{

〈M ,w〉

∣

M is a Turing machine and
M halts when run on input w

}

is also undecidable.

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 2 / 24

At Least A
TM

Is Recognisable

Note that

ATM = {〈M ,w〉 | M is a TM and M accepts w}

is Turing recognisable.

The reason is that it is possible to construct a universal Turing
machine U which is able to simulate any Turing machine.

On input 〈M ,w〉, U simulates M on input w .

If M enters its accept state, U accepts.

If M enters its reject state, U rejects.

If M never halts, neither does U.

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 3 / 24

Hilbert’s Tenth Problem

Mathematicians have this proud history of
inventing algorithms and posing algorithmic
challenges.

Here, for example, is the famous tenth
problem from a list of 23 posed by David
Hilbert in 1900: David Hilbert

Find an algorithm that determines whether a polynomial (in
many variables but with integer coefficients) has an integral
root.

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 4 / 24

Hilbert’s Tenth Problem

70 years after Hilbert posed his tenth problem,
based on work by J. Robinson, Y. Matiyasevich
proved that there is no algorithm for it.

{p | p is a polynomial with integral root} is
undecidable.

However, this language does have a recogniser.

If the input polynomial p has k variables
x1, . . . , xk then we can simply enumerate all
integer k-tuples (v1, . . . , vk) and evaluate
p(v1, . . . , vk), one by one. If p(v1, . . . , vk) = 0,
accept. We refer to this type of problem as
semi-decidable.

Julia Robinson

Y. Matiyasevich

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 5 / 24

Closure Properties

The set of Turing recognisable languages is closed under the regular
operations, and intersection. It is not closed under complement.

The set of decidable languages is closed under the same operations,
and also under complement.

Week 11 tute exercises explore some of these closure results in more
detail.

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 6 / 24

Relating Decidability and Recognisability

Theorem: A language L is decidable iff both L and its complement
Lc are Turing recognisable.

Proof: If L is decidable, clearly L and also Lc are recognisable.

Assume both L and Lc are recognisable. That is, there are
recognisers M1 and M2 for L and L

c , respectively.

A Turing machine M can then take input w and run M1 and M2 on
w in parallel. If M1 accepts, so does M . If M2 accepts, M rejects.

Note that at least one of M1 and M2 is guaranteed to accept.

Hence M decides L.

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 7 / 24

A Non-Turing Recognisable Language

This gives us an example of a
language which is not Turing
recognisable: (ATM )

c , that is,
the complement of ATM .

Namely, we know that ATM is
recognisable.

If (ATM )
c was also Turing

recognisable, ATM would be
decidable.

But we have shown that it isn’t.

Regular

Context-free

Context-
sensitive

Decidable

Turing recognisable

Finite
automata

Pushdown
automata

Linear-
bounded
automata

Halting
Turing

machines

Turing machines

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 8 / 24

Too Many Languages

As we have seen, the set {0, 1}∗ of finite binary strings is a countable
set.

Problem set exercise P12.3 asks you to show that the set B of all
infinite binary strings is uncountable.

That is interesting, because it follows that the set of all languages
over any finite non-empty alphabet Σ is also uncountable.

Namely, the set of all languages over Σ is in a one-to-one
correspondence with B, as we now show.

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 9 / 24

Too Many Languages

Let s1, s2, s3, . . . be the standard enumeration of Σ
∗.

For each language A over Σ, there is a unique characteristic sequence
χA ∈ B, whose ith bit is 1 iff si ∈ A:

Σ∗ : { ǫ, a, b, aa, ab, ba, bb, aaa, aab, . . .}
A : { a, aa, ab, aaa, . . .}
χA : 0 1 0 1 1 0 0 1 0 . . .

Hence we cannot put the set of all languages into a one-to-one
correspondence with the set of all Turing machines.

That is, we could never hope to have a recogniser for each possible
language.

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 10 / 24

Reducibility

Let P and P ′ be decision problems with instances pi and p
′
i
.

P can be reduced to P ′ iff there is a Turing machine M :

〈pi〉 −→ M −→ 〈p
′
i
〉

such that answer (pi) can be obtained from answer (p
′
i
).

P reducible to P ′ and P ′ decidable ⇒ P decidable.

P reducible to P ′ and P undecidable ⇒ P ′ undecidable.

So reducibility is useful for proving decidability and undecidability
results.

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 11 / 24

TM Emptiness Is Undecidable

Theorem:

ETM = {〈M〉 | M is a TM and L(M) = ∅}

is undecidable.

Proof: ATM is reducible to ETM . First notice that, given 〈M ,w〉,
a Turing machine can modify the encoding of M , so as to turn M
into M ′ which recognises L(M) ∩ {w}.

Here is what the new machine M ′ does:

1 If input x is not w , reject.

2 Otherwise run M on w and accept if M does.

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 12 / 24

TM Emptiness Is Undecidable

Notice how w has been “hard-wired” into M ′: This machine is like
M , but it has extra states added to perform the test against w .

Also note that

L(M ′) =

{

{w} if M accepts w
∅ otherwise

Here then is a decider for ATM , using a decider R for ETM :

1 From input 〈M ,w〉 construct 〈M ′〉.

2 Run R on 〈M ′〉.

3 If R rejects, accept; if it accepts, reject.

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 13 / 24

The Argument in Pictures

. . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . reject

. . . . . . . . .

. . . accept

. . . . . . . . .

M :

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 14 / 24

The Argument in Pictures

. . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . reject

. . . . . . . . .

. . . accept

. . . . . . . . .

M :

read x

if x 6= w reject
M ′:

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 14 / 24

The Argument in Pictures

. . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . reject

. . . . . . . . .

. . . accept

. . . . . . . . .

M :

read x

if x 6= w reject
M ′:

Yes No

Emptiness Tester

R :

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 14 / 24

The Argument in Pictures

. . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . reject

. . . . . . . . .

. . . accept

. . . . . . . . .

M :

read x

if x 6= w reject
M ′:

Yes No

Emptiness Tester

R :

No Yes

Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 14 / 24

TM Equivalence Is Undecidable

Theorem:

EQTM = {〈M1,M2〉 | M1,M2 are TMs and L(M1) = L(M2)}

is undecidable.

Proof: ETM is reducible to EQTM .

Assume that S decides EQTM . Here is a decider for ETM :

1 Input is 〈M〉.
2 Construct a Turing machine M∅ which rejects all input.
3 Run S on 〈〈M〉, 〈M∅〉〉.
4 If S accepts, accept; if it rejects, reject.

But we know that ETM is undecidable. So EQTM is undecidable.
Models of Computation (Sem 2, 2021) Reducibility © University of Melbourne 15 / 24

Valid and Invalid Computations

Recall how we captured a Turing machine configuration as a string
(such as baq5bb).

A valid computation for Turing machine M = 〈Q,Σ, Γ, δ, q0, qa, qr 〉
(on input w) is a string of form

C1#C2# · · ·#Ck#

where

1 C1 is M ’s start configuration,
2 Ck is an accepting configuration,
3 for each even i ∈ {2, . . . , k}, Ci−1 ⇒ C

R
i

4 for each odd i ∈ {2, . . . , k}, (Ci−1)
R ⇒ Ci

A string (over the same alphabet) which is not a valid computation is
an invalid computation.

The Language of Invalid Computations

Rephrasing: A string w is an invalid computation iff one or more of
the following properties hold:

0 w is not of the form C1# · · ·#Ck# with Ci in Γ
∗QΓ∗.

1 C1 is not a start configuration for M , that is, not in q0Σ
∗.

2 Ck is not accepting, that is, not in Γ
∗qaΓ

∗.

3 Ci−1 6⇒ C
R
i

for some even i .

4 (Ci−1)
R 6⇒ Ci for some odd i .

The set of strings satisfying (0)–(2) are regular languages.

We claim the set of strings satisfying (3) is context-free
(and so is the set satisfying (4)).

The Language of Invalid Computations

Here is how to build a PDA P for the set of strings for which
Ci−1 ⇒ C

R
i

is false for some even i .

1 P non-deterministically skips past an even number of # symbols.

2 While reading through Ci−1, P pushes onto its stack the symbols
of the configuration C obtained by Ci−1 ⇒ C .

3 After skipping the next #, P compares C (backwards) against
the string found until the following #; if they are different, P
scans over the remaining input and accepts.

Conclusion: The language of invalid computations is context-free!

CFG Exhaustiveness is Undecidable

Theorem:

ALLCFG = {〈G 〉 | G is a CFG and L(G ) = Σ
∗}

is undecidable.

Proof: We just saw that, for any Turing machine M , we can
construct a CFG G that generates all the invalid computations for M .

Clearly L(G ) = Σ∗ iff L(M) = ∅.

Hence if ALLCFG is decidable, then so is ETM .

Since we proved the latter undecidable, ALLCFG must be
undecidable as well.

CFG Equivalence is Undecidable

Our final language undecidability result is an easy reduction from
ALLCFG .

Theorem:

EQCFG = {〈G ,G
′〉 | G ,G ′ are CFGs and L(G ) = L(G ′)}

is undecidable.

Proof: Assume we have a decider E for EQCFG . Then we can easily
build a decider for ALLCFG . Namely, given input grammar G over
alphabet Σ, construct a CFG Gall for Σ

∗. Then run E on 〈G ,Gall〉.

Undecidability in Logic

Around 1930, first-order logic had been found to have a sound and
complete axiomatisation (by Kurt Gödel).

What was then considered the foremost outstanding problem of
mathematical logic was the so-called Entscheidungsproblem:
whether there is a decision procedure for first-order logic.

The Entscheidungsproblem is solved when one knows a pro-
cedure by which one can decide in a finite number of opera-
tions whether a given logical expression is generally valid or
is satisfiable. The solution […] is of fundamental importance
for the theory of all fields, the theores of which are all capable
of logical development from finitely many axioms.

David Hilbert and Wilhelm Ackermann, 1928

Undecidability in Logic

As Hilbert and Ackermann point out, if the
answer to the question “is there a decision
procedure for first-order logic” was yes (as
was commonly assumed), that would have
hugely important ramifications.

It would mean that every theory that can
be formalised in first-order logic would
have an algorithm for deciding the truth of
assertions in that theory. Wilhelm Ackermann

Alan Turing set out to prove that the answer was no.

Undecidability in Logic

Validity in propositional logic is decidable.

Validity in first-order predicate logic is undecidable, however, it is
semi-decidable.

However, it is not the quantifiers per se that cause that problem.
We cross the boundary to the undecidable only when the quantifiers
appear together with predicates of arity greater than 1.

Monadic logic, that is, the fragment of predicate logic which does not
allow predicates of arity 2 and above is decidable.

Rice’s Theorem

We have this rather sweeping result:

Rice’s Theorem: Every interesting semantic
Turing machine property is undecidable!

A property P is interesting iff

P(M1) and not P(M2)

for some Turing machines M1 and M2.

It is semantic iff
P(M1) iff P(M2)

for all Turing machines M1 and M2 such that L(M1) = L(M2).

Related Posts