The s-m-n Theorem

Let be any Computable Partial Function. Then there is a total computable function such that for all and all , we have .

This is conceptually related to the Curry-Howard Correspondence

Proof

Let be the code of a machine that does the following:

1. Accepts input
2. Writes out
3. Computes This is computable.