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

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