Prove whether the process is terminatable.

• If n=1, stop
• If n is even, set n = n/2
• Otherwise, set n = 3n + 1
• Repeat

There is a Turing machine U_tm called the universal Turing machine that, when run on(M, w), where is a Turing machine and w is a string, simulates M running on w.

You can:

• Double the contents of the string after M
• Replace III with U
• Remove UU
• Append U if the string ends in I

L e RE iff L is recognizable.

• RE is the set of all recognizable langauges.