[hawkice]

What is actually happening here is not quite what you think. There is a subset of programs for which you can prove it halts, notably lower-bounded by e.g. Idris' totality checker (which is a part of its type system).