Jelly → Addition Automaton with b = 10, 3 bytes

ṃḌç

Try it online! (contains added Ṅ so that you can see the program being interpreted)

Me in 2018:

Is three bytes possible? [...] at this point it surely seems like it'd be possible somehow, as there are so many ways to do it in four and so many Turing-complete languages you could implement.

Five years later, I finally figured it out.

This program's first argument is the Addition Automaton initial value, and its second argument is the transition table (which is a map). Jelly uses 1-based indexing, so the entry for d=0 actually has to be at the end of the table rather than the start, but otherwise the map is just being specified directly by giving all the mapped-to values in order of the digits being mapped.

Explanation

ṃḌç
ṃ    Convert {the left argument} into digits
       in base (element count of {the right argument}),
       then map them using {the right argument} as the map
 Ḍ   1 × the least significant digit, plus
       10 × the second-least significant digit, plus
       100 × the third-least significant digit, etc.
  ç  Recursive call, where the left argument is {the result of Ḋ}
       and the right argument is {this function's right argument}

Somehow it is not too much of a surprise that the three-byte breakthrough involved using ṃ, a built-in which a) has a very complicated effect and b) for which part of that effect involves indexing into a map/table. Being able to index into a table is the hardest part of implementing many Turing tarpits (not because it's hard, but because the other parts of implementing them are even easier), so finding this answer was a case of looking at what ṃ did and trying to find another builtin that would combine with it to produce a Turing-complete language. (And yes, Addition Automaton was originally discovered by trying to work out what ṃḌ did, although luckily the language as a whole has rather sensible behaviour that can be defined without having to resort to Jelly.)

Addition Automaton is basically defined as "a find-and-replace on the digits of a number, but the replacements can be multiple digits long, and carry into the more significant digits as a consequence". This is actually a very powerful operation; if you allow bases b above 10, it is possible to implement Turing machines pretty much directly. However, the definition requires the two base conversions (into digits to do the mapping, and then back into a single number to handle the carry) to use the same base, whereas thus Jelly program uses the size of the map to do the first conversion and hardcodes the second base conversion to base 10. As such, the program only actually works when b=10; but fortunately, b=10 turns out to be just enough for Addition Automaton to be Turing-complete (it can implement Echo Tag with arbitrary n, which is enough to implement arbitrary tag systems, and from there you can reach Turing machines).

The next challenge in writing very short interpreters in Jelly is likely to try to get them to halt. The effective halt state for this interpreter is "the internal value repeats an older value times a power of 10" – this is something that can be objectively defined, but would take quite a bit of code to implement in Jelly. In Addition Automaton, you have some amount of ability to trade simple halt states for small values of b; b=10 is enough to do things like run 4-state 2-symbol busy beavers, but the "the value multiplies itself by b every cycle" halt state used there is probably not achievable for arbitrary programs with a b as small as 10, and this program has a tendency to collapse into "the binary builtins aren't chaining the way I want them to" hell as soon as you start trying to use custom bases rather than sticking to decimal. So there's a lot of scope for creative solutions there, and Addition Automaton may well not be the best language for the "exit when the implemented language halts" version of the challenge.