Homework answers / question archive / COMP 330 - Fall 2020 - Assignment 5 Due: 11:59pm Nov 21 st

COMP 330 - Fall 2020 - Assignment 5 Due: 11:59pm Nov 21 st

Computer Science

Share With

---

COMP 330 - Fall 2020 - Assignment 5

Due: 11:59pm Nov 21 st.

General rules: In solving these questions you may consult books or other available notes, but you need to provide citations in that case. You can discuss high level ideas with each other, but each student must find and write her/his own solution. Copying solutions from any source, completely

 

or partially, allowing others to copy your work, will not be tolerated, and will be reported to the disciplinary office.

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

 

x is odd 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 < 10¹⁷, 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 conjecture^[1]. Suppose that HALT_TM were decidable, and R was a TM that was deciding HALT_TM. Construct an Turing Machine M based on R such that it 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}.