0
$\begingroup$

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

  • 0
    There are total functions that are not computable, but in this case one only has (at best) a non-effective description of the function, and saying it is terminating does not really make sense.2012-08-28

2 Answers 2

2

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
    Consider the function $f$ which adds 1 to its argument, unless the argument is 0, in which case it goes into an infinite loop and never yields a result. This is not a terminating function, since it will fail to terminate when given the argument 0. It is also not a total function, since it fails to yield a result when given the argument 0.2012-08-22
0

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