Sale!

# COMP 330 – Assignment 5 solution

\$30.00

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.

Category:

## Description

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 }.