5. (15 points) Let f : NN be defined as 3a +1 f(x) = 1/2 I is odd I is even %3D For every natural number a, if you start with z and iterate f, you obtain a sequence a, f(x), f(f(r)), fS(=))),.... Stop if you ever hit 1. For example, if r D 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 a < 1017, we will eventually hit 1 and terminate, but it is unknown whether this is true for every integer r. This is known as Collatz's conjecture'. Let R be an oracle for HALTTM. Construct an oracle Turing Machine MR such that MR accepts e if Collatz's conjecture is true (all numbers a hit 1 eventually), and rejects it if Collatz's conjecture is false (there is some r that does not hit 1).