[edflsafoiewq]

This reminds me of the classic problem in computation, where the simplest form of computation, the lookup table, input -> output, is limited to a finite domain. Turing modified the computation to have a finite internal state and infinite external environment (tape), so it becomes a transition function (state, stimulus) -> (new state, response), applied recursively in a feedback loop, allowing it to operate on infinite domains.

Famously a simple lookup table for the transition function then suffices to compute any computable function.

[eru]

Have a look at Post's correspondence problem for even crazier universal models of computation. Or at Fractran.

Simplified for Post's correspondence problem, you have a set of playing cards with text written on the front and back. (You can make copies of cards in your set.)

The question is, can you arrange your cards in such a way, that they spell out the same total text on the front and back?

As an example your cards might be: [1] (a, baa), [2] (ab, aa), and [3] (bba, bb). One solution would be (3, 2, 3, 1) which spells out bbaabbbaa on both sides.

Figuring out whether a set of cards has a solution is Turing complete.

[clooper]

That's a good point.