2
$\begingroup$

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)

  • 0
    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.)2011-07-12

1 Answers 1

2

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.

  • 0
    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.2011-07-13