What program will derive the underlying algorithm in these question-answer pairs (updated)?

Question

Given this set of question-answer pairs, what program will derive the underlying algorithm and provide the correct answer for any question of the same format.

Question-Answer Pairs (training set):

B:BA
BA:BB
BB:BAA
BAA:BAB
BAB:BBA
BBA:BBB
BBB:BAAA
BAAA:BAAB
BAAB:BABA

Those familiar with binary may notice that the training set is binary numbers with A and B substituted for 0 and 1. The answer to each question is the next binary number (using A and B).

After processing the training set, the program should be able to answer questions such as the following using the algorithm it derived:

BABA:?
BABB:?
BBBBAAA:?
BAABBAAABBABA:?

Constraints:

• The program must derive the counting algorithm only by manipulating the data given in the training set. It must not use hard coded knowledge of binary counting.
• Many algorithms may produce the correct answers. Therefore, the simplest algorithm is preferred.
• The program should assume that each answer is a transformation of the question.
• All questions will be in the binary format seen above, but they may be of arbitrary size.

Can any existing machine learning programs/algorithms solve this? If so, how? If you believe this is unsolvable, please explain why.

---

This update contains background to the question, explanation of the problem space, a new constraint, a proposed solution, and further questions.

This problem is relevant to general machine learning where the machine must learn by observation and feedback the algorithms that govern the world around it.

Based on Kolmogorov complexity, there is at least one program that can produce the correct mappings:

if B, then BA
if BA, then BB
(etc. for all pairs in training set)

This will work for every pair in the training set and nothing else. This will be the shortest program if the training set is completely random. The good news is that this is an upper bound. For any training set that is not random, there will be a smaller program that will work. Also, the number of programs smaller than upper bound is finite.

A unfortunate result of Kolmogorov complexity is that it cannot be calculated. This is due to the halting problem. We can't know if any program will stop until it does.

If the question is "Write pi," then the program that produces the correct answer would never halt because pi has infinite digits. An answer infinitely long is never desirable so I think the best way to deal with this is to put an arbitrary limit on the length of the answer.

With that additional constraint, here is an (inefficient) program that will generate a correct solution program shorter than the upper bound if one exists. (sorry of this is confusing, but these steps outline a program that generates programs that implement an algorithm to map questions to answers in a training set):

1. Create the "upper bound" program. One that maps each input in the training set directly to its output.
2. Generate every possible program that is shorter than the upper bound and list them from shortest to longest.
3. Starting with the shortest program, run the first step of every program.
4. Stop when a correct program is found.
5. Eliminate programs that stop without a correct answer or produce an answer longer than the arbitrary limit.
6. Repeat steps 3-5 running the second step, third step, etc. of the programs.

This program has the following benefits:

• It limits the number of programs to those smaller than the "upper bound" program.
• It avoids the halting problem by
  • incorporating an arbitrary limit to the length of the answer and
  • executing step x in all programs before moving on to step x+1 so that the solution will be found before looping infinity.

The main disadvantage is that it is terribly slow. It takes millions of years to crack a 128 bit password and I think this program could have comparable performance.

Now, the questions:

• Do you see any significant flaws in this solution?

• Can this program's performance be improved in any significant way without introducing onerous constraints?

Answer 1

The same answers you got the last time you asked this question apply. There are infinitely many possible mappings $\{A,B\}^* \to \{A,B\}^*$ and none is preferable to any other.

Let's try to formalize your problem more clearly. I suspect you want an algorithm to solve the following problem:

Given a training set as input (i.e., a set of mappings $x \mapsto y$, where $x,y$ are strings), output the shortest algorithm $A$ with the property that $A(x)=y$ for every $x,y$ in the training set.

The bad news is that this problem is not solvable. In particular, the problem is undecidable, so you should not expect any general algorithm to solve this problem. To do better, you will need some structure on the set of hypotheses (e.g., a distribution on possible mappings or something like that).

Why is this undecidable? Because it is basically the problem of computing the Kolmogorov complexity of the training set, and computing the Kolmogorov complexity is known to be undecidable.

You might be wondering how standard methods for machine learning get around this barrier. The answer is that they avoid this barrier by changing the problem statement. Machine learning methods generally involve a more restricted space of hypotheses (instead of allowing all possible algorithms, we only consider a restricted subset, such as those that are linear or that have some other nice properties) or else involve specifying a probability distribution on the set of possible mappings. I recommend you spend some time studying machine learning.

---

What is the context and motivation for your question? What's the specific real-world situation where you encountered this? To make progress I suspect you'll need to step back and look at the real requirements from your application, and be open to other ways to meet your needs.