Take the 2-minute tour ×

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

share|improve this question
Not by default, but by definition. –  MJD Aug 22 '12 at 2:08
What is the definition of a terminating function? –  William Aug 22 '12 at 2:17
Can you provide the definitions of "total function" and "terminating function" you are using here? –  Rahul Aug 22 '12 at 22:45
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. –  Marc van Leeuwen Aug 28 '12 at 14:31

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

share|improve this answer
Could you please give an example of this ? –  M.A Aug 22 '12 at 2:06
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. –  MJD Aug 22 '12 at 2:10

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

share|improve this answer

Your Answer


