search
Log In
0 votes
85 views
Let

$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 85 views

Please log in or register to answer this question.

Related questions

0 votes
1 answer
1
0 votes
0 answers
2
135 views
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 135 views
1 vote
0 answers
3
111 views
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 111 views
0 votes
0 answers
4
58 views
Rice's theorem. Let $P$ be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turing machine's language has property $P$ is undecidable. In more formal terms, let $P$ be a language consisting of Turing ... any $TMs$. Prove that $P$ is an undecidable language. Show that both conditions are necessary for proving that $P$ is undecidable.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 58 views
...