Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

migrated from Jul 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.

share|cite|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

Your Answer


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.