Recursive functions and the Church-Turing thesis

[ionathanch]

This issue is about the chapter on recursive functions. I'm using the Incompleteness and Computability book, so I'll refer to various parts of it as sections 2.x.

Here's what I've gathered so far, just so I don't get the terms mixed up:

• Primitive recursive functions are zero, succ, and projection, closed under composition and recursion.
• Partial recursive functions are the same as primitive recursive ones but additionally closed under unbounded search.
• Recursive functions are partial recursive functions that are total.
• General recursive functions are the same as primitive recursive ones but additionally closed under unbounded search over regular functions.
• General recursive functions are the same as recursive functions.
• Primitive r.f. ⊂ general r.f. ⊂ partial r.f.

In the Introduction (section 2.1), it states that by the Church-Turing thesis, recursive functions (so, general recursive functions) can simulate other models of computation, which means that general recursive functions are the same as Turing-computable functions. This is restated in section 2.14 on Non-Primitive Recursive Functions, as well as the summary at the end of the chapter.

But shouldn't Turing-computable functions correspond to partial recursive functions? It doesn't seem like general recursive functions could simulate Turing machines that don't halt on some inputs, since these functions are total. Turing machines could also compute partial recursive functions, and not halt on inputs where the function is undefined.

This was slightly difficult to look up, since other sources (e.g. Wikipedia) use the term "(general) recursive function" to mean what we would call partial recursive functions, while others use "total recursive function" to mean what we would call general recursive functions. But in any case, it seems that the functions involved in computability should at least be partial.

[Umberto-C]

Turing computability as originally defined by Alan Turing (1936-1937) covered only total recursive functions. During the '40s Stephen Kleene (who defined for the first time the set of partial recursive functions for another formalism) modified the original version of Turing machines to account also for partial recursive funtions (also inspired by detailed analysis of Turing formalism by Emil Post). Then Kleene proved the equivalence of Turing's definition and his with respect to total recursive functions. So: total Turing-computable functions are the same as total recursive functions of another formalism and partial Turing-computable functions are the same as partial recursive functions of the same other formalism. The Church-Turing thesis regards only the total functions (it was first proposed when partial recursive functions didn't had appeared yet), but it can be easily generalized to partial ones and we may call this generalization Kleene's thesis (Judson Webb and Martin Davis call it so): every mechanically computable partial function is partial recursive, where for recursive we can substitute one of the equivalent formalism, such as Turing-computable (Kleene's version), lambda-definable and so on. The fact that all these formalisms are equivalent is due to Kleene's normal form theorem.

[Umberto-C]

Concretely: if you are working with total functions, you apply Church-Turing thesis to your chosen formalism for recursivity; if you are working with partial functions, you apply Kleene's thesis again to your preferred formalism for recursivity. Obviously, just because total functions are partial functions, Kleene's thesis is stronger and you can use it even in the first case.

[rzach]

I think @Umberto-C 's perfectly correct comment notwithstanding, the issue for the books is one of consistency. Wherever the CT thesis is defined it should be defined so that its invocations are appropriate (ie, if we define it for total functions we should only invoke it for partial functions). A discussion of the partial/total issue is needed too.

Right now the definition of Turing computable applies only to total arithmetical functions so we're technically in the clear. @ionathanch asked how general recursive functions can simulate partial functions -- they cannot. But if a Turing machine computes a total function the simulation by general recursive function will work because in that case the T predicate yields a regular function. Ie: if e is the index of a TM that computes a total function f, then for every x there is a y st T(e,x,y) holds -- y is the record of the halting computation of M_e on input x). So h(y,x) = 0 if T(e,x,y) and =1 otherwise is regular and U(\mu h(y,x) = 0) is general recursive and gives f(x).

[rzach]

Let's leave it open, I should go through and make sure this is all right and add stuff on the total/partial issue