[25] Show that for every m, n 1, there exists a computable function = s (m+1) n of m + 1 variables such

[25] Show that for every m, n ≥ 1, there exists a computable function ψ = s

(m+1) n of m + 1 variables such that for all x, y1,...,ym,

φ(m+n) x (y1,...,ym, z1,...,zn) = φ(n)

ψ(x,y1,...,ym)(z1,...,zn), for all variables z1,...,zn. (Hint: Prove the case m = n = 1. The proof is analogous for the other cases.)

Comments. This important result, due to Stephen C. Kleene, is usually called the s-m-n theorem. Source: [H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967; P. Odifreddi, Classical Recursion Theory, North-Holland, 1989].