algorithm - Create a function for given input and ouput

Question

Imagine, there are two same-sized sets of numbers.

Is it possible, and how, to create a function an algorithm or a subroutine which exactly maps input items to output items? Like:

Input = 1, 2, 3, 4
Output = 2, 3, 4, 5

and the function would be:

f(x): return x + 1

And by "function" I mean something slightly more comlex than [1]:

f(x):
    if x == 1: return 2
    if x == 2: return 3
    if x == 3: return 4
    if x == 4: return 5

This would be be useful for creating special hash functions or function approximations.

---

Update:

What I try to ask is to find out is whether there is a way to compress that trivial mapping example from above [1].

Answer 1

Finding the shortest program that outputs some string (sequence, function etc.) is equivalent to finding its Kolmogorov complexity, which is undecidable.

If "impossible" is not a satisfying answer, you have to restrict your problem. In all appropriately restricted cases (polynomials, rational functions, linear recurrences) finding an optimal algorithm will be easy as long as you understand what you're doing. Examples:

• polynomial - Lagrange interpolation

• rational function - Pade approximation

• boolean formula - Karnaugh map

• approximate solution - regression, linear case: linear regression

• general packing of data - data compression; some techniques, like run-length encoding, are lossless, some not.

In case of polynomial sequences, it often helps to consider the sequence b_n=a_n+1-a_n; this reduces quadratic relation to linear one, and a linear one to a constant sequence etc. But there's no silver bullet. You might build some heuristics (e.g. Mathematica has FindSequenceFunction - check that page to get an impression of how complex this can get) using genetic algorithms, random guesses, checking many built-in sequences and their compositions and so on. No matter what, any such program - in theory - is infinitely distant from perfection due to undecidability of Kolmogorov complexity. In practice, you might get satisfactory results, but this requires a lot of man-years.

See also another SO question. You might also implement some wrapper to OEIS in your application.

Fields:

Mostly, the limits of what can be done are described in

• complexity theory - describing what problems can be solved "fast", like finding shortest path in graph, and what cannot, like playing generalized version of checkers (they're EXPTIME-complete).

• information theory - describing how much "information" is carried by a random variable. For example, take coin tossing. Normally, it takes 1 bit to encode the result, and n bits to encode n results (using a long 0-1 sequence). Suppose now that you have a biased coin that gives tails 90% of time. Then, it is possible to find another way of describing n results that on average gives much shorter sequence. The number of bits per tossing needed for optimal coding (less than 1 in that case!) is called entropy; the plot in that article shows how much information is carried (1 bit for 1/2-1/2, less than 1 for biased coin, 0 bits if the coin lands always on the same side).

• algorithmic information theory - that attempts to join complexity theory and information theory. Kolmogorov complexity belongs here. You may consider a string "random" if it has large Kolmogorov complexity: aaaaaaaaaaaa is not a random string, f8a34olx probably is. So, a random string is incompressible (Volchan's What is a random sequence is a very readable introduction.). Chaitin's algorithmic information theory book is available for download. Quote: "[...] we construct an equation involving only whole numbers and addition, multiplication and exponentiation, with the property that if one varies a parameter and asks whether the number of solutions is finite or infinite, the answer to this question is indistinguishable from the result of independent tosses of a fair coin." (in other words no algorithm can guess that result with probability > 1/2). I haven't read that book however, so can't rate it.

Strongly related to information theory is coding theory, that describes error-correcting codes. Example result: it is possible to encode 4 bits to 7 bits such that it will be possible to detect and correct any single error, or detect two errors (Hamming(7,4)).

The "positive" side are:

• symbolic algorithms for Lagrange interpolation and Pade approximation are a part of computer algebra/symbolic computation; von zur Gathen, Gerhard "Modern Computer Algebra" is a good reference.

• data compresssion - here you'd better ask someone else for references :)