Return to Answer

In Recursive predicates and quantifiers (Trans. Amer. Math. Soc. 53 (1943), 41-73) Kleene gives a description of general recursive functions acording to Herbrand and Gödel, as understood before the paper "standardized" the subject.

According to the definition given therein (I am skipping over some details involving given, auxiliary, and principal function symbols), a sytem of equations $\mathcal{S}$ in function symbols $f_1, \ldots, f_n$, each with a given arity, is a list of equations of the form $L = R$, where $L$ and $R$ are expressions obtained from $0$, successor, variables, and the function symbols $f_i$. There is no restriction on how the function symbols appear, other than their arities being respected. There are basic substitution rules for manipulating expressions, see the paper.

It's not at all clear how to deal with a system of arbitrary equations, which may even be contradictory. It is not so surprising that the definition of general recursive functions was considered unsatisfactory at the time.

Kleene gives an example showing hot to express the minimization operator $\mu y . (r(x_1, \ldots, x_n, y) = 0)$ in this way (I write $\vec{x}$ for $x_1, \ldots, x_n$ and $n^{+}$ for successor of $n$): \begin{align*} \sigma(0, \vec{x}, y) &= y\\ \sigma(z^{+}, \vec{x}, y) &= \sigma(r(\vec{x}, y^{+}), \vec{x}, y^{+}) \\ \phi(\vec{x}) &= \sigma(\rho(\vec{x},0), \vec{x}, 0) \end{align*} This is a system of equations in $\sigma$ and $\phi$, for a given $r$. We then set $\mu y. (r(\vec{x}, y) = 0) \mathrel{{:}{=}} \phi(\vec{x})$.

Kleene goes on to prove that one can reduce every system $\mathcal{S}$ to one involving primitive recursive functions (which he defines in the usual way) and the minimization operator $\mu$. Apparently after this paper everyone forgot about the original unruly definition in terms of systems of arbitrary equations.

In Recursive predicates and quantifiers (Trans. Amer. Math. Soc. 53 (1943), 41-73) Kleene gives a description of general recursive functions acording to Herbrand and Gödel, as understood before the paper "standardized" the subject.

According to the definition given therein (I am skipping over some details involving given, auxiliary, and principal function symbols), a sytem of equations $\mathcal{S}$ in function symbols $f_1, \ldots, f_n$, each with a given arity, is a list of equations of the form $L = R$, where $L$ and $R$ are expressions obtained from $0$, successor, variables, and the function symbols $f_i$. There is no restriction on how the function symbols appear, other than their arities being respected. There are basic substitution rules for manipulating expressions, see the paper.

It's not at all clear how to deal with a system of arbitrary equations. It is not so surprising that the definition of general recursive functions was considered unsatisfactory at the time.

Kleene gives an example showing hot to express the minimization operator $\mu y . (r(x_1, \ldots, x_n, y) = 0)$ in this way (I write $\vec{x}$ for $x_1, \ldots, x_n$ and $n^{+}$ for successor of $n$): \begin{align*} \sigma(0, \vec{x}, y) &= y\\ \sigma(z^{+}, \vec{x}, y) &= \sigma(r(\vec{x}, y^{+}), \vec{x}, y^{+}) \\ \phi(\vec{x}) &= \sigma(\rho(\vec{x},0), \vec{x}, 0) \end{align*} This is a system of equations in $\sigma$ and $\phi$, for a given $r$. We then set $\mu y. (r(\vec{x}, y) = 0) \mathrel{{:}{=}} \phi(\vec{x})$.

Kleene goes on to prove that one can reduce every system $\mathcal{S}$ to one involving primitive recursive functions (which he defines in the usual way) and the minimization operator $\mu$. Apparently after this paper everyone forgot about the original unruly definition in terms of systems of arbitrary equations.

In Recursive predicates and quantifiers (Trans. Amer. Math. Soc. 53 (1943), 41-73) Kleene gives a description of general recursive functions acording to Herbrand and Gödel, as understood before the paper "standardized" the subject.

According to the definition given therein (I am skipping over some details involving given, auxiliary, and principal function symbols), a sytem of equations $\mathcal{S}$ in function symbols $f_1, \ldots, f_n$, each with a given arity, is a list of equations of the form $L = R$, where $L$ and $R$ are expressions obtained from $0$, successor, variables, and the function symbols $f_i$. There is no restriction on how the function symbols appear, other than their arities being respected. There are basic rules substitution rules for manipulating expressions, see the paper.

It's not at all clear how to deal with a system of arbitrary equations, which may even be contradictory. It is not so surprising that the definition of general recursive functions was considered unsatisfactory at the time.

Kleene gives an example showing hot to express the minimization operator $\mu y . (r(x_1, \ldots, x_n, y) = 0)$ in this way (I write $\vec{x}$ for $x_1, \ldots, x_n$ and $n^{+}$ for successor of $n$): \begin{align*} \sigma(0, \vec{x}, y) &= y\\ \sigma(z^{+}, \vec{x}, y) &= \sigma(r(\vec{x}, y^{+}), \vec{x}, y^{+}) \\ \phi(\vec{x}) &= \sigma(\rho(\vec{x},0), \vec{x}, 0) \end{align*} This is a system of equations in $\sigma$ and $\phi$, for a given $r$. We then set $\mu y. (r(\vec{x}, y) = 0) \mathrel{{:}{=}} \phi(\vec{x})$.

Kleene goes on to prove that one can reduce every system $\mathcal{S}$ to one involving primitive recursive functions (which he defines in the usual way) and the minimization operator $\mu$. Apparently after this paper everyone forgot about the original unruly definition in terms of systems of arbitrary equations.

