9
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\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, 2017 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, 2017 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, 2017 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, 2017 at 18:53

2 Answers 2

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ One cannot "reason" historical developments, but rather find documents witnessing past events. $\endgroup$
    – Andrej Bauer
    Oct 9, 2020 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, 2020 at 15:09
  • $\begingroup$ Sure. It's just that Kleene's work predates the 1960's. $\endgroup$
    – Andrej Bauer
    Oct 9, 2020 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, 2020 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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