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
699067
de