In Recursive predicates and quantifiers (Trans. Amer. Math. Soc. 53 (1943), 41-73) Kleene gives a description of general recursive functions acording to Herbrand and Gödel, as understood before the paper "standardized" the subject.

According to the definition given therein (I am skipping over some details involving given, auxiliary, and principal function symbols), a sytem of equations $\mathcal{S}$ in function symbols $f_1, \ldots, f_n$, each with a given arity, is a list of equations of the form $L = R$, where $L$ and $R$ are expressions obtained from $0$, successor, variables, and the function symbols $f_i$. There is no restriction on how the function symbols appear, other than their arities being respected. There are basic substitution rules for manipulating expressions, see the paper.

It's not at all clear how to deal with a system of arbitrary equations, which may even be contradictory. It is not so surprising that the definition of general recursive functions was considered unsatisfactory at the time.

Kleene gives an example showing hot to express the minimization operator $\mu y . (r(x_1, \ldots, x_n, y) = 0)$ in this way (I write $\vec{x}$ for $x_1, \ldots, x_n$ and $n^{+}$ for successor of $n$): \begin{align*} \sigma(0, \vec{x}, y) &= y\\ \sigma(z^{+}, \vec{x}, y) &= \sigma(r(\vec{x}, y^{+}), \vec{x}, y^{+}) \\ \phi(\vec{x}) &= \sigma(\rho(\vec{x},0), \vec{x}, 0) \end{align*} This is a system of equations in $\sigma$ and $\phi$, for a given $r$. We then set $\mu y. (r(\vec{x}, y) = 0) \mathrel{{:}{=}} \phi(\vec{x})$.

Kleene goes on to prove that one can reduce every system $\mathcal{S}$ to one involving primitive recursive functions (which he defines in the usual way) and the minimization operator $\mu$. Apparently after this paper everyone forgot about the original unruly definition in terms of systems of arbitrary equations.

In Recursive predicates and quantifiers (Trans. Amer. Math. Soc. 53 (1943), 41-73) Kleene gives a description of general recursive functions, as understood before the paper "standardized" the subject.

According to the definition given therein (I am skipping over some details involving given, auxiliary, and principal function symbols), a sytem of equations $\mathcal{S}$ in function symbols $f_1, \ldots, f_n$, each with a given arity, is a list of equations of the form $L = R$, where $L$ and $R$ are expressions obtained from $0$, successor, variables, and the function symbols $f_i$. There is on restriction on how the function symbols appear, other than their arities being respected.

We have basic rules of deduction for reasoning about systems of equations, see the paper. They are just obvious substitution rules. It's easy to imagine that it's not so clear how to deal with a system of arbitrary equations, which is presumably why the definition was not considered satisfactory.

Kleene gives an example showing hot to express the minimization operator $\mu y . (r(x_1, \ldots, x_n, y) = 0)$ in this way (I write $\vec{x}$ for $x_1, \ldots, x_n$ and $n^{+}$ for successor of $n$): \begin{align*} \sigma(0, \vec{x}, y) &= y\\ \sigma(z^{+}, \vec{x}, y) &= \sigma(r(\vec{x}, y^{+}), \vec{x}, y^{+}) \\ \phi(\vec{x}) &= \sigma(\rho(\vec{x},0), \vec{x}, 0) \end{align*} This is a system of equations in $\sigma$ and $\phi$, for a given $r$. We then set $\mu y. (r(\vec{x}, y) = 0) \mathrel{{:}{=}} \phi(\vec{x})$.

Kleene goes on to prove that one can reduce every system $\mathcal{S}$ to one involving primitive recursive functions (which he defines in the usual way) and the minimization operator $\mu$. Apparently after this paper everyone forgot about the original unruly definition in terms of systems of arbitrary equations.

In Recursive predicates and quantifiers (Trans. Amer. Math. Soc. 53 (1943), 41-73) Kleene gives a description of general recursive functions acording to Herbrand and Gödel, as understood before the paper "standardized" the subject.

According to the definition given therein (I am skipping over some details involving given, auxiliary, and principal function symbols), a sytem of equations $\mathcal{S}$ in function symbols $f_1, \ldots, f_n$, each with a given arity, is a list of equations of the form $L = R$, where $L$ and $R$ are expressions obtained from $0$, successor, variables, and the function symbols $f_i$. There is no restriction on how the function symbols appear, other than their arities being respected. There are basic rules substitution rules for manipulating expressions, see the paper. 

It's not at all clear how to deal with a system of arbitrary equations, which may even be contradictory. It is not so surprising that the definition of general recursive functions was considered unsatisfactory at the time.

Kleene gives an example showing hot to express the minimization operator $\mu y . (r(x_1, \ldots, x_n, y) = 0)$ in this way (I write $\vec{x}$ for $x_1, \ldots, x_n$ and $n^{+}$ for successor of $n$): \begin{align*} \sigma(0, \vec{x}, y) &= y\\ \sigma(z^{+}, \vec{x}, y) &= \sigma(r(\vec{x}, y^{+}), \vec{x}, y^{+}) \\ \phi(\vec{x}) &= \sigma(\rho(\vec{x},0), \vec{x}, 0) \end{align*} This is a system of equations in $\sigma$ and $\phi$, for a given $r$. We then set $\mu y. (r(\vec{x}, y) = 0) \mathrel{{:}{=}} \phi(\vec{x})$.

Kleene goes on to prove that one can reduce every system $\mathcal{S}$ to one involving primitive recursive functions (which he defines in the usual way) and the minimization operator $\mu$. Apparently after this paper everyone forgot about the original unruly definition in terms of systems of arbitrary equations.