Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If I understand a set to be recursively enumerable, if it is a projection of a recursive set, meaning it is a set of the form $\left\{ (x_1, \dots,x_{l-1}) |\exists x_l: (x_1, \dots,x_{l-1},x_l) \in A \right\}$, where $A$ is a recursive set. How can I then prove, that I could weaken this definition to: $A \subseteq \mathbb{N}^l$ is recursively enumerable if and only if it is the projection of primitive recursive set ?

share|cite|improve this question
up vote 2 down vote accepted

The details depend on how you approach the subject. But for example if we do it through Turing machines, we can use the fact that the following predicate, traditionally called the $T$-predicate, is primitive recursive. Here $$T(e,z,x_1,x_2,\dots, x_n)$$ holds if $e$ is the index of a Turing machine, and $z$ is the index of a computation, with final result $0$, (for *true," people in logic sometimes make strange choices), when machine $e$ is given input $(x_1,x_2,\dots,x_n)$.

The point is that you can tell primitive recursively whether a number encodes a sequence of states/tape contents/head positions that is a terminating computation using machine $e$ and given input.

Things do not change very much if you approach the question through $\mu$-recursion.

share|cite|improve this answer
You lost me a bit here...Can I think of a Turing machine also as a simple FOR-type program (that has just bounded loops and basic arithmetic) in your answer ? (If yes, what would be the index and the index of computation ?) And of which set should I then take the projection ? Because I yet don't know anything about Turing machines...Or what could be a different approach ? (So sorry for not providing these details earlier.) – temo May 1 '11 at 6:10
@temo: Sorry, can't do much in 600 characters. Look up (Wikipedia is OK) Turing machine, godel number. Index of a machine is just a number assigned to it that identifies it, a Turing machine is really a program. A terminating computation is can be described if we describe what was in memory, where we were in the program, at every step from beginning to end. So it can be thought of as a finite string of integers, which can be coded as a single integer, the index of the computation. – André Nicolas May 1 '11 at 12:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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