COSC5315
TEST-1
3/3/2008
Keys Used:
1-5:
FBCBA
6-10:
CFCDB
11-15:
ECDBB
16-20:
BCCDB
21-22:
CE
Name: (Please Print, else you lose 5 points)_______________________________________________________
Notations:
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. l: The empty string
PART-A. Multiple Choices.
(66 points)
For each question in this PART-A, clearly write down A,B,C,D,E,F or G(in capital) next to each question
number and nowhere else.
First five questions are about the
following set:
S = {x | g (<r(x), l(x)>) is defined where g(x) is a PC function of one argument}
1. The problem of deciding whether or not the set S is RE is the same as deciding whether or not
a. ~S is RE
b. ~S is Recursive
c. g(x) is Computable
d. all above e. two above. f. none above.
2. The problem of deciding whether or not the set S is many-one reducible to the set K is the same as deciding whether or not
a. the set S is m-Complete
b. the set S is many-one reducible to an arbitrary m-Complete set.
c. Both. d. neither.
3. The problem of deciding whether or not the set S is Recursive is the same as deciding whether or not
a. ~S is Recursive
b. ~S is RE c. both. d. neither.
4. The problem of deciding whether or not g(x) is total is the same as deciding whether or not
a. S is Recursive.
b. It is Computable. c. both. d. neither.
5. 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.
********************END-OF-SET REFERENCE**********************
6. Which is solvable?
a. deciding whether or not Bounded Minimalizations preserve Computable functions
b. deciding whether or not Unbounded Minimalizations preserve PR functions
c. both. d. neither.
7. Which is solvable?
a. the membership question of the set K.
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.
8. 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.
9. Which is Computable?
a. any function that can be obtained by Compositions and Proper 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.
10. Which is minimally needed to compute the next snapshot of a program?
a. the current snapshot
b. the current snapshot and the program (under execution)
c. the current snapshot, the program (under execution) and the statement currently being executed.
d. none above.
11.
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. two above. f. none above.
12. Which preserves Computable functions?
a. Iterated Operations and Bounded Quantifications
b. Proper Minimalizations
c. both. d. neither.
13. Which preserves PC functions?
a. Iterated Operations and Unbounded Quantifications
b. Unbounded Minimalizations
c. Proper Minimalizations. d. All. e. two.
14. Which is RE?
a. the set of all programs (with exactly one input) that compute a total function each
b. the set K and the set K0
c. both. d. neither.
15. Which is Recursive?
a. the set of all Computable functions of exactly one argument.
b. an RE set whose complement is RE.
c. Both. d. Neither.
16. Which is Computable?
a. determining whether or not an arbitrary RE set is Recursive.
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.
17. Which is m-Complete?
a. {l(x) | f(x,x) is defined}
b. {<y, x> | f(x,y) is defined}
c. both. d. neither.
Next four questions are about the following DTMD with seven quads and the alphabet = {a,b}:
N1: Q1 B R Q2
N2: Q2 a R Q3
N3: Q2 b R Q2
N4: Q2 B B Q2 // infinite loop
N5: Q3 a R Q3
N6: Q3 b R Q2
N7: Q3 B b Q4 // accepting combination
18. Which language is accepted by this TM?
a. {a+ b+ a}
b. {a* b* a}
c. {(a + b}* a}
d. {(a + b)+ a }
e. none
19. The function computed by this TM
a. is Computable.
b. turns the input “abb” into the output “abbb”
c. both. d. neither.
20. Q3 B a Q4
Suppose that above quadruple replaced the quadruple# N7 above.
In this case, the resulting new TM would
a. compute the same function as before.
b. accept the same language as before.
c. Both. d. neither.
21. This TM computes
a. a PC function strictly.
b. a Computable function non-strictly.
c. a PC function non-strictly.
d. All above. e. two above. f. none above.
22. Which is Solvable?
a. determining whether or not an arbitrary TM accepts an arbitrary input string.
b. determining whether or not an arbitrary TM is truly deterministic.
c. determining whether or not the family of all TM’s and the family of all quintuple TM’s with designated
final states are equivalent.
d. all above. e. two above. f. none above.
PART-B. Other Problems.
(34 points)
Do three problems in this
PART-B.
A. Prove or disprove that there is a set that is not even RE when its complement is RE.
B. Prove or disprove that each of the following is Computable:
a. Factorial(Y,X) = Y*(Y+1)*(Y+2)*…*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 TM, M, with three states and six quadruples:
Q1 B R Q1
Q1 1 R Q1
Q1 2 R Q2
Q2 2 1 Q3
Q2 1 1 Q2
Q3 B B Q3
Devise and clearly show another TM whose TM State problem is equivalent to the Halting Problem of
this TM.
D. Give a TM that accepts the following language:
L = { l, ab, abab, ababab, abababab, ababababab, … }
E. Show that any RE set is m-Complete if the set K0 is many-one reducible to this set.
F. Show that bounded minimalization preserves Computable functions.