# A programming language that can only implement computable bijective functions?

Are there programming languages(or logic) that can implement(or express) a function $f:\mathbb{N}\to \mathbb{N}$ if and only if $f$ is a computable bijective functions?

• Somebody proved to me that it is impossible to create a language that accepts only terminating programs. Since you question is pretty similar, I guess no. Nov 22 '12 at 21:34
• It seems unlikely there would be such a programming language, I guess you could try to enforce it, but then you wouldn't be able to do simple things like sorting, at least not without it becoming horribly complex and painful. Nov 22 '12 at 21:56
• @FUZxxl This doesn't capture many terminating programs, In fact even the function f(x)=1 is impossible to express in this language. Also I have a feeling this kind of functions are captured by total functional programming since every function is a total function. Nov 22 '12 at 22:04
• @FUZxxl, I don't think that's right, but such a language would have to be limited. For example, a language that was equivalent to Finite deterministic automata would be guaranteed to terminate, but would be extremely limited in what it could calculate. Nov 23 '12 at 5:10
• @FUZxxl, the details of such a statement are important. It is easy to design a programming language in which every program terminates. It is a different matter to design a language which we can express every computable function. Nov 23 '12 at 8:08

There is no such language.

However, have a look at Boomerang. It is a language for writing bijections between strings. I do not know how wide a class of maps is expressible in it, but I am sure you can find out if you search a bit.

It is reasonable to require of a programming language that the set of valid programs be recognizable by an interpreter or a compiler, i.e., that it be a computably enumerable set. Suppose then we had a programming language whose set of valid programs were computably enumerable and which implemented precisely all computable bijections $\mathbb{N} \to \mathbb{N}$. That would imply that we can computably enumerate all computable bijections (simply enumerate all valid programs in this programming language), but this is impossible by the next theorem.

Theorem: Suppose $f_0, f_1, f_2, \ldots$ is a computable sequence of computable bijections. Then there is a computable bijection which is not in the sequence.

Proof. We construct a bijection $g : \mathbb{N} \to \mathbb{N}$ as follows. To define the values $g(2 k)$ and $g(2 k + 1)$, we look at $f_k(2 k)$:

• if $f_k(2 k) = 2 k$ then set $g(2 k) = 2 k + 1$ and $g(2 k + 1) = 2 k$,
• if $f_k(2 k) \neq 2 k$ then set $g(2 k) = 2 k$ and $g(2 k + 1) = 2 k + 1$.

Clearly, for every $k \in \mathbb{N}$, $g$ is different from $f_k$ because $g(2 k) \neq f_k(2 k)$. Furthermore, $g$ is computable and it is a bijection because it is its own inverse. QED.

• Why do you even need this $2k$ and $2k+1$ trick? Using $g(k)=f_k(k)+1$ should suffice. Nov 23 '12 at 7:11
• @FUZxxl: if you use $f_k(k)+1$ the resulting function is not surjective
– Vor
Nov 23 '12 at 8:35
• You need to make sure that $g$ is bijective. Nov 23 '12 at 15:38
• The initial statement is wrong, there are many such languages in the literature. Feb 2 '14 at 9:47
• On the other hand your proof seems legit. Perhaps I'm confused somehow. I need to read Axelsen and Glück's paper (see my answer) carefully to figure out what's going on here. Feb 2 '14 at 10:07