CSE 6321: Assignment 1
Due: 11:59pm Sunday, February 7th
General rules: If you consult any books or other sources, you must provide citations for your sources. If you collaborate with other students on any of the problems, you must state it clearly at the beginning of your so- lution to the problem (give name(s) of the collaborator(s)).
Your solutions should be submitted on Car- men in pdf format (either typed or easy to read handwritten & scanned).
Write clean and succinctly; solutions will be graded based on correctness not based on their volume.
1. (5 Points) Prove that every recognizable language L satisfies L ≤m AT M .
2. (10 Points) Prove that for every two languages A and B, there is a language J such that A ≤T J
and B ≤T J. (Note that A, B, and J do not have to be over the same alphabet).
3. (10 points) Suppose that
T ⊆ {⟨M⟩|M is a Turing machine which halts on all inputs (i.e. is a decider)}
is a recognizable language. Prove that there exists a Turing machine D, which halts for every input, and such that for every ⟨M⟩ ∈ T, L(M) ̸= L(D). Namely, no Turing machine M, with ⟨M⟩ ∈ T, decides the same language as D.
4. (10 points) Let M1 and M2 be two Turing machines. Consider the following Turing machine D: D on input w:
1. Run M1 on input w. If M1(w) halts and accepts, then accept 2. Run M2 on input w. If M2(w) halts and accepts, then accept
What is the language of this Turing Machine? Justify your answer. 1
5. (15 Points) Let E be an enumerator for a language L with the extra property that it will print the words in a non-decreasing order of word-lengths. That is it will never print a word w before a shorter word u. For example if w = 0010 and u = 101 are both in L, then E will never print u after it has printed w.
Prove that L is decidable.
6. (10 points) Is the following language decidable.
L = {⟨M⟩ | M = ({1,2,…,50},{0,1},{0,1,b},δ, 1 , 2 , 3 ) is a decider},
qstart qaccept qreject
where a Turing Machine is called a decider if it halts on every input. Note that the only free
variable in the description of M in L’s definition is the transition function δ.
7. (15 Points) We observed in class that the following language is recognizable. Prove that it is in
fact decidable.
L = {⟨p(x)⟩ | p(x) is a univariate polynomial with integer coefficients that has an integer root}.
8. (15 Points) Prove that a language L is recognizable if and only if there exists a decidable language R such that
L = {x | ∃y such that ⟨x, y⟩ ∈ R}.
QΣΓ
2