Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Set of Turing machines that halt after exactly 14 steps

, ,
Problem Detail:

Let $M_i$ be the Turing machine with Gödel number $i$. Let $$A = \{i \mid M_i \text{ with input $$x$$ halts after exactly 14 steps}\}$$ Is the set $A$ recursive?

I assume you mean $M_i$ is a TM which is determined by Gödel Number $i$ such that from $i$ one can always construct $M_i$ in finite time and that $A = \{i \mid M_i \text{ halts after exactly 14 steps on $$x$$ as input, where$i$is a G}\ddot{o}\text{del Number}\}$ where $x$ is constant.

$A$ is recursive if there exists a TM for $A$ that always halts.

Such a TM can can be constructed as follows:

1. If $i$ is a Gödel Number construct $M_i$, else $i \notin A$, halt.
2. Run $M_i$ on the constant $x$ for 14 steps, if it halts after exactly 14 steps then $i \in A$, else $i \notin A$, halt.

Both 1 & 2 always halt which means that the TM always halts. So $A$ is recursive.

Question Source : http://cs.stackexchange.com/questions/44194

3.2K people like this