Proof

(related to Corollary: The set of WHILE-computable functions is included in the set of partially WHILE-computable functions)

It is sufficient to find a function \(f : \mathbb N^k \to \mathbb N\), which is partially WHILE-computable, but is not WHILE-computable. This is the case for the partial function \(f : \mathbb N \to \mathbb N\)

\[f(n):=\cases{0&\text{if }n=0\\ undefined&\text{if }n\neq 0}\]

which is computed by the following \(W H I L E\) program:

\[\mathtt{WHILE~r_i\neq 0~DO~r_i:=r_i+1~END;}\]


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition