Question

Let
$f\left(x\right)=\left\{\begin{array}{l}3x+1foroddx\\ x/2forevenx\end{array}\right.$

for any natural number x . If you start with an integer x and iterate f , you obtain a sequence, x,$f\left(x\right),f\left(f\left(x\right)\right),......$Stop if you ever hit 1. For example, if x=17 , you get the sequence 17,52,26,13,40,20,10,5,16,8,4,2,1 .Extensive computer tests have shown that every starting point between 1 and a large positive integer gives a sequence that ends in 1 . But the question of whether all positive starting points end up at 1 is unsolved; it is called the 3x+1 problem. Suppose that $A_{TM}$were decidable by a TM H. Use H to describe a TM that is guaranteed to state the answer to the 3x+1 problem.

Short answer

We have constructed a TM that is describe by H.

Step-by-step solution

Construction of Turing Machine Mquery

Let’s design a Turing Machine $M_{query}$which takes x as input and accepts only if iterating f starts from x lets to obtain 1 and looping infinite.

So we construct$M_{query}$ as follows:

$M_{query}$=on input

• If x=1

Accepts x

• If x=odd number

Update x=3x+1

• If x=even number

Update x=x/2

• Repeat again from starting

Now create Turing Machine$M_{loop}$ that will iterate for all positive number.$M_{loop}$ will search a value of x such that f starting from x up to 1 and will accept it if fund such value of x. Now we will use another TM H which helps us to instead of simulating$M_{query}$ on x, because if we simulate$M_{loop}$ to $M_{query}$, there can be chance that we may or may not meet to counter example of x. Due to this reason we use H for$M_{loop}$ to check if $M_{query}$accept x by making it pass to H.

Construct Turing Machine Mloop

Construct $M_{loop}$as follows:

$M_{loop}$=on input

• Ignore w
• For y=1,2,....
• Run H on
• If H rejects

Then $M_{loop}$will accept

Else

Continue the loop

Now solve for 3x+1. To do this we need to know if$M_{loop}$ is able to find counter-example or not. So here also we will use H to check if$M_{loop}$ find counter-example or not.

• Ignore w
• Run H on
• If H accept

Then print “We found counter-example of 3x+1”