bijective projection N <-> algorithms

I thought I'd might be interesting to do some "automated algorithm/turing-automata finding" (I had the busy beaver in mind). I thought about trying many in a specific language (brainfuck or smallfuck) in order to find a programm with an output as large as possible for a given input. Creating a smallfuck-programm form a integer is of course a trivial problem if the program itself does not need to be valid (unfinished loops) with conversion to base-n.

But given the condition that all n had to point to an actual program and vice verse, that different Ns point to different algorithms, and that all algorithms possible will be projected (sorry for my bad english, I don't know many CS terms).

Is this possible? Has somebody done this yet? What keywords do I have to use to find background informations on this topic?

(I know finding an algorithm this way is a kind of stupid, but maybe an answer will improve my knowledge of automatas)

-

migrated from cstheory.stackexchange.comJul 12 '11 at 0:56

This question came from our site for theoretical computer scientists and researchers in related fields.

Hi Fritz. This question doesn't seem to be a research-level question and it is probably more suitable for Math.SE, would like me to migrate it to Math.SE? –  Kaveh Jul 8 '11 at 1:28
If you think so please do. Why three downvotes? Is the answer that obvious? My english that bad? –  Fritz Jul 11 '11 at 20:45
OK, I am imgrating it to Math.SE. (I guess down votes are mainly because people think the question is not research-level and therefore out of scope for cstheory as explained in the FAQ, but clarifying the question would be a good idea.) –  Kaveh Jul 12 '11 at 0:54

Well mathematically this is easy. Suppose you have a bijection $f: \mathbb N \to \Sigma^*$, where $\Sigma$ is the set of all valid characters in a program. Let $\mathfrak P$ be the set of valid (smallfuck- or whatever) programs. Now clearly $\mathfrak P \subset \Sigma^*$. Suppose further, that $|\mathfrak P| = \infty$, then there exists a bijection $g: \mathbb N \to \mathfrak P$. We will define $g$ recursively:
$$g(1) := f(k^*) \text{ with } k^* = \min \{k \in \mathbb N\;|\;f(k) \in \mathfrak P\}$$
$$g(n+1) := f(k^*) \text{ with } k^* = \min \{k \in \mathbb N\;|\;f(k) \in \mathfrak P \text{ and } k > f^{-1}(g(n))\}$$
This is probably not what you want for application in computer science, because it basically just the same as checking if $f(k)$ is a valid program for every $k$, and then only counting those that are.