Take the 2-minute tour ×

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)

share|improve this question
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
add comment

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


1 Answer

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.

share|improve this answer
Sorry, your right this is not what I'm looking for. Thought about Goedel-numbers, but It does not lead me anywhere. –  Fritz Jul 13 '11 at 18:32
You will most likely have to come up with your own encoding/enumeration, especially when using such esoteric languages. –  Alexander Thumm Jul 13 '11 at 18:36
I thought i'd be the easiest way to describe a turing machine and therefor the easies way to enumerate all algorithms running on a turing computer. –  Fritz Jul 13 '11 at 19:27
add comment

Your Answer


