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