30
$\begingroup$

We learned about the concept of enumerations of functions. In practice, they correspond to programming languages.

In a passing remark, the professor mentioned that the class of all total functions (i.e. the functions that always terminate for every input) is not enumerable. That would mean that we can not devise a programming language that allows us to write all total functions but no others---which would be nice to have!

So how is it that we (apparently) have to accept the potential for non-termination if we want decent computational power?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
25
$\begingroup$

Because of diagonalization. If $(f_e: e \in \mathbb{N})$ was a computable enumeration of all total computable functions from $\mathbb{N}$ to $\mathbb{N}$, such that every $f_e$ was total, then $g(i) = f_i(i)+ 1$ would also be a total computable function, but it would not be in the enumeration. That would contradict the assumptions about the sequence. Thus no computable enumeration of functions can consist of exactly the total computable functions.

Suppose we think of a universal computable function $h(e,i)$, where "universal" means $h$ is a computable binary function and that for every total computable unary function $f(n)$ there is some $e$ such that $f(i) = h(e,i)$ for all $i$. Then there must also be some $e$ such that $g(n) = h(e,n)$ is not a total function, because of the previous paragraph. Otherwise $h$ would give a computable enumeration of total computable unary functions that includes all the total computable unary functions.

Thus the requirement that every function is a system of functions is total is incompatible with the existence of a universal function in that system. For some weak systems, such as the primitive recursive functions, every function is total but there are not universal functions. Stronger systems that have universal functions, such as Turing computability, simply must have partial functions in order to allow the universal function to exist.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I just wanted to add that somebody found what appears to be a loophole in diagonalization. If you use a typed representation for the program, you can use the type system to disallow diagonalization and create a total self-interpreter. See Breaking Through the Normalization Barrier: A Self-Interpreter for F-omega for details. $\endgroup$
    – hatch22
    May 19, 2016 at 21:03
  • $\begingroup$ Of course, System F is not a Turing complete system. The paper you linked is interesting; it seems that they manage to leverage the non-Turing-completeness in an interesting way. $\endgroup$
    – Carl Mummert
    May 20, 2016 at 11:50
  • $\begingroup$ I don't get why "then $g(i) = f_i(i) + 1$ would also be a total computable function". If $g$ is a total computable function then $\exists k, f_k = g$, then evaluating $g(k)$ requires evaluating $g(k) = f_k(k) + 1 = g(k) + 1$: conttradiction. So it seems that if there is an enumeration of total computable functions, we cannot even build $g$, so that we cannot reach a contradiction to disprove the initial hypothesis (We can reach a contradiction, but it just disproves $g$ being total computable). $\endgroup$
    – agemO
    Jul 23, 2018 at 6:03
  • $\begingroup$ And even using a shifted diagonal to avoid this problem seems to lead to contradictions. $\endgroup$
    – agemO
    Jul 23, 2018 at 6:24
10
$\begingroup$

Just to be clear, we need to distinguish mathematical functions (I will call them functions and there is often uncountably many of them so they are not at all enumerable) and functions you can write: I will call them programs or also computable functions.

A subset $S$ of a countable set $E$ is called computable if there is a program that, given an element $x$ of $E$ responds "yes" if $x∈S$ and "no" if $x\not∈S$. (And he always has to respond something) A set is called recursively enumerable if the program is authorized not to respond instead of saying "no". (it's equivalent to require that the program has to print all elements of $S$ in any order)

The set of all programs that are total on a finite set is enumerable because you can write an interpreter that just run the program on all the elements of the finite set and return "yes" if they all terminates. (But can't see if any of them does not)

Your professor said that the set of all programs that are total on a infinite set is not enumerable because you can't just run your program on an infinite number of elements.

But this does not mean this is bad:

  1. For example the set if all programs that are provably total is enumerable because you can enumerate all the proofs and mechanically check if they prove your program is total.

  2. Even an enumerable set would not be practical, because you may have to wait forever without being sure if the procedure would terminate one day. I don't see how to use a programs that enumerate all total functions...

There are some programming languages where everything you write is guaranteed to terminate just with static typing! There are even some that guarantees you polynomial bound. They are mostly academic for now, writing in those will probably make you feel the constraints more that writing in Python, but there are a lot of researchers working on this.

So to answer your question: in a sense, yes. Potential non-termination is necessary to be Turing-complete (highest computational power for now). But I don't find this directly relevant to the fact that total functions are enumerable or not. You can still write all total programs!

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ "because you can't just run your program on an infinite number of elements" -- this is a weak argument as I might not need to do this if I can salvage all information I need from the program itself. See here for a question illustrating the danger of your reasoning. $\endgroup$
    – Raphael ♦
    Mar 13, 2012 at 6:44
  • $\begingroup$ Indeed. I did not claim it was a proof (as always you have to build a diagonal argument) and maybe I shouldn't have used the word "because". I was trying to answer your question which (I thought) was not about a proof of your professor's statement but about why termination conflicts with computational power. $\endgroup$
    – jmad
    Mar 13, 2012 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.