The modern definition of computable functions $f\colon \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 concerned 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

The Stanford Encyclopaedia of Philosophy has a summary of the history of recursive functions. In particular, in Section 1.8 we can read that Stephen Kleene explicitly defined the partial recursive functions, and showed them to be equivalent to several other notions of computable functions, in a series of papers between 1936 and 1954. For example, already his 1936 paper General recursive functions and natural numbers introduces the unbounded search operator which leads to partial functions (when the search does not find anything).


My guess is 1965-1971, due to the introduction of analysis of algorithm runtimes. See below for reasoning.

I'm not great with the history here, but as I understand it what happened is that people switched from considering

  • functions $\mathbb N \rightarrow \mathbb N$ (find the nth number in the increasing sequence). In this definition, the natural question to ask is, "can we enumerate this sequence", and how many steps does it take it output each digit?
  • To considering functions $\mathbb N \rightarrow \{YES, NO\}$. In this definition, the natural question is "how hard is it to calculate the answer"? Note that it's now much easier to consider partial functions.

When this switch happened, I'm less sure. Turing was using sequences in 1936 to calculate digits. Stearns and Hartmanis in 1965 still were, in their paper that introduced asymptotic analysis of algorithms. Steven Cook in 1971 was not. I assume these were typical of the time (that everyone publishing that year used the same convention). Given the (very!) short gap to a switch after a long stability, I can only assume that decision problems are more natural to think about for complexity analysis, and this caused the change.

  • $\begingroup$ One cannot "reason" historical developments, but rather find documents witnessing past events. $\endgroup$ – Andrej Bauer Oct 9 '20 at 14:58
  • $\begingroup$ This was not a historical event. No one specific thing happened, most likely. As such, I'm taking the etymology approach--try to bisect and find when things changed. It may work or not, but I don't think there's going to be a significantly more satisfying answer, only a better researched one. I did in fact go read three primary papers to see when attitudes changed? $\endgroup$ – Zachary Vance Oct 9 '20 at 15:09
  • $\begingroup$ Sure. It's just that Kleene's work predates the 1960's. $\endgroup$ – Andrej Bauer Oct 9 '20 at 15:50
  • $\begingroup$ Partial (computable) functions where already considered for the domain and range $\mathbb N$, as pointed out by Andrej Bauer, years before the 1960's. But anyway, you are quite right about the shift from computability to decision problems. Then, probably, the abstraction to semi-decidability is not that far of a stretch. As far as I recall, Turing, in his seminal work, was more concerned with computing sequences, i.e., given a number and output a digit. $\endgroup$ – StefanH Oct 9 '20 at 21:24

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.