Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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?

Asked By : CyKon

Answered By : Computer

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.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback