0
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ Welcome to Computer Science. What have you tried? Tell us more about what you know, and where you got stuck. $\endgroup$ – André Souza Lemos Jul 6 '15 at 20:41
  • 1
    $\begingroup$ How do you think one can check whether $i\in A$, I mean whether $M_i$ halt after 14 steps on input $x$. I suppose that $x$ is a fixed string. $\endgroup$ – babou Jul 6 '15 at 21:14
  • 1
    $\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out our reference questions, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Jul 7 '15 at 5:53
  • 1
    $\begingroup$ I opened a discussion on meta about this question: meta.cs.stackexchange.com/q/1048/755 $\endgroup$ – D.W. Jul 7 '15 at 18:11
3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ You might consider not to encourage undesirable posting behaviour in the future. Up to you -- I respect whatever call you decide to make. (Not intended as a criticism...) $\endgroup$ – D.W. Jul 7 '15 at 18:12
  • $\begingroup$ Note that you can use math formatting here. $\endgroup$ – Gilles 'SO- stop being evil' Jul 7 '15 at 19:51
  • 1
    $\begingroup$ @D.W., complete_idiot: note that claiming that this answer “encourage[s] undesirable posting behaviour” is a personal claim, not a site policy. Some people consider answering lazy questions a waste of time, but if you want to do it, that's your choice. $\endgroup$ – Gilles 'SO- stop being evil' Jul 8 '15 at 12:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.