Turing-Complete Language Interpreter

Brachylog (2) → Post correspondence problem, 9 bytes

~h=∋ᵐ\cᵐ=

Try it online!

Input is a list of lists of strings. (In the Post correspondence problem as defined on Wikipedia, the inner lists have two elements each, although this program can actually handle a generalisation to any number of elements.) This program brute-forces solutions to the problem, in order of length, until a solution is found. The Post correspondence problem is known to be able to simulate a Turing-machine, and thus brute-forcing solutions to it is Turing complete. If run as a function, rather than a program, it actually produces meaningful output as well.

The program in the TIO link above is [["a","baa"],["ab","aa"],["bba","bb"]], which I copied from Wikipedia. The solution (which the program finds fairly quickly) is ["bbaabbbaa","bbaabbbaa"].

Explanation

This is pretty much just a direct translation of the Post correspondence problem to Brachylog.

~h=∋ᵐ\cᵐ=
~h         Find {the shortest possible} list which starts with {the input}
  =        and for which all elements are equal
   ∋ᵐ      such that taking an element of each element,
     \cᵐ   and concatenating elements in corresponding positions,
        =  produces a list all of whose elements are equal.

Basically, we create a list that's repeated copies of the input (as few as possible, meaning that we don't miss any possibilities when brute-forcing), take one element from each copy, then concatenate corresponding elements (as in the Post correspondence problem).

Jelly → "Add minimum to transpose", 5 4 bytes

+"Ṃẞ

Try it online! (runs only one iteration, to avoid timeouts)

A very simple Turing-complete construction: we take a square matrix as a program, and loop forever, identifying the lexicographically smallest row, then increasing each element of the first row by the first element of the lexicographically smallest, each element of the second row by the second element of the lexicographically smallest, and so on. (The Jelly program is "+" add corresponding elements {of the input and} Ṃ the minimum {of original}, ẞ loop"; this is a byte shorter than my previous program Z+ṂZß, which did exactly the same thing. Clearly I should have focused on golfing the Jelly, not just golfing the implemented language.)

The resulting language is Turing-complete for much the same reason as Kangaroo. The first element of each row acts like a skip count (although instead of the skip count of each command reducing when it's skipped, we instead increase the skip count of each command when it's run, and look for the command with the lowest skip count rather than commands with zero skip counts; this comes to the same thing). We ensure that this first element is higher than the other elements (which represent the number of times each command appears in each command's multiset), thus ensuring that the first row is never the minimum; the remainder of the first row can be garbage. The only remaining trouble is modelling the way that commands with equal skip count run cyclically in sequence, but we can do that by multiplying all the skip counts by a large constant, then adding on small "initial" skip counts to the first column to serve as a tiebreak. This gives us a tiebreak of "first nonskipped command runs", not "nonskipped commands run cyclically in sequence", but the Turing-completeness construction for Kangaroo does not care about this difference.

Mathematica interpreting Conway's Game of Life, 64 bytes

CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}~Nest~##&

Conway's Game of Life is known to be Turing complete; and cellular automata are Stephen Wolfram's truest obsession. CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}} is a rule that transforms a two-dimensional array of 0s and 1s according to one step of Conway's Game of Life. (I think the default behavior is that this array wraps around its edges, so is really a discrete torus.) ~Nest~##& turns this rule into a function which, when given an initial board state (of any dimensions) and an integer n as arguments, outputs the result of n iterations of the Game of Life rule.

For your own enjoyment, you could use the wrapped version

b = RandomInteger[1,{50,50}];
Manipulate[ArrayPlot[
  CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}~Nest~##&
    [b, n] ]
, {{n,0}, 0, 100, 1}]

and scroll your way through 100 generations on a 50x50 board.