Smn-Theorem
The theorem is a central result of computability theory. It provides a means by which one can calculate the code of a program as a function of parameters. One result is that a programming language that can perform runtime-generated code can support currying.
Formal definition
Given with, the Gödel number of the program is predictable.
Then there is a total and computable function with
Non-formal declaration
Said property that it (or can be carried out ), a transformation program is a code U w, which is executed with the parameters x and y, the x and V w calculated from a program, which when entering - SMN of v calculated the same as w at the input of x and v.
Example
We have to show: There is a total and computable function, so that it covers'.
Define. can be calculated and there is a there exists such that:.
After the theorem is true:
There is a total and computable function with for all.
Now we define. is total and computable and we have:
- Computability theory