test
antara97
Chapter12.ppt*
Computational Notions
*
Section 12.1 Turing Machines
A Turing machine (TM) is a simple computer
that has an infinite amount of storage in the
form of cells on an infinite tape. There is a
control unit that contains a finite set of state
transition instructions.
(i, a, b, R, j)
An instruction reads the symbol in the current tape cell, writes a symbol to the same cell,
and then moves the tape head one cell left or right or remains at the same cell, after which
the machine enters a new state.
Assumptions:
- The symbol L denotes a blank cell.
- The tape head is initially at the left end of a nonempty input string (unless specified
otherwise)
- There is a designated start state.
- There is one “halt” state.
- The moves are denoted by L, S, R for move left, stay, and move right.
Instructions are represented in graphical form or as 5-tuples, as
shown in the example to the right.
This instruction executes if the current state of the TM is i and the
current input symbol is a. The TM writes b into that cell, moves
right one cell and enters state j.
a
…
…
Control
Unit
Tape
Tape head
Executes a finite set of instructions
i
j
*
*
Acceptance
An input string on the tape is accepted by the TM if the machine enters the halt state.
The language of a TM is the set of all strings accepted by the machine.
Example/Quiz. Given the following simple TM.
(0, a, a, R, halt).
What is the language of the TM?
Answer: If an input string begins with the letter a, then the TM executes the instruction and
halts. So the string is accepted. Therefore, the language of the TM is the set of all strings that
begin with the letter a.
Example. Construct a TM to accept the language {abn | n N}.
Solution. Let the start state be state 0. The idea is to see whether a is in the current cell.
If so, move right to scan b’s until is found.
(0, a, a, R, 1)
(1, , , S, halt)
(1, b, b, R, 1).
Quiz. Construct a TM to accept the language {abna | n N}.
Solution. Let the start state be state 0. The idea is to see whether a is in the current cell.
If so, move right to scan b’s until a is found. Then make sure there is to the right.
(0, a, a, R, 1)
(1, a, a, R, 2)
(1, b, b, R, 1)
(2, , , S, halt).
*
*
Quiz. Construct a TM to accept the language of the regular expression a(a + b)*.
Solution. Let the start state be state 0. The idea is to see whether a is in the current cell.
If so, move right to scan any a’s or b’s until is found.
(0, a, a, R, 1)
(1, a, a, R, 1)
(1, b, b, R, 1)
(1, , , S, halt).
Example/Quiz. Find a TM to accept {anbn | n N}.
Solution. Let the start state be state 0. The idea is to see whether a is in the current cell.
If so, write X and scan right looking for a b to replace by Y.
(0, , , S, halt) accept
(0, a, X, R, 1) mark a with X
(0, Y, Y, R, 3) no more a’s
Scan right looking for b to pair with a:
(1, a, a, R, 1)
(1, Y, Y, R, 1)
(1, b, Y, L, 2) mark b with Y
Scan back left looking for X:
(2, a, a, L, 2)
(2, Y, Y, L, 2)
(2, X, X, R, 0)
Scan right looking for and halt:
(3, Y, Y, R, 3)
(3, , , S, halt)
TMs are very powerful. For example, the preceding example can be generalized to a TM
that accepts the non-context free language {anbncn | n N}. (See Example 13.2 in the
Text.) So a TM can handle two stacks. In fact, a TM can handle any number of stacks.
*
*
Turing Machines with Output
Specify the form of the output on the tape when the machine halts.
Example/Quiz. Find a TM to add 4 to a natural number represented in binary. Start with the
tape head at the right end of the input string and halt with the tape head at the left end of the
output string.
Solution. Let the start state be 0.
Move two cells left:
(0, 0, 0, L, 1)
(0, 1, 1, L, 1)
(1, 0, 0, L, 2)
(1, 1, 1, L, 2)
(1, , 0, L, 2)
Add 1:
(2, 0, 1, L, 3) Move left
(2, 1, 0, L, 2) Carry
(2, , 1, S, halt) Done
Find left end of the string:
(3, 0, 0, L, 3)
(3, 1, 1, L, 3)
(3, , , R, halt) Done
Quiz. How would you construct a TM to add 5 to a binary number?
One Solution: Add 1, move back to right end, and then use the preceding solution.
For this purpose, let the start state be 4.
Add 1:
(4, 0, 1, R, 5) Move right
(4, 1, 0, L, 4) Carry
(4, , 1, R, 5) Move right
Find right end of the string:
(5, 0, 0, R, 5)
(5, 1, 1, R, 5)
(5, , , L, 0) Go add 4
*
*
Example/Quiz. Find a TM to move any string over {a, b} to the left one cell position.
Assume the tape head ends at the left end of any nonempty output string.
Solution. Let the start state be 0.
Find a or b to move:
(0, a, , L, 1) Go write a
(0, b, , L, 2) Go write b
(0, , , L, 4) Done
Write a or b:
(1, , a, R, 3) Write a
(2, , b, R, 3) Write b
(3, , , R, 0) Skip
A trace for input aba (tape head is red):
a b a (0, a, , L, 1)
b a (1, , a, R, 3)
a b a (3, , , R, 0)
a b a (0, b, , L, 2)
a a (2, , b, R, 3)
a b a (3, , , R, 0)
a b a (0, a, , L, 1)
a b (1, , a, R, 3)
a b a (3, , , R, 0)
a b a (0, , , L, 4)
a b a (4, , , L, 5)
a b a (5, a, a, L, 5)
a b a (5, b, b, L, 5)
a b a (5, a, a, L, 5)
a b a (5, , , R, halt)
a b a Output.
Move to left end of output:
(4, , , L, 5)
(5, a, a, L, 5)
(5, b, b, L, 5)
(5, , , R, halt).
Quiz. (Exercise 2). Find a TM to search for
the symbol # on an otherwise empty tape,
where the tape head starts at a random cell.
A Solution: Use a new symbol, say x, to mark
cells that have been searched as the machine
alternately looks left and right.
A Sample Trace:
#
# x
# x x
# x x
# x x x
# x x x
# x x x .
*
*
Alternative Definitions of Turing Machine
One-way Infinite Tape Multihead Multitape
Quiz. Why are they all equal in power to the original
definition of a Turing machine?
An n-head or n-tape instruction contains n-tuples for the cell contents and move operations.
Example. A typical instruction for a 2-head or a 2-tape TM is
(0, (a, b), (c, d), (L, R), 1).
Example/Quiz. Implement some sample PDA instructions as
TM instructions for a 2-tape TM. Assume one tape holds the
input string and the other tape holds the stack. Assume the
input is scanned left to right and the the stack grows from
right to left.
PDA Instruction:
1. (i, a, X, nop, j)
2. (i, a, X, pop, j)
3. (i, a, X, push(Y), j)
4. (i, L, X, pop, j).
TM Instruction:
1. (i, (a, X), (a, X), (R, S), j)
2. (i, (a, X), (a, L), (R, R), j)
3. (i, (a, X), (a, X), (S, L), k) and (k, (a, L), (a, Y), (R, S), j)
4. For each letter a: (i, (a, X), (a, L), (S, R), j).
…
…
…
…
…
…
…
…
…
a
input
…
…
X
stack
*
*
Nondeterministic Turing Machines
Example. Generate an arbitrary string over {a, b} of length n.
Solution: Assume the input is any string over {a, b} of length n. The tape head is at the right
end of the output string.
(0, a, a, R, 0)
(0, a, b, R, 0)
(0, b, a, R, 0)
(0, b, b, R, 0)
(0, L, L, L, halt).
Nondeterministic TMs have the same power as deterministic TMs
The idea: Any nondeterministic TM can be simulated by a deterministic TM that simulates
all 1-step computations, then all 2-step computations, and so on. The process stops if some
computation enters the halt state.
*
*
Section 12.2 The Church-Turing Thesis
The Church-Turing Thesis: Anything that is intuitively computable can be be computed by a
Turing machine.
It is a thesis rather than a theorem because it relates the informal notion of intuitively
computable to the formal notion of a Turing machine.
Computational Models
A computational model is a characterization of a computing process that describes the form a
program and describes how the instructions and are executed.
Example. The Turing machine computational model describes the form of TM instructions
and how to execute them.
Example. If X is a programming language, the X computational model describes the form of a
program and how each instruction is executed.
Equivalence of Computational Models
Two computational models are equivalent in power if they solve the same class of problems.
Any piece of data for a program can be represented by a string of symbols and any string of
symbols can be represented by a natural number.
So even though computational models may process different kinds of data, they can still be
compared with respect to how they process natural numbers.
We’ll make the assumption that there is an unlimited amount of memory available. So we can
represent any natural number or any finite string.
Each of the following models of computation is equal in power to the TM model.
*
*
The Simple Programming Language
This imperative programming model processes natural numbers. The language is defined as
follows:
- Variables have type N.
- Assignment statements: X := 0; X := succ(Y); X := pred(Y). (assume pred(0) = 0)
- Composition of statements: S1; S2.
- while X ≠ 0 do S od.
This simple language model has the same power as the Turing machine model.
For input and output use the values of the variables before and after execution.
Example/Quiz. To demonstrate the power of this language, define the following macros.
Some Macros Macro Expansion
X := Y
X := 2
Z := Z + X
Z := X + Y
Z := X monus Y
while X < Y do S od
if X ≠ 0 then S1 else S2 fi
X := succ(Y); X := pred(X).
X := 0; X := succ(X); X := succ(X).
C := X; while C ≠ 0 do Z := succ(Z); C := pred(C) od.
Z := X; C := Y; while C ≠ 0 do Z := succ(Z); C := pred(C) od.
Z := X; C := Y; while C ≠ 0 do Z := pred(Z); C := pred(C) od.
T := Y monus X; while T ≠ 0 do S; T := Y monus X od.
U := X; V := 1;
while U ≠ 0 do S1; V := 0; U := 0 od;
while V ≠ 0 do S2; V := 0 od.
*
*
Partial Recursive Functions
This model consists of a set of functions that take natural numbers as arguments and as
values. The functions are defined as follows, where x can represent zero or more arguments.
- Initial functions: zero(x) = 0, succ(n) = n + 1, and projections (e.g., p2(a, b, c) = b).
- Composition: e.g., ƒ(x) = h(g1(x), …, gm(x)), where h, g1, …, gm are partial recursive.
- Primitive recursion:
ƒ(x, 0) = h(x) (h is partial recursive)
ƒ(x, succ(y)) = g(x, y, ƒ(x, y)) (g is partial recursive).
- Unbounded search (minimalization):
ƒ(x) = min(y, g(x, y) = 0) (g is total partial recursive).
This means that ƒ(x) = y is the minimum y such that g(x, y) = 0, if such a y exists.
This model for constructing functions has the same power as the Turing machine model.
Example. The predecessor and monus functions are partial recursive as follows:
pred(0) = 0
pred(succ(y)) = y, which can be written in the form p1(y, pred(y)).
monus(x, 0) = x
monus(x, succ(y)) = pred(monus(x, y)), which can be written pred(p3(x, y, monus(x, y))).
Quiz. Show that pred(monus(x, y)) = monus(pred(x), y)).
Proof: The equation is true if x = 0 or y = 0. So assume x > 0 and y > 0. Then we have:
pred(monus(x, y)) = if x > y then x – y – 1 else 0
monus(pred(x), y)) = if x – 1 > y then x – 1 – y else 0.
Although x > y and x – 1 > y are different, the if-then-else values are equal. QED.
*
*
Quiz. Let p and q be partial recursive with p(x), q(x) {0, 1}, for false and true. Show that
the logical operations p(x) q(x), ¬ p(x), and p(x) q(x), are partial recursive functions.
Solutions: p(x) q(x) = p(x)q(x)
¬ p(x) = monus(1, p(x))
p(x) q(x) = p(x) + monus(1, p(x))q(x).
Examples (Unbounded Search, Minimalization)
ƒ(x) = min(y, xy = 0) defines ƒ(x) = 0.
ƒ(x) = min(y, x + y = 0) defines ƒ(x) = if x = 0 then 0 else undefined.
ƒ(x) = min(y, monus(x, y) = 0) defines ƒ(x) = x.
ƒ(x) = min(y, monus(y, x) = 0) defines ƒ(x) = 0.
ƒ(x, y) = min(z, monus(x + z, y) = 0) defines ƒ(x, y) = if x ≤ y then 0 else undefined
Example/Quiz. For y ≠ 0, let ƒ(x, y) = min(z, monus(x, yz) = 0). What function does ƒ compute?
Answer: ƒ(x, y) = x / y . To see this, notice that the definition
ƒ(x, y) = min(z, monus(x, yz) = 0)
means that ƒ(x, y) = z is the smallest natural number such that monus(x, yz) = 0.
The definition of monus tells us that
monus(x, yz) = 0 means that x ≤ yz.
So z is the smallest natural number such that x ≤ yz. In other words, we have
y(z – 1) < x ≤ yz.
Divide by y to obtain z – 1 < x/y ≤ z. Therefore z = x / y .
*
*
Markov Algorithms
This model processes strings. An algorithm consists of a finite, ordered, sequence of
productions of the form x y, where x, y A* for some alphabet A.
Any production can be suffixed with (halt) although this is not required.
Execution
Given an input string w A*, perform the following execution step repeatedly.
Scan the productions x y sequentially to see whether x occurs as a substring of w. If so,
replace the leftmost occurrence of x in w by y and reset w to this string. Otherwise halt.
If the x y is labeled with (halt), then halt.
Assumption: w = Lw. So a production of the form L y would transform w to yw.
The Markov algorithm model has the same power as the Turing machine model.
Example. The Markov algorithm consisting of the single production a L will delete all a’s
from any string.
Example. A more instructive Markov algorithm to delete all a’s from any string over {a, b}
can be written as the following sequence of productions (# is an extra symbol).
1. #a #
2. #b b#
3. # L (halt)
4. L #.
An example trace: abab (input)
#abab (by 4)
#bab (by 1)
b#ab (by 2)
b#b (by 1)
bb# (by 2)
bb (by 3, halt).
*
*
Quiz (1 minute). Find a Markov algorithm to replace each a with aa in strings over {a, b}.
Answer. Modify the previous example: 1. #a aa#
2. #b b#
3. # L (halt)
4. L #.
Example/Quiz. Find a Markov algorithm to delete the rightmost b from strings over {a, b}.
Solution: 1. #a a#
2. #b b#
3. # @
4. a@ @a
5. b@ L (halt)
6. @ L (halt)
7. L #.
Example/Quiz. Find a Markov algorithm to implement succ(x), where x is a natural number
represented in binary. Assume no leading zeros (except 0 itself).
Solution: 1. #0 0#
2. #1 1#
3. 0# 1 (halt)
4. 1# @0
5. 1@ @0
6. 0@ 1 (halt)
7. @ 1 (halt)
8. L #.
*
*
Post Algorithms
This model processes strings. An algorithm consists of a finite set of productions of the
form s t where s and t are strings over the union of an input alphabet A with a set of
variables and other symbols. Restriction: If a variable X occurs in t then X occurs in s. A
production can be suffixed with (halt) although this is not required.
Execution
Given an input string w A*, perform the following execution step repeatedly.
Find a production x y such that w matches x.
If so, use the match and y to construct a new string w. Otherwise halt.
If the x y is labeled with (halt), then halt.
Assumption: A variable may match L.
Example. If the input string is 1, then 1 matches 1X. So a production like 1X 1X0 would
transform 1 into 10.
The Post algorithm model has the same power as the Turing machine model.
Example. A Post algorithm with the single production XaY XY will delete all a’s from
any string. Notice the nondeterminism.
Example. A Post algorithm to replace each a with aa in strings over {a, b}.
Solution: 1. aX @aa#X
2. bX @b#X
3. X#aY Xaa#Y
4. X#bY Xb#Y
5. @X# X (halt).
*
*
Example. A Post algorithm to delete the rightmost b from any string over {a, b}.
Solution: 1. Xb X (halt)
2. Xa X#a@
3. Xa#Y X#aY
4. Xb#Y@ XY (halt)
5. #X@ X (halt).
Example/Quiz. Find a Post algorithm to implement succ(x), where x is a natural number
represented in binary. Assume no leading zeros (except 0 itself).
Solution: 1. X0 X1 (halt)
2. X1 X#0#
3. X1#Y# X#0Y#
4. X0#Y# X1Y (halt)
5. #Y# 1Y (halt).
Post Systems
This model generates a set of strings from axioms (a given set of strings) and inference
rules (a given set of productions that map strings to strings by matching).
Execution: Match the left side of a production with an axiom string or a string that has
already been constructed. Then use the match and the right side to construct a new string.
Example. A Post system to generate the binary representations of natural numbers:
Axioms: 0, 1
Inference Rules: 1X 1X0
1X 1X1.
The system generates the set {0, 1, 10, 11, 100, 101, 110, 111, … }.
*
*
Quiz. Find a Post system to generate {a}*.
Solution: Axiom: L
Inference rule: X aX.
Quiz. Find a Post system to generate the set {anbncn | n N}.
One of Many Solutions: Axioms: L, abc
Inference rule: aXbcY aaXbbccY.
The Post system model has the same power as the Turing machine model in the following
sense: A function ƒ : A* A* is Post-computable if there is a Post system to compute the
function as a set of ordered pairs in the form {x#ƒ(x) | x A*}. Post-computable functions
coincide with Turing-computable functions.
Example/Quiz. Generate the function ƒ : {a}* {a}* where ƒ(an) = a2n.
Solution: Axiom: L#L
Inference rule: X#Y Xa#Yaa (or the simpler X aXaa)
This system generates the set {L#L, a#aa, aa#aaaa, …, an#a2n, … }.
Example/Quiz. Generate the function ƒ : N N defined by ƒ(n) = n2, where n is
represented as a string over {a} of length n.
A Solution: Axiom: L#L
Inference rule: X#Y Xa#YXXa.
Proof: In terms of natural numbers, from the pair n#n2 we must construct (n + 1)#(n + 1)2.
We can write (n + 1)2 = n2 + 2n + 1 = n2 + n + n + 1.
So from n#n2 we must get (n + 1)#(n2 + n + n + 1).
In terms of strings over {a}, we transform X#Y into Xa#YXXa. QED.
*
*
Section 12.3 Computability
Some problems cannot be solved by any machine/algorithm.
To prove such statements we need to effectively describe all possible algorithms.
Example (Turing machines). Associate a Turing machine with each n N as follows:
n b(n) (the binary representation of n)
a(b(n)) (b(n) split into 7-bit ASCII blocks, with leading zeros if needed)
if a(b(n)) is the syntax of a TM then a(b(n)) else (0, a, a, S, halt) fi.
So we can effectively describe all possible Turing machines:
T0, T1, T2, …
Of course we could use the same technique to list all possible instances of any computational
model. For example, we can effectively list all possible simple programs and we can
effectively list all possible partial recursive functions.
If we want to use the Church-Turing thesis, then we can effectively list all possible solutions
(e.g., Turing machines) to every intuitively computable problem.
Decision Problems
A decision problem is a problem can be phrased as a yes/no question.
Such a problem is decidable if an algorithm exists to answer yes or no to each
instance of the problem. Otherwise it is called undecidable.
A decision problem is partially decidableif an algorithm exists to halt with the answer
yes to yes-instances of the problem, but may run forever if the answer is no.
*
*
Examples. 1. Is an arbitrary propositional wff a tautology? Decidable.
2. Is an arbitrary first-order wff valid? Undecidable and partially decidable.
3. Does a DFA accept infinitely many strings? Decidable.
4. Does a PDA accept a string s? Decidable.
The Halting Problem
The halting problem asks the following question.
Does an arbitrary program halt on an arbitrary input?
The halting problem is partially decidable: Just execute the program on the input. If the
program halts, output yes.
The halting problem is undecidable.
To prove this, we’ll prove the following form for computable functions.
Is there a computable function that can decide whether an arbitrary computable function
halts on an arbitrary input?
Proof: Assume, BWOC, that the halting problem is decidable. We’ll use the following
effective listing of all computable functions of a single variable.
ƒ0, ƒ1, ƒ2, …
Define the partial function g by
g(n) = if ƒn(n) halts then loop forever else 0 fi.
Observe that g is computable because “ƒn(n) halts” is computable by assumption.
So there is some k such that g = ƒk. Now apply g to k to obtain a contradiction:
g(k) halts iff g(k) does not halt. Therefore the halting problem is undecidable. QED.
*
*
Example/Quiz. Given the following effective listing of all Turing machines.
T0, T1, T2, …
Is it decidable whether Tn halts on some input string of a’s within k steps?
Answer: Yes. Perform the following algorithm.
l := 0; (l represents the length of an input string of a’s. So the tape is initially empty.)
while l ≤ k do
Execute Tn for k steps or until the halt state is reached, whichever comes first;
If the halt state was reached, stop and output the answer YES;
l := l + 1 (Reset the tape with one more a)
od;
Output the answer NO.
Notice: If the while loop terminates without stopping with a YES-answer, then l > k.
In this case Tn will take more than k steps to process l cells with a’s. So the answer is NO.
Some Total Problems
There is no effective listing of the total computable functions.
Proof: To see this for total computable functions of a single variable, assume, BWOC, that
we have the following effective listing of these functions.
ƒ0, ƒ1, ƒ2, …
Define g(n) = ƒn(n) + 1. Since ƒn is total, it follows that g is total too. Therefore g must be
somewhere in the list. So there is some k such that g = ƒk. But then ƒk(k) = g(k) = ƒk(k) + 1,
which is a contradiction. QED.
*
*
The total problem asks whether an arbitrary computable function is total.
The total problem is undecidable.
Proof: Assume, BWOC, that the total problem is decidable. We’ll use the effective listing of
all computable functions of a single variable ƒ0, ƒ1, ƒ2, … . Now define the function
T(n) = if ƒn is total then 1 else 0 fi.
Since “ƒn is total” is computable by assumption, it follows that T is total too. But now we can
effectively list all the total computable functions from the given list as follows:
Let g0 be the smallest k such that T(k) = 1;
Let g1 be the smallest k > g0 such that T(k) = 1;
…
Let g(n +1) be the smallest k > gn such that T(k) = 1.
Continue in this manner to construct the list ƒg0, ƒg1, …, ƒgn, … of all total computable
functions of a single variable. But this contradicts the fact that it can’t be done. QED.
Example/Quiz. Show that we can’t effectively list the total computable functions that have
finite ranges. For example, ƒ(n) = n mod 4 has range {0, 1, 2, 3}.
Proof: Suppose, BWOC, that ƒ0, ƒ1, ƒ2, … is an effective listing of the single-variable
computable functions with finite range. Now define the function
g(n) = if ƒn(n) ≤ 25 then ƒn(n) + 1 else 25 fi.
Observe that g is total, computable, and has finite range. So there is some k such that g = ƒk.
Quiz: What is the contradiction?
Answer: If ƒk(k) ≤ 25 then ƒk(k) = ƒk(k) + 1. If ƒk(k) > 25 then ƒk(k) = 25. QED.
*
*
Post Correspondence Problem (PCP)
Given an arbitrary finite sequence (s1, t1), …, (sn, tn) of pairs of strings, does there exist a
sequence of indices i1, …, ik, with repetitions allowed, such that si1…sik = ti1…tik?
Example/Quiz. Does the following instance of the PCP have a solution?
(ab, b), (b, a), (a, ab), (ba, b).
Answer: Yes. If the pairs are labeled 1, 2, 3, 4, then the sequence 3, 2, 1 gives the equation
abab = abab.
Quiz. Does the following instance of the PCP have a solution?
(a, aa), (aaaa, a).
Answer: Yes. If the pairs are labeled 1, 2, then the sequence 1, 1, 1, 2 gives the equation
aaaaaaa = aaaaaaa.
The Post correspondence problem is undecidable for alphabets of size 2 or more.
The proof involves reducing the problem to the halting problem.
The PCP is also used in proving that it is undecidable to tell whether a context-free grammar
over an alphabet of size 4 or more is ambiguous.
Details of these two proofs can be found in: Harrison, Introduction to Formal Language
Theory, Addison Wesley, 1981.
*
*
Section 12.4 A Hierarchy of Languages
Context-Sensitive Languages
A context-sensitive grammar has productions of the form xAz xyz, where A is a
nonterminal and x, y, z are strings of grammar symbols with y ≠ . The production S is
also allowed if S is the start symbol and it does not appear on the right side of any
production. A context-sensitive language has a context-sensitive grammar.
Example. The following grammar is context-sensitive.
S aTb | ab
aT aaTb | ac.
Quiz. What is the language of the grammar?
Answer: {ab} {an+1cbn+1 | n N}. This language is context-free. For example, it has the
grammar S aTb | ab, and T aTb | c.
Any context-free language is context sensitive.
Example. {anbncn | n ≥ 0} is context-sensitive but not context-free. Here is a csg.
S | abc | aTBc
T abC | aTBC
CB CX BX BC
bB bb.
Cc cc.
Quiz. Derive aaabbbccc.
Answer: S aTBc aaTBCBc aaabCBCBc aaabBCCBc aaabBCBCc
aaabBBCCc aaabbBCCc aaabbbCCc aaabbbCcc aaabbbccc.
*
*
Linear Bounded Automata (LBA)
A linear bounded automaton (LBA) is a Turing machine that may be nondeterministic and
that restricts the tape to the length of the input with two boundary cells that may not change.
Example. An LBA to check whether a natural number n is divisible by k ≠ 0.
Idea for a Solution: Use a 2-tape (or 2-head single tape) machine. For ease of explanation,
represent k by the nonempty string 1k and represent n by the string an. For example, if k = 3
and n = 9, the input is represented by,
111 a a a a a a a a a
If n = 0, which is represented by L, then halt. Otherwise, move both tape heads to the right k
places while there are a’s to read. Then leave the tape head for a’s in place and move the tape
head for k back to the left end and start the process over. Continue in this manner and enter
the halt state if both tape heads point to L.
Theorem: The context-sensitive languages are exactly the languages that are accepted by
linear bounded automata (LBA).
Example/Quiz. Find an LBA to accept {ap | p is prime}.
Idea for a Solution: Use the the divisibility algorithm in the previous example to implement
the following algorithm, where p ≥ 2.
k := 2;
while k < p do
if k divides p then stop (but don’t enter the halt state) else k := k + 1 fi
od;
Enter the halt state (accept).
*
*
Recursively Enumerable Languages
An unrestricted grammar has productions of the form s t, where s ≠ L. So any grammar is
an unrestricted grammar.
An unrestricted or recursively enumerable language has an unrestricted grammar.
Example. The following grammar is unrestricted. S TbC
Tb c
cC Sc | L.
This grammar is not context-sensitive, not context-free, and not regular.
But we can transform it into S Sc | L. So the language of the grammar is regular.
Theorem: The recursively enumerable languages are exactly the languages that can be
accepted by Turing machines. These languages can also be enumerated by Turing machines.
(That’s where “enumerable” comes from.)
Theorem: {an | ƒn(n) halts} is recursively enumerable and not context-sensitive.
Proof: (1) Set k := 0. (2) For each pair (n, m), where n + m = k, execute ƒn(n) for m steps to
see if it halts. If it halts, output an. (3) Increment k and go to (2).
Languages With No Grammars
Since there are a countable number of Turing machines, there are a countable number of
languages with grammars. But there are an uncountable number of languages over any finite
alphabet. So there are an uncountable number of languages don’t have a grammar.
Theorem: {an | ƒn is total} is not recursively enumerable. So it has no grammar.
Proof: If, BWOC, the language is recursively enumerable, then we can enumerate it by a
TM. So we can enumerate the total computable functions, which we can’t do. QED.
*
*
Section 12.5 Complexity Classes
A complexity class is a set of problems related by how much time or space algorithms take to
solve them. Complexity classes are usually defined for decision problems, which are
problems that ask a question with a yes/no answer. Here are some fundamental complexity
classes.
The class P
The set of problems that can be solved by deterministic algorithms with worst-case running
times of polynomial order.
The class NP
The set of problems for which solutions can be verified by deterministic algorithms with
worst-case running times of polynomial order. (The N stands for nondeterministic guess and
the P stands for polynomial time to verify that the guess is a solution.)
The class PSPACE
The set of problems that can be solved by deterministic algorithms where the worst-case
number of memory cells needed is of polynomial order.
Intractable Problems
The set of problems that are not in P.
NP-Completeness
Polynomially Reducible, NP-Competeness, CNF-Satisfiability, Cook’s Theorem, Algorithm
to find NP-complete problem, Restricting CNF-Satisfiability.
*
*
Example
The subset sum problem: given a positive integer A and a set B = {p1, ..., pn} of
positive integers, is there a subset of B whose sum is A?
Discussion: A simple deterministic algorithm to solve the problem would go through
all the subsets of B looking for a subset whose elements summed to A. Since there
are 2n subsets of B, this algorithm does not take polynomial time. But any subset can
be checked with at most n – 1 additions.Thus there is a O(n) algorithm to do the
checking. So the problem is in NP. The problem has been shown to be NP-complete.
