= Total computable diagonal over primitive recursive syntax
{title2=$d(n)=F_{p_n}(n)+1$}
Enumerate all valid unary <primitive recursive functions in intension> by their decidable codes $p_n$, and interpret each extension $F_{p_n}$. The <function> $d(n)=F_{p_n}(n)+1$ is a <total computable function>, since each finite construction terminates. If it were <primitive recursive>, some $F_{p_j}$ would equal $d$, giving $d(j)=d(j)+1$. Repeated extensions in the syntax enumeration do not affect this argument.
Back to article page
