HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

In the beginning, computable functions were always total, but when where the partial functions included

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
totalthecomputablealwaysbutwherebeginningwerepartialincluded

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#79665, answer score: 3

Revisions (0)

No revisions yet.