Total function and termination

303 Views Asked by At

If we have a total function, is it by default terminating function? How can we prove the termination for this total function?

2

There are 2 best solutions below

2
On

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).

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).