2
$\begingroup$

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 ?

1 Answers 1

2

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.

  • 0
    @temo: Sorry, can't do much in 600 characters. Look up (Wikipedia is OK) Turing machine, godel number. Inde$x$ 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 inde$x$ of the computation.2011-05-01