Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  FUZxxl Nov 22 '12 at 21:34
1  
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. –  Luke Mathieson 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. –  Chao Xu 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. –  jmite 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. –  Vijay D Nov 23 '12 at 8:08

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
Why do you even need this $2k$ and $2k+1$ trick? Using $g(k)=f_k(k)+1$ should suffice. –  FUZxxl 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. –  Andrej Bauer Nov 23 '12 at 15:38
    
The initial statement is wrong, there are many such languages in the literature. –  Nathaniel Feb 2 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. –  Nathaniel Feb 2 at 10:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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