patternMajor
Why are computable functions also called recursive functions?
Viewed 0 times
whycalledcomputablearealsorecursivefunctions
Problem
In computability theory, computable functions are also called recursive functions. At least at first sight, they do not have anything in common with what you call "recursive" in day-to-day programming (i.e., functions that call themselfes).
What is the actual meaning of recursive in the context of computability? Why are those functions called "recursive"?
To put it in other words: What is the connection between the two meanings of "recursiveness"?
What is the actual meaning of recursive in the context of computability? Why are those functions called "recursive"?
To put it in other words: What is the connection between the two meanings of "recursiveness"?
Solution
The founders of computability theory were mathematicians.
They founded what is now called computability theory
before there was any computers.
What was the way mathematicians defined functions that could be computed?
By recursive definitions!
So there were recursive function before
there were any other model of computation like Turing machines or
lambda calculus or register machines.
So people referred to these function as recursive functions.
The fact that they turned out to be exactly
what Turing machines and other models can compute is a later event
(mostly proven by Kleene).
We have the simple definition of a recursive function which is now called
primitive recursive function.
There were not general enough (e.g. Ackermann's function)
so people developed more general notions
like $\mu$-recursive functions and
Herbrand-Gödel general recursive functions that
did capture all computable functions (assuming the Church's thesis).
Church claimed that his model of lambda calculus captured
all computable functions.
Many people, and in particular Gödel, were not convinced that
these capture all functions that can be computed.
Until Turing's analysis of computation and introduction of his machine model.
The name of the field used to recursion theory.
However there has been a successful push in recent decades
to change the name to something more appealing from
recursion theory to something more computer sciency (vs. mathy).
As a result the field is now called computability theory.
However if you look at books, papers, conferences, etc. in the early decades
they are called recursion theory and not computability theory.
Even the title of Soare's own 1987 book
(who was the main person behind the push to change the name
to computability theory)
is "Recursively Enumerable Sets and Degrees".
If you want to know more about the history
a fun and good place to read about it is
the first chapter of Classical Recursion Theory by Odifreddi.
They founded what is now called computability theory
before there was any computers.
What was the way mathematicians defined functions that could be computed?
By recursive definitions!
So there were recursive function before
there were any other model of computation like Turing machines or
lambda calculus or register machines.
So people referred to these function as recursive functions.
The fact that they turned out to be exactly
what Turing machines and other models can compute is a later event
(mostly proven by Kleene).
We have the simple definition of a recursive function which is now called
primitive recursive function.
There were not general enough (e.g. Ackermann's function)
so people developed more general notions
like $\mu$-recursive functions and
Herbrand-Gödel general recursive functions that
did capture all computable functions (assuming the Church's thesis).
Church claimed that his model of lambda calculus captured
all computable functions.
Many people, and in particular Gödel, were not convinced that
these capture all functions that can be computed.
Until Turing's analysis of computation and introduction of his machine model.
The name of the field used to recursion theory.
However there has been a successful push in recent decades
to change the name to something more appealing from
recursion theory to something more computer sciency (vs. mathy).
As a result the field is now called computability theory.
However if you look at books, papers, conferences, etc. in the early decades
they are called recursion theory and not computability theory.
Even the title of Soare's own 1987 book
(who was the main person behind the push to change the name
to computability theory)
is "Recursively Enumerable Sets and Degrees".
If you want to know more about the history
a fun and good place to read about it is
the first chapter of Classical Recursion Theory by Odifreddi.
Context
StackExchange Computer Science Q#51770, answer score: 20
Revisions (0)
No revisions yet.