The modern definition of computable functions $f : \mathbb N \to \mathbb N$ as given on wikipedia quite naturally describes partial functions, and not just total functions. Now I am reading some historical references, and before and around the 1930's people just seemed to be concernced with total computable function, so that when they talk about computable functions they always mean total functions.

As an example let me cite An unsolvable problem of elementary number theory by A. Church, here he just considers total functions right from the start, and when he introduces $\lambda$-definable, or recursive functions, he also just considers total function.

So at what point, and why, people dropped the assumption that computable functions always have to be total?

  • $\begingroup$ It appears that paper is defining lambda calculus. In computability theory, there is a difference between a program and the function induced by a program. Some programs may be partial in the sense that their behavior isn't defined for all inputs. Lambda calculus is total in that sense.... $\endgroup$ – DanielV Aug 4 '17 at 19:39
  • $\begingroup$ ...But the induced function is only total if the program converges for every input. In that sense, lambda calculus does not at all assume computable functions are total. Plenty of lambda programs don't halt. Further, every partial computable (in the turing complete sense) function is induced by some lambda calculus expression. $\endgroup$ – DanielV Aug 4 '17 at 19:39
  • $\begingroup$ The formalism itself might allow non-terminating computation paths, but nevertheless in the paper it is just applied to total functions, a (total) function $f : \mathbb N \to \mathbb N$ is called computable if there exists a formula F (=$\lambda$-term) with $F(n) = m$ iff $f(n) = m$ (where $n$ and $m$ are represented by appropriate $\lambda$-terms), so by definition just $\lambda$-programs that terminate for every input are considered in the definition. $\endgroup$ – StefanH Aug 5 '17 at 18:52
  • $\begingroup$ That in some sense is what I am asking, from the formalism it is quite natural to include partial functions, but this is not done, and also not in other papers from that time (I just took this one as an example). $\endgroup$ – StefanH Aug 5 '17 at 18:53

Your Answer

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

Browse other questions tagged or ask your own question.