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.