COMP 330  - Assignment 5

COMP 330  - Assignment 5

You should upload the pdf file (either typed, or a clear and readable scan) of your solution to
mycourses.
1. (5 Points) Prove that every Turing Recognizable language L satisfies L ≤m ATM.
2. (10 Points) Prove that for any two languages A and B, there exists a language J such that
A ≤T J and B ≤T J.
3. (10 Points) Prove that for any languages A, there exists a language J such that A ≤T J and
J 6≤T A.
4. (15 Points) Let Γ = {0, 1, t} be the tape alphabet for all Turing Machines in this problem.
Define the busy beaver function BB : N → N as follows. For each value of k, consider all k-state
Turing Machines that halt when started with a blank tape. Let BB(k) be the maximum number
of 1’s that remain on the tape among all of those machines. Prove that BB is not a computable
function.
5. (15 points) Let f : N → N be defined as
f(x) = ?
3x + 1 x is odd
x/2 x is even
For every natural number x, if you start with x and iterate f, you obtain a sequence
x, f(x), f(f(x)), f(f(f(x))), . . . .
Stop if you ever hit 1. For example, if x = 17, we get the sequence
17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
It has been checked by computers that if we start with any number x < 1017, we will eventually
hit 1 and terminate, but it is unknown whether this is true for every integer x. This is known
1
as Collatz’s conjecture1
. Let R be an oracle for HALTTM. Construct an oracle Turing Machine
MR such that MR accepts ε if Collatz’s conjecture is true (all numbers x hit 1 eventually), and
rejects it if Collatz’s conjecture is false (there is some x that does not hit 1).
6. (15 points) Let
X = {hM, wi|M is a single-tape TM that never modifies the w part of the tape, and it accepts w }.
Is X decidable? Prove your answer.
7. (15 Points) Prove that a language L is Turing Recognizable if and only if it can be expressed as
L = {x | ∃y such that hx, yi ∈ R}
where R is a decidable language. You need to prove that every language of this form is Turing
recognizable, and that every Turing recognizable language can be described as above for some
decidable language R.
8. (15 Points) Determine whether the following language is decidable or undecidable:
X = {hMi | On every input w, M eventually leaves the start state}.
1
It is interesting to view this in regard to Q4 in the previous assignment. It is fairly easy to construct a Turing
Machine M with 100 states that given 1x
as input, applies f recursively to this, and halts and accepts if we hit 1. Note
that M is a decider if and only if Collatz’s conjecture is true, which currently is unknown.
2