I was just reading a chapter about LOOP-computable functions and I have the following question: Is it possible to numerate every LOOP program with an algorithm?
Formally: Is it possible to have a LOOP program M, s.t M(n,m)=P_n(m) (input is n,m. output is P_n(m), where P_n is the numeration of the loop programs).
No. Assume M is a loop-program. Define program D(x) = M(x, x). Then D is trivially a loop-program. Let i be the index of D in the enumeration, i.e. P_i = D; then M(i, i) doesn’t halt because it’s an infinite loop (D(i) calls M(i,i) calls D(i) …). Therefore M can’t be a loop-program.
2