The Gateway to Computer Science Excellence
0 votes

$f(x)=\left\{\begin{matrix}3x+1 & \text{for odd}\: x& \\ \dfrac{x}{2} & \text{for even}\: x & \end{matrix}\right.$

for any natural number $x$. If you start with an integer $x$ and iterate $f$, you obtain a sequence, $x, f(x), f(f(x)), \dots$  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 $ATM$ were decidable by a $TM\: H$. Use $H$ to describe a $TM$ that is guaranteed to state the answer to the $3x + 1$ problem.
in Theory of Computation by Veteran (58.9k points) | 22 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,296 answers
104,975 users