COCS5315
Test-1
7/30/2010
Name: (Print in CAPITAL or else
you lose FIVE points)
______________________________________________________
In
this test, the following notations are used:
1. L: The Simple language with 3 basic instructions.
2.
PC:
Partially Computable
3. PR: Primitive Recursive
4. RE: Recursively enumerable
5. A1: Alphabet of a Turing-Machine
6. A2: Alphabet of a Turing-Machine Tape
7. U1: A universal program in L that simulates L programs with one input.
8. U2: A universal program in L that simulates L programs with two inputs.
9. TM: Turing Machines (quadruples, two-way infinite tape, no designated final states)
10: NTM: Non-deterministic TM
11. CS: Context-Sensitive
12. l: The empty string
13. TOT: The set of all programs (with exactly one input) that computes a total function each.
14. K: {x | f (x,x) is defined}
15. K 0 : { <x,y> | f (x,y) is defined}
PART-A. Multiple Choices. (20 questions)
(60 points)
Answer 20 questions by making
exactly one choice by clearly writing down A,B,C,D,E, or F (in capital) next to each question
number and nowhere else. (If not
followed, you lose FIVE points)
First four questions are about the following set:
S = {x | g(l(<x, r(x)>)) is defined where g(x) is a PC function of one argument}
1. The problem of deciding whether or not this set S is Recursive is the same as deciding whether or not
a. ~S is Recursive
b. S is RE c. both. d. neither.
2. The problem of deciding whether or not g(x) is the same as g(r(x)) is the same as deciding whether or not
a. <l(x), r(x)> is the same as x
b. g(x) is Computable.
c. both. d. neither.
3. The problem of deciding whether or not the set K is many-one reducible to this set S is
the same as deciding whether or not
a. S is m-Complete.
b. S appears infinitely many times in the “Enumeration of All RE sets.”
c. Both. d. neither.
4.
The problem of deciding whether or not this set S is RE is the same as
deciding whether or not
a.
~S is RE
b.
S is Recursive.
c.
both.
d.
neither.
The
next four questions are about the following quadruple TM with twelve
quadruples.
Note that this TM has 5 states,
q1, q2, q3, q4 and q5, on the alphabet, {a,b}
and the only accepting
combination is (q5, B).
N1:
q1
B
R
q2
N2:
q2
a
R
q3
N3:
q2
b
b
q2
N4:
q2
B
B
q2
N5:
q3
b
R
q4
N6:
q3
a
a
q3
N7:
q3
B
B
q3
N8:
q4
b
R
q4
N9:
q4
a
R
q5
N10:
q4
B
B
q4
N11:
q5
a
a
q5
N12:
q5
b
R
q5
5.
The language accepted by this TM is:
a.
a
a*
b+
a*
b.
a+
b+ a b*
c.
neither.
6.
The function computed by this TM is
a.
partially computable
b.
Computable
c.
strictly computed
d.
all above.
e. two above.
Q5
B
B
Q5
7.
Suppose that above quadruple replaced the quadruple N11 above. In this
case, the new TM would
a.
compute the same function as before.
b.
accept the same language as before.
c.
both.
d.
neither.
8. Which string is accepted by this TM?
a. a a b a
b. a a a b b a
c. a b b
d. all above. e. two. f. none.
9.
Which pair is equivalent?
a.
All quadruple TM’s and all quintuple TM’s
b. All L
programs and all PC functions.
c.
All RE sets of single
numbers and all TM’s with one input string.
d. all
above.
e. two.
f.
none.
10.
Which is solvable?
a.
deciding whether or not HALT(x,y) is Computable.
b.
deciding whether or not an arbitrary PC function is
Computable.
c.
deciding whether or not an arbitrary PR function is
Computable.
d.
All above.
e.
Two.
f.
None.
11. Which is solvable?
a. deciding whether or not Bounded Minimalizations preserve PR functions
b. deciding whether or not Unbounded Minimalizations preserve Computable functions
c. both. d. neither.
12. Which is solvable?
a. the membership question of the set of all PC functions of one argument.
b. the membership question of the set of all PR functions of one argument.
c. the membership question of the set of all Computable functions of one argument.
d. all above. e. two above. f. none above.
13. Which is solvable?
a. Turing Machine Halting Problem.
b. TM State Problem.
c. deciding whether or not there exists a quintuple one-way infinite TM equivalent to an arbitrary
quadruple two-way infinite tape TM.
d. all above. e. two above. f. none above.
14. Which is Computable?
a. any function that can be obtained by Compositions and Bounded Minimalizations on the three basic
PR functions (Zero-functions, Successor-functions and Projection-functions)
b. deciding whether or not an integer is a multiple of another.
c. STP (x,y,t)
d. all above. e. two above. f. none above.
15.
Which are closed under
a. the family of all RE sets of single integers.
b. the family of all Recursive sets of single integers.
c. any family of sets that is closed under Intersection and also under Complementation.
d. all above. e. b and c above. f. none above.
16. Which preserves Computable functions?
a. Iterated Operations and Bounded Quantifications
b. Unbounded Minimalizations
c. both. d. neither.
17. Which preserves PC functions?
a. Iterated Operations and Unbounded Quantifications
b. Unbounded Minimalizations
c. Proper Minimalizations.
d. All above. e. two.
18. Which is RE?
a. the set of all programs (with exactly one input) that compute a total function each
b. the Complement of the set K and the Complement of the set K0
c. both. d. neither.
19. Which is Recursive?
a. the set of all Computable functions of exactly one argument.
b. an RE set whose complement is Recursive.
c. Both. d. Neither.
20. Which is Computable?
a. determining whether or not an arbitrary RE set is accepted by a TM.
b. SQ(X) = 0 if X is a square of an integer or else 1. (e.g., it is 0 if X=1, 4, 9, 16, 25, 36, ...)
c. both. d. neither.
21. Which is m-Complete?
a. {l(x*x) | f(x,x) is defined}
b. {<y, x> | f(y,x) is defined}
c. both. d. neither.
22. Which pair can be unifiable?
a.
P1 (V1, V2, F1(V2))
P1 (F2(V4), V4, F1(V4))
b.
P1 (C1,
F1(C2,V1))
P1
(V2, F1(V3,V2))
c.
Both.
d.
neither
23.
Which is unsolvable?
a.
deciding whether or not a non-empty RE set is the range of a PC
function.
b.
deciding whether or not a non-empty RE set is the domain of a PC
function.
c.
deciding whether or not a PC function can be computed by a Universal
program.
d.
all above.
e. two above.
f. none
above.
24.
Which is Computable?
a.
deciding whether or not a TM accepts an input string after entering a
given state.
b.
deciding whether or not a TM accepts an input string without
stopping.
c.
deciding whether or not an RE set is many-one reducible to the set
K0 .
d.
all above.
e. two above.
f. none
above.
PART-B.
Other
problems
(40 points)
Do four problems in this
PART-B.
A. Prove or disprove that there is a set that is not even RE when its complement is Recursive.
B. Prove or disprove that each of the following is PR
a. Factorial(Y,X) = (Y+1)*(Y+2)*(Y+3)*…*X if Y <= X
= 1 otherwise.
b. Divide (X1,X2) = whether or not X2 exactly divides X1 like 3 dividing 3 or 6 or 9 or 12 but not 4
Divide(12,3)=T
Divide(9,3) =T
Divide(6,3)=T
Divide(4,3)=F
C. Consider the following NTM with three states, Q1, Q2, and Q3 and five quadruples
on the alphabet {1}:
Q1 B R Q1
Q1 1 R Q2
Q1 1 1 Q2
Q2 1 1 Q3
Q3 B 1 Q3
Devise and clearly show another NTM whose TM State problem is equivalent to the Halting Problem of
this NTM.
D. Give a TM that accepts the following language:
L = {abc, ababc, abababc, ababababc, abababababc, … }
E. Show that the set K0 is many-one reducible to the set K.
F. Show that bounded minimalization preserves PR functions.
G.
Show that the
set TOT is not RE.
H.
Consider the following quadruple TM with four instructions on the
alphabet A={a,b}:
Q1
B
a
Q2
Q1
b
b
Q1
Q2
a
R
Q2
Q2
B
b
Q3
Clearly show an equivalent quintuple TM.