Lecture notes - University of Iowa

22c:135 Theory of Computation
Nestan Tsiskaridze
Course Website:
http://divms.uiowa.edu/~ntsiskaridze/teaching/135
The University of Iowa
Department of Computer Science
Lecture 22
Reductions Via Computation Histories
(Recall)
The computation history for a Turing machine on an input is
simply the sequence of configurations that the machine goes
through as it processes the input.
It is a complete record of the computation of this machine.
Reductions Via Computation Histories
(Recall)
Definition:
Let M be a Turing machine and ω an input string.
An accepting computation history for M on ω is a sequence of
configurations, C1, C2,..., Cl, where:
C1 is the start configuration of M on ω, Cl is an accepting
configuration of M, and each Ci legally follows from Ci−1 according
to the rules of M.
A rejecting computation history for M on ω is defined similarly,
except that Cl is a rejecting configuration.
Reductions Via Computation Histories
(Recall)
Computation histories are finite sequences.
If M doesn’t halt on ω, no accepting or rejecting computation
history exists for M on ω.
Deterministic machines have at most one computation history
on any given input.
Nondeterministic machines may have many computation
histories on a single input, corresponding to the various
computation branches.
Reductions Via Computation Histories
Our first undecidability proof using the computation history method
concerns a type of machine called a linear bounded automaton.
A linear bounded automaton (LBA) is a restricted type of Turing
machine wherein the tape head isn’t permitted to move off the
portion of the tape containing the input.
Reductions Via Computation Histories
A linear bounded automaton is a Turing machine with a limited
amount of memory.
It can only solve problems requiring memory that can fit within the
tape used for the input.
Using a tape alphabet larger than the input alphabet allows the
available memory to be increased up to a constant factor.
Hence we say that for an input of length n, the amount of memory
available is linear in n - thus the name of this model.
Schematic of an LBA:
Reductions Via Computation Histories
Despite their memory constraint, LBAs are quite powerful.
Examples: the deciders for ADFA, ACFG, EDFA, and ECFG all are
LBAs.
Every CFL can be decided by an LBA.
In fact, coming up with a decidable language that can’t be decided
by an LBA takes some work.
Theorem: ALBA is Decidable
Problem:
Testing whether an LBA accepts an input is a decidable problem.
Language: The language ALBA .
ALBA = {‹M, ω› | M is an LBA that accepts string ω}
Theorem:
ALBA is decidable.
Lemma
Lemma:
An LBA can have only a limited number of configurations when a
string of length n is the input.
Formally: Let M be an LBA with q states and g symbols in its tape
alphabet. There are exactly qngn distinct configurations of M for a
tape of length n.
Lemma
Lemma:
An LBA can have only a limited number of configurations when a
string of length n is the input.
Formally: Let M be an LBA with q states and g symbols in its tape
alphabet. There are exactly qngn distinct configurations of M for a
tape of length n.
Proof:
A configuration of M is a tuple: (state, headPosition, tapeContents).
Recall:
Configuration 1011q701111
Lemma
Lemma:
An LBA can have only a limited number of configurations when a
string of length n is the input.
Formally: Let M be an LBA with q states and g symbols in its tape
alphabet. There are exactly qngn distinct configurations of M for a
tape of length n.
Proof:
A configuration of M is a tuple: (state, headPosition, tapeContents).
●
●
●
●
M has q states.
Length of input is n, so the head can be in n positions.
Only gn possible strings can appear on the tape.
Hence, qngn is the number of different configurations of M.
Theorem: ALBA is Decidable
Theorem:
ALBA is decidable
Proof idea:
To decide whether an LBA M accepts ω simulate M on ω.
During the simulation:
●
●
If M halts and accepts or rejects, we accept or reject accordingly.
If simulation does not halt, detect the loop so that one can halt
and reject.
How do we detect the loop?
Loop Detection
During the computation M goes from configuration to configuration.
If M ever repeats a configuration, it would go on to repeat this
configuration over and over again, and thus looping.
Since M is an LBA, the amount of tape available to it is limited.
M can only be in limited number of configurations on this amount
of tape: qngn configurations.
Hence, if it performs a number of steps larger than qngn and it did
not halt, then M repeats a configuration and thus it loops.
Proof of ALBA Decidability
ALBA = {‹M, ω› | M is an LBA that accepts string ω}
The algorithm that decides ALBA is:
L = "On input ‹M, ω›, M is an LBA, ω a string:
1. Simulate M on ω for qngn steps or until it halts.
2. If M halted: accept if M has accepted, and reject if M
rejected. If M has not halted, reject."
Proof of ALBA Decidability
This theorem shows that LBAs and TMs differ in the essential way:
for LBAs the acceptance problem is decidable while for TMs – not.
Certain other problems involving LBAs remain undecidable.
Example: emptiness problem
ELBA = {‹M› | M is an LBA where L(M) = ∅} is undecidable.
Theorem: ELBA is Undecidable
Theorem:
ELBA = {‹M› | M is an LBA where L(M) = ∅} is undecidable.
Proof idea:
By reduction of ATM to ELBA, show that if ELBA is decidable then so is
ATM.
Theorem: ELBA is Undecidable
Proof idea:
To decide if ‹M, ω› ∈ ATM means to determine for M and ω
whether M accepts ω. Under the assumption that ELBA is
decidable: we can construct a certain auxiliary LBA B and test if
L(B) is empty.
The language recognized by B consists of all accepting
computation histories of M on ω:
If M accepts ω, L(B) contains one string and so L(B) ≠ ∅.
If M does not accept ω, L(B) = ∅.
Hence, if we can detect whether L(B) is empty, we can determine
whether M accepts ω.
Theorem: ELBA is Undecidable
Constructing B from M and ω:
We need to show how a TM can obtain a description of B from M
and ω.
Construct B to accept its input x, if x is an accepting computation
history for M on ω.
Note: the accepting configurations of B are represented as single
strings with configurations separated by #, i.e.:
x = #C1#C2#. . .#Cl#
Theorem: ELBA is Undecidable
LBA B works as follows:
When it receives an input x, B is supposed to accept x if x is an
accepting computation history for M and ω.
First, B breaks up x according to delimiters into strings: C1,C2,...,Cl.
Then, B checks the conditions:
1. C1 is the start configuration for M on ω, i.e. C1 = q0ω1ω2...ωn,
q0 is the start state of M.
2. Each Ci+1 legally follows from Ci: i.e. verify that Ci and Ci+1 are
identical except for the positions under and adjacent to the head in
Ci. These positions must be updated according to the transition
function of M.
3. Cl is an accepting configuration for M on ω, i.e., Cl contains
qaccept of M.
Theorem: ELBA is Undecidable
Condition (2) can be verified directly from the transition function δ.
This is shown below for δ(q3, a) = (q5,x,R).
Checking can be performed by zig-zagging between corresponding
positions of Ci,Ci+1.
Theorem: ELBA is Undecidable
Proof:
Suppose that TM R decides ELBA. Construct TM S that decides ATM
as follows:
S = "On input ‹M, ω›, M a TM and ω a string:
1. Construct LBA B from M and ω as described above.
2. Run R on input ‹B›
3. If R rejects, accept; if R accepts, reject."
Theorem: ELBA is Undecidable
Note:
If R accepts ‹B› then L(B) = ∅, thus M has no accepting
computation on ω, and M does not accept ω.
Consequently S rejects ‹M, ω›.
If R rejects ‹B›, then L(B) ≠ ∅. Since the only string B can accept
is an accepting computation history for M on ω it means that M
accepts ω.
Consequently S accepts ‹M, ω›.
This is a contradiction, so R cannot exist.
Theorem: ALLCFG is Undecidable
Problem: Test whether a CFG generates all possible strings over
its terminal alphabet Σ.
Language: the language
ALLCFG = {‹G› | G is CFG and L(G) = Σ*}
Theorem:
ALLCFG is undecidable.
Proof idea: By contradiction. Assume that ALLCFG is decidable
and then show that ATM is then decidable.
Theorem: ALLCFG is Undecidable
Proof idea:
Using the decidability of ALLCFG, one can devise the following
decision procedure for ATM:
For a TM M and input ω construct a CFG G that generates all
strings over the extended alphabet of M iff M does not accept ω.
If M does accept ω, G does not generate a particular string,
namely the accepting computation history for M on ω.
Note: G is designed such that it generates all strings that are not
accepting computation histories for M on ω.
Theorem: ALLCFG is Undecidable
Strategy:
We need to make the CFG G generate all strings that fail to be an
accepting computation history for M on ω.
A string may fail to be an accepting computation history for several
reasons: if a computation history for M on ω appears as
#C1#C2#...#Cl# and
1. does not start with C1, or
2. does not end with an accepting configuration, or
3. some Ci does not properly yield Ci+1 under the rules of M.
Since CFG and PDA are equivalent, we may use PDA to check the
above conditions. For this theorem designing a PDA is easier.
Theorem: ALLCFG is Undecidable
Designing the PDA D:
In this instance, D will start by nondeterministically branching to
guess which of the preceding three conditions to check.
1. One branch checks on whether the beginning of the input string is
C1 and accepts if it isn’t.
2. Another branch checks on whether the input string ends with a
configuration containing the accept state qaccept and accepts if it's not.
3. The third branch is supposed to accept if some Ci does not
properly yield Ci+1:
Theorem: ALLCFG is Undecidable
Designing the PDA D:
3. The third branch is supposed to accept if some Ci does not
properly yield Ci+1:
It works by scanning the input until it nondeterministically decides
that it has come to Ci.
Next, it pushes Ci onto the stack until it comes to the end as marked
by the # symbol. Then D pops the stack to compare with Ci+1. They are
supposed to match except around the head position, where the
difference is dictated by the transition function of M.
Finally, D accepts if it discovers a mismatch or an improper update.
Theorem: ALLCFG is Undecidable
Designing the PDA D:
The problem with this idea is that when D pops Ci off the stack, it is in
reverse order and not suitable for comparison with Ci+1.
To resolve: we write the computation history differently.
Every other configuration appears in reverse order. The odd positions
remain written in the forward order, but the even positions are
written backward.
Rewritten computation history:
Theorem: ALLCFG is Undecidable
Proof:
Suppose that TM R decides ALLCFG. Construct TM S that
decides ATM as follows:
S = "On input ‹M, ω›, M a TM and ω a string:
1. Construct CFG G from M and ω as described above
2. Run R on input ‹G›
3. If R rejects, accept; if R accepts, reject."
Theorem: ALLCFG is Undecidable
Note:
If R accepts ‹G› then L(G) = Σ*, thus M has no accepting
computation on ω, and M does not accept ω. Consequently S
rejects ‹M, ω›.
If R rejects ‹G›, L(B) ≠ Σ*. Since the only string G cannot generate
is an accepting computation history for M on ω it means that M
accepts ω. Consequently S accepts ‹M, ω›.
This is a contradiction, so R cannot exist.

Download Report