There is not a clear answer in literature on the question: Can total computable functions be computable enumerated?, i.e., is a set of encodings of total computable functions computably enumerable (c.e.)? On the shaking ground, I am tossing an algorithm that encodes all total recursive functions and the set of codes is c.e.. Is the algorithm a flaw? your views will help to answer it. Thank you for your review and comments in advance.

To reach our goal, we use Kleene's T predicate (Pages 288 and 330 of Kleene's text book [1]. The notations below mostly come from Shoenfield's text book [2]). Let Kleene’s T predicate:

$$T_{k} (e, x_{1}, x_{2}, …, x_{k}, y)$$

be rewritten as

$$T (e, \vec{x} , y)$$

e, the code of a program p, expressing a partial recursive function {e}.
$\vec{x} ≡ (x_{1}, x_{2}, …, x_{k})$, k-tuple, input to p, here k0.
y, the code of the computation after n steps when p is applied to $\vec{x}$.

The rewrite is intended to say that T includes the enumeration of all partial recursive functions, i.e.,

$$T = \cup_{k>=0} T_{k}$$

Further we rewrite T as:

$$T’ (e, \vec{x} , n, v)$$

v = U (μy T( e, $\vec{x}$, y)), the output {e}($\vec{x}$) of the computation if it halts within steps n. Otherwise
v = ‘still-running’, a special symbol other than natural numbers.

The rewrite says that given a n, a tuple (e, $\vec{x}$, y) in T is expanded to have n more tuples in T’: (e, $\vec{x}$, 0, $v_{0}$), (e, $\vec{x}$, 1, $v_{1}$), …, (e, $\vec{x}$, n, $v_{n}$), here $v_{i}$, for each i between 0 and n, is v in correspondence to i steps.

Recall that we need to use Cantor’s diagonal method when we generate Kleene’s T predicate, a relation, in order to reach every property of partial recursive functions. Therefore for a n in a tuple of T’, there is another number m, the total steps run so far in enumerating a finite set of programs including p, after p has run n steps. Therefore, we equivalently rewrite T’ as:

$$T’ (e, \vec{x}, m, n, v)$$

From Kleene’s T predicate, we know that T’ is recursive, i.e., given any tuple (e, $\vec{x}$, m, n, v), we can decide if it is in T’. Further we know that T’ approaches the properties of all partial recursive functions when m approaches infinite. Therefore we say that

(1) There is a language that is recursive and at the same time it is as effectively powerful as a programming language.

Now let’s re-shovel the content in T’ to show that there exists an encoding of all total recursive functions such that the encoding is c.e.. Given a m and an e, consider the tuples in T’ that have values not equal to ‘still-running’, and rewrite T’ as:

$$T’’ (<e, m>, \{(\vec{x}, v) | \{e\}(\vec{x})=v \wedge v\neq‘still-running’\})$$

Note that semantically T’’ has no difference from T’. Clearly, each tuple, having <e, m> as a code, is a function with finite properties, i.e., the set of tuples ($\vec{x}$, v) that are enumerated within the total m steps against {e}. Since it has finite properties, it can be represented by a total recursive function (See Wagner's Theorem 2.4 of [3]). Therefore, T’’ is a collection of total recursive functions, each of which is precisely coded as <e, m> and precisely defined by its properties, the set of tuples ($\vec{x}$, v).

Since T includes the properties of all partial, including total, recursive functions, we imagine that T’’ would include all the total recursive functions provided that we had infinite time and space. In reality, however, we can always decisively answer the following question: Given an arbitrary natural number j, is j a code <e, m> for a total recursive function? To this end, we have proved that

(2) There exists an encoding, the set of codes <e, m>, for all total recursive functions, such that the set is c.e..

Claiming that an encoding of total recursive function is c.e. doesn’t resolve the halting problem. Given an e, can we find if {e} is recursive by searching through T’’? The answer is no, since the function with <e, m> has finite properties while {e} has infinite properties.

The predicate T’’ demonstrates an algorithm that pushes all partial recursive functions to the outskirt of computation. It shows that we don’t have to deal with partial recursive functions for our software development. Instead, it is sufficient to use a recursive language alone for the same purpose.

Before ending the article, we summarize two properties of T’’:

(3) The function encoded by <e, m> is included in the function encoded by <e, m + 1>
(4) The function encoded by <e, m> converges with {e} when m is approaching infinite.

(4) is a reiteration of (1).

[1] S. C. Kleene. “Introduction to Metamathematics”. Ishi Press International, 1952.
[2] J. R. Shoenfield. “Recursion Theory (Lecture Notes in Logic)”, Springer-Verlag, 1993.
[3] E. G. Wagner. “Uniformly Reflexive Structures: On the Nature of Godelizations and Relative Computability”. Trans. Amer. Math. Soc., Vol. 144, pp. 1-42, 1969.

  • 8
    $\begingroup$ «There is not a clear answer in literature on the question»... This is a standard exercise on the subject! $\endgroup$ – Mariano Suárez-Álvarez Apr 18 '12 at 5:04

If you are asking:

Is there a total, recursive function $\psi$ where $\psi(n) = \psi_{n}$ is the $n$th total, recursive function?

Then the answer is no.

Proof: Suppose such a function existed. Construct a new function $\varphi$ as follows.

$$\varphi(x) = \psi_{x}(x) + 1$$

where $\psi_{x}(x)$ is the $x$th total, recursive function evaluated at $x$. Clearly, $\varphi(x)$ is both recursive and total. Let $e$ code for it, so that $\psi_{e} = \varphi$. Then

$$\varphi(e) = \psi_{e}(e) + 1 = \varphi(e) + 1$$

which is absurd.

| cite | improve this answer | |
  • $\begingroup$ To me, $$\varphi(x) = \psi{x}(x) + 1$$ is a definition-by-case with infinite cases $\psi{0}$, \psi_{1}, \psi_{2}, .... Then $$\varphi(x) would not be recursive any more. $\endgroup$ – u never know Apr 18 '12 at 11:48
  • $\begingroup$ To me, $\varphi(x) = \psi_{x}(x) + 1$ is a definition-by-case with infinite cases $\psi{0}$, $\psi{1}$, $\psi{2}$, .... Then $\varphi$ would not be recursive any more. $\endgroup$ – u never know Apr 18 '12 at 12:00
  • 2
    $\begingroup$ No, it's just definition by composition. Think about it like this: I know I have this recursive algorithm to produce $\psi_{x}$. I'm merely adding two extra instruction: (1) evaluate at $x$. (2) add $1$. $\endgroup$ – Elchanan Solomon Apr 18 '12 at 13:37
  • $\begingroup$ A comopsition function takes only finite number of parameters (page 219 of Kleene's text book [1]) $\endgroup$ – u never know Apr 18 '12 at 16:12
  • 1
    $\begingroup$ I'm not sure what you are asking. You can prove $x \to \psi_{x}(x)$ is recursive using the $S^{m}_{n}$ function... $\endgroup$ – Elchanan Solomon Apr 18 '12 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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