If we have a total function, is it by default terminating function? How can we prove the termination for this total function?
2026-04-04 14:22:43.1775312563
On
Total function and termination
303 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
0
On
To echo @William: what does talk of 'termination' mean here?
It suggests (at least to this reader) the idea of a terminating computation. But even if we restrict ourselves to total functions that map numbers to numbers, not all such functions are computable. So on one very natural reading, not ever total function $f \colon \mathbb{N} \to \mathbb{N}$ can be said to be terminating (if that means that there is a way of computing $f$ which terminates for every input).
Since the definitions of "total function" say that is defined for all possible inputs, it seems that, yes, it must terminate (otherwise it would not be defined for any input that is does not terminate for).