- A computable function is a function that can be written as an algorithm and executed by a machine. This execution should terminates and produces a value.
- An intuitive computable functions are the set of functions that we know in advance how many step the computation requires.
For instance; the average of 1-2-3 ... to N, requires exactly N additions and one division.
This kind of computable functions is commonly called : Primitive recursive functions.
- Primitive recursive functions is a subset of computable functions. A classic example of a computable function that isn't Primitive recursive is the famous Ackerman function.
Wondering: functions / procedures are actions. An action holds temporal meaning (act in past, present future):
- Present: Natural / sequential programming
- Future: non deterministic / concurrent / asynchronous programming
- Past: Versioning / memorization / history sourcing
See full classification of comutability here: Chomsky hierarchy
No comments:
Post a Comment