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 ?
Weaker definition of recursively enumerable sets
1 Answers
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.
-
0You 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.) – 2011-05-01
-
0@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. – 2011-05-01