# HW2 Answer

Qun Lou [e-mail]

## 1. 3x+1

Suppose A_tm is decided by H, thus, L(H) = A_tm = { <M,w>| M is a TM and M accepts w}. Construct a new turing machine F on input x as the function f(x): if x is odd, calculate x = 3x+1; if x is even, calculate x = x/2; if x = 1, accept. Now we can construct the abstract turing mahcine M_3 on input x.

M_3:

1. F,x as above
2. Run F on x; reject if F reject x;
3. If F(x) is accepted, Run F on x = x + 1; (go back to step 2.)

Knowing that we can easily construct another turing machine H' to solve HALT problem via using H ( if a TM M' halts on input w, accept; otherwise reject), we will run the HALT machine H' on M_3:

if H' reject M_3, which means M_3 will loop forever (as many as ‎א‎ ), the 3x+1 problem proved. Otherwise, M_3 will **halt** on some F(x), which means **NOT** all positive string will end in 1.

## 2. BB

Suppose there is a turing machine M_bb can compute (always halt) on input k for BB(k) problem. Then let's show that HALT $\leq_P$ BB_tm.
We can construct M_halt to decide halt problem for k-state TMs M_halt_blank with blank input:
1. construct a (k+c)-state TM M_k' to simulate M_k on input w, where c is constant; and the extra c states can be used to keep a 1s-array after the tape of M_k by shift the 1s-array and add a 1 after each step.
2. compare the number of 1s in M_k'(M,w) with BB(k+c), knowing that BB(k+c) is the maximum states number for TMs which will halt; but our M_k' will never halt iff the <M,w> not halt. And the number of 1s in M_k' tape will exceed the number of BB(k+c), and in such circumstance it is non-HALT for <M,w>.

The k is not important because TM has finite states. So far we have shown that BBtm $\leq_P$ HALT (with blank tape input); and it's easy to solve HALT with our M_halt_blank on <M,w> with the new TM R:
1. original tape is blank
2. write w on the previous blank tape
3. run M on w

now in order to solve HALT, we just need to run M_halt_blank<R<M,w>,blank>.
Since HALT is not computable as we know, the halt_blank and thus BB is also not computable.

## 3. LBA
Here is an example, the w_i means words in decided language and L_i means all LBAs. If L_i accept w_j, Matirx Mij = 1, otherwise 0.

    w1 w2 w3 w4 ...
L1  0  1  1  0
L2  1  1  0  1
L3  1  1  0  0
L4  1  0  1  1
..

Now we construct a new langague Lan where the word w_i is in Lan iff the LBA L_i does not accept w_i. In this case, it's {1 0 1 0} (the re-complement of diagno). We reach $f^{-}$(Lan)=∅ by definition. Thus, there exists a decidable language that is not accepted by any linear-bounded Turing machine.

## 4. R & RE
Knowing L_non_halt = {<M,w>\| M is a TM and it doesn't halt on string w} is not RE.
(a) show reduction in L_non_halt and L1. With a TM T_l1 we get T_nh:
1. run M on w

(b) first, L2 is at least RE. We can verify if <M> is in L1 by this TM :
1. generate a new input string s
2. run M on s, if accept, counter +=1; else goto 1.
3. if counter >=218, accept; else goto 1.

then, L2 is not decidable. We can use the TM M_L2 to solve HALT<M,w>:
1. Simulate to run M on w;
2. If M halts on w,accept;
3. Otherwise, reject

If M halts on w, M_L2 will accept any input, thus, L(M_L2) > 218; otherwise, L(M_L2) = 0; so HALT solved. Thus, L2 is not decidable.

## 5. bonus