Turing-Complete Language Interpreter

Question

A challenge I thought that would be very cool is to make an interpreter for a Turing-complete language of your choosing.

The rules are simple:

1. You may use any language to create this interpreter even if it is newer than this challenge.
2. You may use any Turing-complete language as long as it is not the same as the one you are writing it with.
3. You may not simply evaluate code for example use eval functions.
4. An explanation of how you approached this will be nice but not required.
5. This will be scored in bytes.
6. Each submission must be fully working that means that every feature that your chosen language has must be present.

To be put simply:

Your task is to create a working interpreter for any Turing-complete language with any language of your choosing.

Good luck!

Answer 1

Vim, interpreting Malbolge Unshackled, 2010 bytes

o/rd<C-V>
@g^Wy$/rc<C-V>
WD"0p<ESC>^"iC/ra<C-V>
@f^WylWD"xp`o<C-V><DEL>:if@0.@-[len(@-)-1]==21<C-V>
norm o<C-V>
el<C-V>
norm A<C-V><C-R>=nr2char(@-,1)<C-V>
<C-V>
en<C-V>
<ESC>^"aC`i+x/ra<C-V>
Wr0WD"=char2nr(@-,1)<C-V>
p<ESC>^"bC/rw<C-V>
W"yy$-@g^W"xylWy$:if@y>len(@")<C-V>
norm A<C-V><C-R>=repeat(@x,@y-len(@"))<C-V>
<C-V>
en<C-V>
^WWx$p^Wy$/ra<C-V>
WD"0p<ESC>^"cC/rd<C-V>
@g^Wy$/rd<C-V>
WD"0p@u<ESC>^"jC/ra<C-V>
Wyl$p^WW"ny$++@g^Wyl$p^WW"my$@o^WWD"mpx^WR<C-V><C-R>"<C-V><ESC>y$/ra<C-V>
WD"0p<ESC>^"pC^WWD:wh@">2<C-V>
norm"=<C-V><C-V><C-V><C-R>"%3<C-V><C-V><C-V>
p<C-V>
let@"=@"/3<C-V>
endw<C-V>
p<ESC>^"tC^WWD:let@x=@-|let@"=join(map(split(@",'\zs'),{a,b->b*float2nr(pow(3,a))}),'+')<C-V>
"=<C-V><C-R>"<C-V>
p<ESC>^"fCmg@wgg/m<C-V><C-R>- \|m!<C-V>
WWy$:let@s=@-|if@"==-1<C-V>
norm`g^WxPWyll<C-V>
let@x=4*@-+@"+6-@-<C-V>
norm y$<C-V>
for_ in split(@",'\zs')<C-V>
let@x=(@x+3*(_+6-@-))%6<C-V>
endfo<C-V>
let@x=@x+1<C-V>
norm`n@xjy$2Gom<C-V><C-R>s <C-V><C-V><C-V><C-R>"<C-V>
en<C-V>
@f^WWD"xp:let@"=@x<C-V>
<ESC>^"gC@f@t@f<C-V><C-A>@t^WWy$:if len(@0)!=len(@x)<C-V>
norm$x^Wx"=@-%2<C-V><C-V><C-V>
P$"=(@-+1)%3<C-V><C-V><C-V>
p<C-V>
en<C-V>
<ESC>^"vC:let@"=len(@n)-len(@m)|if@">0<C-V>
let@[email protected](@m[len(@m)-1],@")<C-V>
elsei@"<0<C-V>
let@[email protected](@n[len(@n)-1],-@")<C-V>
en|let@m=join(map(split(@n,'\zs'),{a,b->((float2nr(pow(b+(@m[a]*512)+8,2))%82)%3)}),'')<C-V>
<ESC>^"oC&&<C-V><C-V><C-V><C-R>=<C-V><C-V><C-V>
!=<ESC>^"zCgg"zx/ra<C-V>
^WWD"=_<C-V>
p@t@wggjom<C-V><C-R>- 0 <C-V><C-R>=char2nr(@z,1)<C-V>
<C-V><ESC>@t<ESC>^"dC/rc<C-V>
@g^Wyl:if@"<1<C-V>
let@"=@-<C-V>
en|if@">32&&@"<127<C-V>
let@"=nr2char(@")<C-V>
if@"=="/"<C-V>
let@"='\/'<C-V>
en<C-V>
norm`x/\V<C-V><C-V><C-V><C-R>"<C-V><C-V><C-V>
j"zyl/rc<C-V><C-V><C-V>
@g^WWC<C-V><C-V><C-V><C-R>=char2nr(@z)<C-V><C-V><C-V>
<C-V><C-V><C-V><ESC>@t<C-V>
en<C-V>
<ESC>^"eC^WxPWy$:s/<C-V><C-R>-*$/<C-V><C-R>-<C-V>
^WWD"0p<ESC>^"wC/rd<C-V>
WylW"yy$:s/<C-V><C-R>0*$<C-V>
$"0p^WW"zy$+Wy$:if@"/2<(len(@z)-1)<C-V>
let@0=len(@z)+5<C-V>
norm ^WD"0p/rd<C-V><C-V><C-V>
WWD"yp<C-V>
en<C-V>
<ESC>^"uC/rc<C-V>
@f^WWD"xp:let@z=@-<C-V>
@g:let@z=(@-+@z)%94<C-V>
<ESC>^"hDddggo!
m! -1 -1
@
ra 0 0
rc 0 0
rd 0 0
rw 10
<ESC>mx:for_ in range(32,126)
norm A<C-V><C-R>=nr2char(_)<C-V>

endfo
o 5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1CB6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G"i@
#<ESC>miGo
<C-O>mo$
<C-O>mn%<ESC>gg"xy$:for_ in range(len(@x))
norm @d
endfo
/ra
^WWDA0<ESC>/m<C-R>"
^W"zD"zpj^Wy$`no<ESC>"0p^2x$pxo<ESC>"zp^2x$px:norm<C-R>=repeat("-\"my$+\"ny$@oo<C-V><ESC>\"mp",18-((len(@x)%6)))

G5-d`nO%<ESC>mnj:g/^\d/norm$x^Pa 
:wh1
norm@h
if@z==4
norm@i
elsei@z==5
norm@a
elsei@z==23
norm@b
elsei@z==39
norm@c
elsei@z==40
norm@j
elsei@z==62
norm@p
elsei@z==81
brea
en
norm @e/rc<C-V>
@vj@v
endw

...I'm so tired. This took a solid two months of work. The specification for Malbolge Unshackled is so vague in some places that I had to learn C, just so I could read the reference implementation and copy that. I LEARNED C FOR A VIM PROGRAM.

In all seriousness, this is something that I've wanted to do for a few years now, and having left the site for about a year and a half, I figured I should come back with something big, you know? I call it: Vim Unshackled.

Gist containing full code explanation

Copy+paste it online!
(Running "Hello, world!" takes something like half an hour, which is slightly longer than TIO's 60 second limit, so you'll have to run it on your own machine if you wanna do that)

Answer 2

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).

Answer 3

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.

Answer 4

Perl -a → I/D machine, 24 bytes

$p=$a[$p]+=$_ for@F;redo

Try it online! (contains a header that prints the internal state and halts after 10 iterations, so that the behaviour is observable)

About the language

I've spent the past couple of days working on the I/D machine, one of my latest ideas for very simple programming languages. It works as follows: the data storage consists of an unbounded RAM, initially all zeros. Each element can store an unbounded integer (although in practice, most I/D machine programs will only store small integers in most of them, and make use of the unbounded integers only as a way of addressing cells with large addresses). There's also a data pointer, which points to a cell (i.e. holds the address as a cell); it's initially also zero.

There are only two commands:

• I: Increment the cell the data pointer points to. (The data pointer itself remains unchanged.)
• D: Dereference the data pointer, i.e. read the value of the cell that the data pointer points to. Then store the resulting value that you read back into the data pointer.

Execution simply runs the program in a loop repeatedly, forever.

It's fairly surprising that a language this simple is Turing-complete, so I've been working on proving that. Here's the proof. It's pretty similar to (but simpler than) the proof for Three Star Programmer, a very similar language (and in fact, this submission uses the same basic OISC "shell" around the program, differing only in the actual instruction implemented).

About the program

Usage

The input should be given on standard input, and is an I/D machine program without comments, and using the RLE/OISC syntax. (The I/D machine has two different, equivalent syntaxes, but for golfiness this program only supports one of them.) In this syntax, a program is a sequence of numbers in decimal, representing the lengths of runs of I commands between D commands. (You can specify two or more consecutive D commands via placing a "run of 0 I commands" between them, so the syntax is fully general.)

Explanation

As can be seen from the program, this isn't implementing the I and D commands individually. In fact, it's a (very slightly) optimising interpreter (purely because it's shorter to write this way). The key is to see that a run of n increment commands increment the data pointer's target n times, i.e. add n to it; and a run of 0 increment commands can also be implemented this way, as adding 0 to memory has no effect. So the operation we actually implement is to alternate between implementing a run-of-Is and a D. Or in other words, "add n to the value pointed to by the data pointer (storing it back in the value pointed to by the data pointer), then read the value pointed to by the data pointer and store it in the data pointer". That's clearly more verbose than it needs to be, and we can further simplify this to "add n to the value pointed to by the data pointer, then store that value both in the data pointer's target and the data pointer itself".

So that makes for the core of our program. We're using an array $a to store the RAM, and $p as the data pointer (indexing into the array):

$p=$a[$p]+=$_
         + $_  add {the run length}
   $a[$p]      to the element of $a pointed to by $p
   $a[$p] =    storing the result back into that element
$p=            and also in the pointer itself

Conveniently, Perl interprets uninitialised array elements as 0 when they're treated like numbers, so the array will be lazily initialised to zeroes for us without any explicit code for that being needed. (One potential issue is numerical accuracy when the numbers get large; however, that'll only happen if the amount of the array being used exceeds the machine's address space (Perl integers are large enough to hold pointers), something that can't happen on an idealised machine.)

Finally, all we need to do is to place this program into a couple of loops. The for@F loop, combined with the -a command line option, will loop over the fields of standard input (the default definition of "field" here will split on whitespace). The redo loop will place the entire program in an implicit loop (other than, conveniently, the reading of standard input), which will cause the program to run in a loop repeatedly, as required by the semantics of the I/D machine.

Answer 5

M → Tip, 4 bytes

Ṅ×ịß

Try it online!

The TIO link adds a footer to call the function with the example Tip program shown on the Esolang page (M's "automatic wrapper" to call functions as though they were programs can't handle rational or fixed-point numbers, or at least I haven't figured out how to tell it how, so I need to make the function into a full program by hand to be able to run it.)

This actually prints useful debug output; the program can't be written in 3 bytes in M because a program consisting of exactly three dyads triggers a special case in the parser, so I had to add an extra command to avoid the special case. Making it Ṅ (print with newline) at least gives it a useful purpose.

Function submission, taking two arguments: the initial IP on the left, the program on the right. The program is 1-indexed (i.e. command 1 is the first command; M uses 1-indexing by default); goto commands are represented as M rationals, and the halt command as ı (i.e. the imaginary unit, \$i=\sqrt{-1}\$).

Does not implement I/O (other than halt/no-halt). I/O is an extension to Tip (not part of the language itself), and not required for Turing-completeness.

Explanation/background

Ṅ×ịß
Ṅ     Print {the left argument} and a newline; also resolves a parser ambiguity
  ị   {The left argument}th element of {the right argument}, wrapping on OoB
 ×    Multiply {the left argument} by {the chosen element}
   ß  Recursive call; arguments: {the product} and {the same right argument}

I was reading through the answers to this entry and realised that iterated Collatz functions, which were used in quintopia's earlier answer, would be fairly short to represent in golfing languages in which list indexing wraps by default (i.e. the fifth element of [1,2,3] is 2, because the list is being treated as [1,2,3,1,2,3,1,2,3,…]). So it's easy to extract a particular Collatz operation from a list in very few characters. Can we implement the Collatz operation easily? Well, a Collatz operation is \$rx+s\$, which is a polynomial, and the "base conversion" builtin that many golfing languages have is actually a general-purpose polynomial evaluator in disguise. So all we have to do is index into a list of lists of digits, base-convert them, and we're done, right?

Unfortunately, it's not that simple. The first problem is that although Collatz functions can be defined entirely in terms of integers, that requires a divmod to extract the new value of \$x\$ (the definition where \$x\$ is the same value that's used to index into the list of Collatz operations requires rationals). Well, we just need a golfing language that supports rationals, right? M is a Jelly derivative that supports many types of arbitrary-precision arithmetic, and arithmetic on the rationals is part of its arsenal of mathematical operators.

Then we get to the second problem: M's base-conversion builtin ḅ takes its arguments in the wrong order (it wants the list of digits to appear before the base). The problem with this is that M's default method of chaining together two binary operators given two arguments is \$x\oplus(x\otimes y)\$, and yet we'd want the Collatz operation (which can only fit the \$x\otimes y\$ part of this structure, as it's obtained by an index) to be on the left of the \${\oplus}\$. Sure, we could override the chaining behaviour to pretty much anything we want, but that would cost a whole byte, and the golfing language entries to this question are getting so short that a byte is a lot.

So I looked back and re-evaluated a bit. Are there any operations we could use instead of polynomial evaluation? Ideally, ones that are commutative, so we don't have to worry about argument order? Soon after that, I realised that Collatz functions are more complex than they need to be.

As a result, I created Tip, a simplification/tarpit-ification of iterated Collatz functions in which \$s\$ is always 0, meaning that instead of a polynomial evaluation, we can perform the various operations via a simple multiplication. The language is more complex to prove Turing-complete than Collatz functions are, but it still has enough power to implement any program; there's a proof on the Esolang page.

And of course, unlike base conversion (ḅ), multiplication (×) is commutative, and thus it doesn't matter what order the arguments are placed in. So all we need to write is ×ị, and then place the program into an infinite recursion with ß, and we have a Turing-complete language. Right?

Unfortunately, we run into a new problem. If a program starts with three binary operations, M engages in a special case that chains them as \$(x\odot y)\oplus(x\otimes y)\$ which is the worst possible structure for us, as it doesn't have the three nested function calls we'd need (index, multiply, and recursive call). So no matter what, we're going to need a fourth byte to disambiguate. ¹×ịß (adding the identity function ¹ as a no-op so that the program doesn't start with three binary operators) does exactly what we'd need, causing them to nest inside each other in the way we want. We can use other operations in place of ¹; Ṅ is a good choice because it produces useful debug output.

Is three bytes possible? Unless I'm missing something, not with this specific choice of implementing and implemented language, but 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.

Answer 6

Turing machine (finitely initialized, halts) implementing an encoding of Grill Tag, 2 states, 14 symbols, 232 bytes

We've had a few answers implementing Turing machines in various languages. Time to go the other way, and implement a language in a Turing machine. (A lot of time… I started working on this problem in 2019, and only proved Grill Tag, the implemented language, to be Turing-complete just now.)

0 e e r 1
0 P p l 0
1 P p r 1
0 p P l 0
1 p q r 0
0 q P r 1
* > < r *
0 < > l 0
1 < < l 0
0 i a r 0
1 i < l 1
0 I A r 0
1 I < r 0
0 a x l 0
1 a i l 1
0 A X l 0
1 A I l 1
* X a r *
* x A r *
0 _ o l 0
1 _ _ l halt
0 o _ l 1
1 o A r 0

Try this program in an online simulator

Something that needs to be made clear, because the details can make a huge difference to the size of a universal Turing machine: the problem I'm solving here is the problem of creating a universal Turing machine where the program to implement is specified using a finitely initialized tape (i.e. all but finitely many cells are blank), and for which the Turing machine halts when the implemented program halts. It is possible for a Turing machine to be much smaller if, e.g., you allow for an infinite repeating pattern on the tape, and work out whether the program "should have halted" by inspecting the tape rather than by using a halt state, but that is effectively an entirely different problem (and both are interesting).

As far as I can tell, the previous record for a 2-state Turing machine was 18 symbols, so unless there's been some development I've missed since, this is a huge proportion golfed off a very long-standing mathematical problem.

You can encode a Grill Tag program and initial string into an initial tape for this Turing machine using this Jelly program (the last line of output is the initial tape, the other lines are debug output). The program is specified in the RLE syntax, and its initial queue in JSON (with the head at the start of the array).

Explanations

The implemented language

Grill Tag

Grill Tag is a variant of cyclic tag in which all productions have an odd length, start and end with 0, and alternate between 0 and 1. In other words, the only valid productions are 0, 010, 01010, 0101010, and longer strings that follow the same pattern.

In case you don't know what cyclic tag is, the language works like this: there is a queue of bits, which handles all the data storage for the program; and a program, which runs in an infinite loop forever until/unless the queue becomes empty. Each program command, known as a "production", dequeues a bit from the front of the queue, then enqueues either something (if a 1 bit was dequeued) or nothing (if a 0 bit was dequeued) to the back of the queue – the only freedom you have when writing the program is in specifying what exactly it is that gets enqueued. In the full version of cyclic tag, you can enqueue any arbitrary sequence of bits, but Grill Tag is restricted to using 010…010-style sequences ("grills") only.

Grill Tag is something that I've been looking at as a potential target for interpreter golf for several years now. However, back in 2019 when I created it, I wasn't able to determine whether or not it was Turing-complete; the language has a fundamental issue that make it very hard to program in (the number of 0s minus the number of 1s in any given string is equal to the number of 1s in the string that produced it, which means that programming in it requires controlling both the length and the 0/1 ratio of everything you use in order to keep control of which productions the 1s will expand).

I have very recently proven it Turing-complete, via creating a Turing-complete language (Genera Tag) in which you can write programs where every symbol expands in a very regimented way: every symbol always expands into two symbols in the next generation, each of those expands into another two symbols, and so on. Unfortunately, this construction tends to cause a useless explosion of no-ops (one no-op expands into two, then four, then eight, etc.) and makes programs run very slowly, but that is not an obstacle to Turing-completeness (and is probably not inherent in the language, but just trying to find anything that works was hard enough – I'm not immediately planning to go looking for something more efficient, even though it probably exists).

A decomposition of Grill Tag

As described above, Grill Tag has some fairly complex commands ("pop, and conditionally append … if a 1 bit was popped"). However, it is possible to break it down into smaller pieces, in a way that's quite suitable for a simple language like a Turing machine to handle.

The first observation (which is a standard transformation which I learned from Bitwise Cyclic Tag) is that instead of appending to the end of the queue all in one go, it is instead possible to split it up and push bit by bit: "dequeue a bit, and if it was a 0 bit, ignore any commands that would enqueue to the queue until the next bit is dequeued", "enqueue a 0 bit", "enqueue a 1 bit". The existence of the first command here effectively leads to two global states, which I think of as "blocked" and "extending"; in a blocked state, enqueuing commands do nothing, and in an extending state, they enqueue onto the back of the queue. This is still 3 commands, though, which is not ideal for implementing in a 2-state Turing machine (it's possible, but you need to add a lot of extra symbols to remember the half-command that you've seen already).

The second observation is that, in order to reach the far end of the queue, a Turing machine has to move its head over the entire queue as it does so (and generally speaking it's terser to have the "growing" end of the queue – the tail – at the opposite end from where the program is stored, so that it doesn't end up crashing into the program or forcing you to move the program out of the way). That gives it an opportunity to make simple changes as it goes, like, say, inverting the queue by flipping every bit in it. So instead of "dequeue and possibly block", "enqueue 0", "enqueue 1", it's possible instead to use "dequeue and possibly block", "enqueue 1", "invert the queue" (with an enqueuing of 0 implemented as an invert, enqueueing of 1, and another invert).

Look at what happens when using this decomposition on grills, rather than arbitrary strings:

• 0: dequeue/block; invert; enqueue 1; invert
• 010: dequeue/block; invert; enqueue 1; invert; enqueue 1; invert; enqueue 1; invert
• 01010: dequeue/block; invert; enqueue 1; invert; enqueue 1; invert; enqueue 1; invert; enqueue 1; invert; enqueue 1; invert
• etc.

Every second command is an invert command, so they can be paired with the preceding (or subsequent) commands in order to create a language that has only two commands, rather than three. I chose to pair them with the subsequent commands, meaning that Grill Tag can be implemented using only two commands:

• invert, then dequeue/block
• invert, then enqueue 1

(These commands actually give you a little more power than Grill Tag has – I made a catalogue of "languages that might be good to implement in low-powered languages and might be Turing-complete" back in 2019, and codenamed the full version of this language a vd vt. The extra power of a vd vt is not needed, though, with Grill Tag being Turing-complete on its own.)

Now that there are only two commands, it is possible for the Turing machine to remember which command it is executing via using its two states – it no longer needs to store a "half-command" onto the tape to remember what it's doing.

In the next section, I discuss how a vd vt (thus Grill Tag) is implemented in the Turing machine.

How the Turing machine works

This is a program of two halves, each of which does something sensible in isolation: the "left half" that uses the four symbols epPq, and the "right half" that uses the other ten symbols (including the "blank tape" symbol). The left half stores the program; the right half stores the queue, and implements the logic of Grill Tag.

Right half

Let's look at the right half of the program first. This is an implementation of all of Grill Tag other than the routines for determining what the next Grill Tag command is (which are implemented by the left half of the program).

The part of the tape used by this half of the program consists of a section of < and > symbols, followed by the tape, and possibly an o at the end (and beyond that is blank tape forever). The queue is encoded very directly: the head of the queue is towards the left-hand side of the tape (with the tail being at the right-hand side), and uses states represented by capital letters to encode 1 bits and states represented by lowercase letters to encode 0 bits. This part of the program is, in effect, a state machine; it remembers which state it is in by using different pairs of symbols to represent the queue (either iI, xX, or aA).

The only requirement that the right half of the program makes on the left half is that it can ask for commands. To ask for a command, it moves the tape head to the left out of its own section of the program, in state 0. The left half of the program responds with a command, returning the tape head in state 1 for an "invert and enqueue" command, or state 0 for an "invert and dequeue" command. There are a couple of quirks:

• After a returning a 0 command, the next "ask for a command" must, instead of returning the next command in the program, unconditionally return in state 1.
• Every second 0 command is implemented as unconditionally blocking the queue, rather than inverting and dequeuing a bit. This can be worked around by adding a sequence of dummy commands after each original 0 command: arbitrarily many 1 commands in the program, followed by one 0 command (to unblock the queue and dequeue the bit that should have been dequeued by the original 0 command).

These quirks are present because they allow the Turing machine to be smaller, and the workarounds don't hurt its universality. (In fact, each of the quirks has positive (or at least simplifying) impacts on both halves of the Turing machine, which is something of an amazing coincidence.) The reasoning behind them, and the way that they benefit the construction, will be explained in the appropriate sections below.

Apart from storing the queue, the right half of the Turing machine is effectively just one state machine, with a few hardcoded states.

Below, I take a look at every state. If you'd prefer to read the description in Jelly rather than English (maybe to have something to compare the Turing machine to), I have a Jelly implementation of the state machine available (which implements the program queue itself rather than asking the left half of the tape).

Idle

[head] >>>…>>>iIIii…Iii

The idle state happens a) at the start of the program, b) immediately after a 0 command. In this state, the right half of the Turing machine consists of an arbitrary number > symbols, followed by the queue written with iI (which could be any combination of lowercase i and capital I, reflecting the 0 and 1 bits that make up the queue).

In this implementation, a 0 command does not actually dequeue the first bit of the queue immediately. Instead, it sets the state to idle, and then allows the implementation of the idle state to handle dequeuing the bit of the queue.

The idle state is intended to run immediately after a 0 command, at a time when the left half of the tape is unconditionally returning control in state 1 (rather than reading a command from the program); the Jelly implementation unconditionally rotates the program to emulate this. That means that the idle state will be entered in state 1 (and this is the reason why the "always 1 after 0" quirk is helpful to the right-hand half – it ensures that the idle state is entered with the Turing machine in the correct state, necessary because the idle state wouldn't work properly in Turing machine state 0).

The Turing machine proceeds to move along the row of >, changing them to < and remaining in state 1 (per the rules for >). When it reaches the end of the row of >, one of three things happens:

• The next symbol could be i. In this case, the i becomes < and the head moves left, remaining in state 1. It will move to a <, which remains as <, moves the tape head to the left and changes to state 0. In state 0, the machine will change all the remaining < back to > and pass control to the left half in state 0.

  The machine has dequeued a 0 from the queue (a lowercase letter became a filler symbol <), and entered a double-blocked state (>>>…>>><<). This dequeues a symbol (as required), and blocks the queue (also as required when a 0 bit is dequeued).

• The next symbol could be I. In this case, the I becomes <, the head moves to the right, and the Turing machine enters state 0. In state 0, I becomes A and i becomes a, with the head moving to the right over the entire queue; the queue is becoming active. When it reaches the end of the queue, the Turing machine is in mark as extending state. This dequeues a symbol (as required), and does not block the queue (as required when a 1 bit is dequeued). The mark as extending state will handle marking the queue as extending.

• The queue could be empty – there might be no next symbol. In this case, beyond the last > will be an empty portion of the tape. The rule for empty tape is to halt in state 1, and we will be in state 1, so this correctly emulates a halt; Grill Tag halts when the queue is empty, and so does the Turing machine.

Blocked and double-blocked

Blocked:
[head] >>>…>>>><iIIii…Iii

Double-blocked:
[head] >>>…>>><<iIIii…Iii

The blocked and double-blocked states are very similar to each other. They handle situations where enqueue commands should be ignored, either because a 0 was dequeued, or due to the quirk where every second 0 command unconditionally blocks the queue.

A double-blocked state effectively says "the last 0 command blocked the queue, and the next 0 command should block the queue as well" – this is used to remember the fact that after a "regular" block of the queue when a 0 command dequeues a 0 bit in idle state, a "quirky" block is required on the next 0. A blocked state is one in which the last 0 command blocked the queue, but the next 0 command should be processed normally. As such, a 0 command changes the state from double-blocked to blocked or blocked to idle. 1 commands are entirely ignored in this state, because its entire purpose is to discard inverts and enqueues.

The blocked and double-blocked states read commands from the program – they are entered from the left half of the program. When either state is initially entered, it will be after a 0 command was read, so there will be a spurious 1 command arriving – but that quirk is irrelevant here, because the states discard 1 commands anyway. So all they actually have to do is to wait for a 0 command, and then remove one blockage upon receiving it.

There are two possibilities for what could happen, because the left half of the program could give this half control in either state 0 or state 1. In either state, the machine moves along the row of >, changing them to <, while remaining in the same state. When it reaches the <, there are two possibilities.

• In state 1, with a 1 command (or spurious-1-after-0) having been read from the program, the < remains unchanged and moves the head back to the left in state 0 (as per the rules for <). The rest of the row of > will be flipped back to <, and control will move to the left half of the program in state 0 (asking for a new program command). In other words, nothing changes other than a new command is being requested; in particular, the row of > and < ends up exactly as it started, so the machine will remain in blocked or double-blocked state (whichever it was in previously).
• In state 0, with a 0 command having been read from the program, everything is almost the same as in state 1; however, the rule for < in state 0 is to change to > and remain in state 0 (rather than remaining as < and changing to state 0). Thus, everything ends up the same, except that the machine has changed from double-blocked to blocked or blocked to idle state (because the only difference between the representation of those states is the number of < at the rightmost end of the >).

Mark as extending

<<<…<<<aAAaa…Aaa [head]

The mark as extending state is used to produce the correct representation of the queue for extending state. It is entered with the Turing machine in state 0, with the tape head in the blank space to the right of the tape.

This one works very simply: the rule for blank space (_ in the notation used by the interpreter I chose) in state 0 is to write an o, then move the head to the left in state 0. <aA's rules for state 0 all move the head to the left, with < becoming >, a becoming x, and A becoming X. The content of the queue has remained unchanged, the head has moved to the left in state 0 (reading the next command) and now the machine is in extending state.

Extending

[head] >>>…>>>xXXxx…Xxxo

The extending state is used to handle the "invert" half of commands, in cases where the queue is not blocked.

The extending state can be entered with the Turing machine in either state 0 or state 1 – a command has just been read from the program. The rules for >, x, and X are basically the same between the two states: they leave the Turing machine in the same state, but otherwise the state doesn't matter (it's just remembered so that the o at the end of the tape knows which command to implement the second half of).

>, x and X all move the head to the right, in both state 0 and state 1. > becomes <; x becomes A; and X becomes a. This mapping of lowercase to capital and capital to lowercase letters is inverting the sense of the queue; 0 bits become 1 bits and vice versa. The machine is now in enqueue or stop extending state.

Enqueue

<<<…<<<aAAaa…Aaao[head] in state 1

The enqueue state is entered from extending when a 1 command was read (and thus the Turing machine is in state 1), with the head over the o at the end of the tape. This is the simplest state in the entire machine, implemented by a single Turing machine transition: the o becomes an A (writing a capital letter at the end of the queue and thus enqueueing a 1 onto it), and the head moves to the right, onto the blank space beyond the queue. The Turing machine is now in mark as extending state, which will set the tape back to the format it was in before the "invert and enqueue" command ran – but the tape has now been inverted (because extending inverts the queue but mark as extending does not invert it back), and then an A (which becomes an X during mark as extending) was appended to the end.

Stop extending

<<<…<<<aAAaa…Aaao[head] in state 0

The stop extending state has an identical tape to enqueue, and the head is likewise over the o, but the Turing machine is in a different state. The purpose of this state is to bridge between the "invert" and "dequeue" halves of an "invert and dequeue" command – the "invert" half leaves the head at the rightmost end of the tape, but the "dequeue" command needs the head at the left, so the stop extending state is used to move the head into the correct location and appropriately re-encode the queue as it goes.

First, the o at the end of the queue deletes itself (which is what the rules for o do in state 0), switching to state 1 and moving the head back onto the last a/A.

Then, the head moves back leftwards over the queue, remaining in state 1 (a and A leave the state the same), with a becoming i and A becoming I – the queue encoding is going back to the encoding used for idle.

When the head moves back to the <, the logical thing to do (and the obvious thing to try to implement) would be to change the < back to >, and enter idle state (which implements the "dequeue" half of an "invert and dequeue" command). Unfortunately, golfing the Turing machine down to only 14 symbols ended up making the logical and obvious behaviour impossible to fit in, so the machine does something else instead; < in state 1 remains < and moves to the left, changing to state 0. The remaining < do change back to >, though (now that the machine is in state 0), so the resulting queue state consists of arbitrarily many >, an <, and the queue encoded with iI – in other words, this is blocked state!

This explains the quirk in which every second 0 command unconditionally blocks the queue, rather than doing an invert-and-dequeue like it's supposed to. If a 0 command runs when the queue is unblocked, then stop extending will end up inverting and then blocking the queue – it's the next 0 command that will actually do the dequeue (so the invert happens when it's supposed to, but the dequeue is delayed until the next 0 command). I couldn't find a terse way to avoid this behaviour. However, it was trivial to change the behaviour of a 0 command that blocks the queue to match (by making it double-block the queue rather than merely blocking it), in order to produce a construction in which every second block of 111…1110 in the program is consistently ignored (a quirk that is trivial to work around if you know it exists, simply by adding dummy commands).

That concludes the entire functionality of the right hand half of the program: enqueuing, dequeuing, inverting and halting. Apart from the weirdness of stop extending becoming blocked rather than idle (requiring a double-blocked state to compensate), everything is fairly straightforward and intuitive, and you can generally immediately understand what it's doing in the simulator.

Unfortunately, the left half will be a whole lot weirder and harder to understand – unlike the right half, it wasn't constructed, but rather discovered. Let's take a look at how it works.

Left half

Low-level behaviour

The left half of the program uses only 4 of the 14 symbols (e, p, P, q), and in fact only 6 of the 8 transitions are used (the other two do not have a rule defined because they never occur). Its purpose is to store the program, which it does by producing a specific, endlessly repeating stream of "state 0" and "state 1" signals; whenever the tape head enters it from the right (in state 0 – the right half always sets the state to 0 when giving the left half control), it will return the tape head to the right in either state 0 or state 1, whichever is the next element in the sequence.

First, let's take a look at what the rules actually do. The structure of the left half of the tape, when the tape head is outside it, is always of one of the following two forms (where p and P can be arbitrarily mixed):

eppPp…PPpp
eppPp…PPpq

Let's consider the first of these forms, and what happens when the tape head enters it in state 0. While moving to the left, the behaviour is fairly simple; p becomes P, and vice versa, with the machine remaining in state 0. When it reaches the e, it changes to state 1 and moves back to the right.

When moving rightwards, things are more complex. A P becomes a p, moves to the right, and remains in state 1; in other words, it undoes the inversion that was done when moving to the left, restoring the symbol to its original state. However, a p has a much weirder rule: it becomes a q and moves to the right, while switching to state 0. This has the effect of inverting the symbol to the right (because both p and P, when encountered in state 0, invert), and moving back to the left, onto the q. The q then becomes P and moves to the right in state 1, as "normal".

In other words, when moving to the right, P becomes p, and p inverts the symbol to the right and then becomes P. The result of this is that each cell, when the head leaves it, becomes set equal to the cumulative/running XOR of the original states (i.e. before they were inverted while moving to the left) of all the cells so far. This can be seen inductively. The base case is that the first cell starts out as the inversion of its original value, i.e. the XOR of all the cells so far, i.e. itself. For the inductive case, immediately before a cell changes to P (i.e. asserting that the XOR of all the cells so far was odd), it inverts the cell to its right, so it ends up being inverted three times and flipping (i.e. it was set to its original value XOR 1 = its previous value XOR that of all the cells to its left), whereas if a cell changes to p, the cell to its right is inverted only twice (leaving it at its original value, which must be the XOR of all the cells seen so far because the cells to its left XOR to 0).

People familiar with small Turing machines may be familiar with this general algorithm, of using a running XOR to store data. I learned about this pattern from Wolfram's (2,3) Turing machine, which is capable of doing a running-XOR and which uses this mechanism as its primary data storage. In fact, the rules used in this Turing machine were based on those from the (2,3) Turing machine, with all the relevant states and transitions being the same and used for the same purpose (the only difference is the addition of an e symbol to reflect the tape head, which is required because both transitions of the blank symbol are both being used for other purposes).

One quirk of this method of doing things is the way in which output is produced. When the last symbol becomes a p (i.e. all the symbols XOR to 0), the output uses a sensible protocol: it just reports the 1 via transferring control to the right half in state 1 (the state numbering is inverted, so a 1 command has to be stored as a 0 and vice versa, but this is not a significant issue because you can just invert the commands before encoding them). When the last symbol becomes a P (i.e. all the symbols XOR to 1), the head does indeed move to the right half in state 0, informing the right half of a 0 command – but this happens during the "invert the next cell" attempt, when the scan over the program storage has not yet finished. As a consequence, there is a q at the end of the program storage rather than a P. The next time control is transferred to the left half, it will finish the scan, changing to a P and transferring control to the right half in state 1 (which is the state that it would normally use to scan its next cell). The consequence is that each 0 is necessarily followed by a spurious 1. Fortunately, this quirk turned out to be easy to work around in the right-hand half of the program (and it actually simplifies the idle state a little, whilst not having negative consequences on anything else).

Encoding a running-XOR storage

Only one question remains: is it possible to encode a running-XOR storage such that iterating the running-XOR operation will produce any desired sequence of 0s and 1s?

The answer is "not any sequence: there's a restriction". It turns out that the period of a running-XOR storage will always be a power of 2. However, it is possible to construct a running-XOR storage that outputs 0s and 1s in any arbitrary pattern whose period is any arbitrary power of 2. Fortunately, this is a trivial restriction to obey: a quirk in the right half of the program means that every second block of 0111…111 in the output gets entirely ignored, and it is possible to pad out any of these blocks by inserting extra 1s until the length of the program becomes a power-of-2 number of commands.

As for encoding the actual sequence, the encoding algorithm is a fairly simple recursive algorithm:

• The sequence [0] encodes as [0];
• The sequence [1] encodes as [1];
• Otherwise, split the sequence into two equal-length halves A and B, and concatenate (the encoding of A pointwise-xor B) with (the encoding of B).

Proving that this works is a somewhat interesting induction, as the inductive hypothesis needs to include both the encoding rule itself, and the behaviour of a length-2ⁿ running-XOR memory if you invert all the storage cells (this causes the running-XOR memory to output the same period-2ⁿ sequence except that the last element in the sequence gets inverted). It is most intuitive to think of a running-XOR memory as a length-2ⁿ queue whose output is XORed with its input; when entering the memory normally, the last element is dequeued, and both output and enqueued back onto the queue; when entering the memory "inverted" (i.e. with the cells to its left XORing to 1), the last element is dequeued, inverted, and the inverted value is both output and enqueued back onto the queue. If you concatentate two such queues of length 2ⁿ together, then for 2ⁿ cycles, you get the XOR of the values dequeued from both queues, and after those cycles the later of the original queues has pointwise-XORed itself with the earlier (because the values it output were enqueued back onto it), whilst the earlier has its original values. The next 2ⁿ cycles will then output the XOR of the new values of the queues, i.e. the original value of the earlier queue XOR (the original value of the earlier queue XOR the original value of the later queue), which is just the original value of the later queue. Thus, concatenating a running-XOR memory representing A and a running-XOR memory of the same power-of-2 width representing B will output the sequence (A pointwise-XOR B) concatenate B (which is why the recursive encoding algorithm works).

Conclusions

This is a 2-state, 14-symbol strongly universal Turing machine (i.e. it starts from a finitely initialized tape and implements halting correctly). Finding small universal Turing machines is effectively a code golf problem, so it makes sense to post it on a code golf site.

Most of the machine actually functions fairly intuitively. The only confusing part is the running-XOR storage used for the program, but that can easily be encoded mechanically (and there is a program to do it) – it's generally considered that as long as the encoding algorithm can be proven to always halt and produce a finite result, it counts. (I prefer for the encoding algorithms to be primitive recursive, so that you can easily tell how long the encoding to take, but this one is (and in fact runs in O(n log n) time, so is even pretty fast.)

There is still quite a bit of slack in this construction; I ended up not needing to use 2 of the 28 transitions that were available, and it seems likely that many small variations of this machine are also going to be strongly universal. In 2019, I catalogued a range of small programming languages that could be encoded into 2-state 14-symbol Turing machines (the "Core BIX Queue Subsets"), although I didn't at the time mention what my motivation for selecting that particular set of languages was. a vd vt is not the only Core BIX Queue Subset that seems promising for Turing-completeness (although it did seem like the easiest to prove, and given that it took me almost 4 years, I have not been particularly inspired to try to work on one of the harder ones…); this Turing machine can easily be adapted to interpret any of the others.

I'd be interested to know whether anyone else has been trying to golf universal Turing machines recently (either strongly universal Turing machines like this one, or one of the less restrictive categories of universality). A quick search didn't turn up anything better for 2 states than 18 symbols, but it's quite possible that this sort of result would be in some obscure corner of the Internet that might be hard to find.

Answer 7

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.

Answer 8

Iterated Generalized Collatz Functions -> Python 2, 46 bytes

a,b,x,m=input()
while-~x%m:x=x/m*a[x%m]+b[x%m]

Call this function with a lists of m-1 a's and b's, the starting value x, and the divisor m, which collectively constitute a "program" for IGCF. Rather than taking a third array to indicate on which moduli to halt, this simply halts whenever the modulus is m-1. This simplification means it may take some extra effort to convert a given Fractran program into this variant, but it does save a couple of bytes in the interpreter.

Try it online! This TIO demonstrates how to add 5+5 with this language. The program a=[3],b=[0],m=2 does addition, and starting with 7776=2^5*3^5 eventually yields 59049=3^10.

Answer 9

x86 assembly (Intel syntax/MASM)-Brainfuck 2127 bytes.

Still golf able

.386
.model flat,stdcall
.stack 4096
include \masm32\include\masm32.inc
includelib \masm32\lib\masm32.lib
ExitProcess proto,dwExitCode:dword
.data
bfsrc BYTE 200 dup(0) 
bfcells BYTE 100 dup(0) 
loopStack DD 5 dup(0) 
charBuf BYTE 5 dup(0) 
newline BYTE 10,0 
prompt BYTE "$",0 
hr BYTE 50 dup('-'),0 
space BYTE ' ',0
.code
EvalBf proc
    start:
    invoke StdOut, addr prompt
    invoke StdIn, addr bfsrc,200
    cmp bfsrc,0
    je exit
    mov eax,0 
    mov ebx,0 
    mov ecx,0 
    processInstruction:
    cmp BYTE PTR bfsrc[ebx], '+'
    je plus
    cmp BYTE PTR bfsrc[ebx], '-'
    je minus
    cmp BYTE PTR bfsrc[ebx], '>'
    je fwd
    cmp BYTE PTR bfsrc[ebx], '<'
    je back
    cmp BYTE PTR bfsrc[ebx], '['
    je open
    cmp BYTE PTR bfsrc[ebx], ']'
    je close
    cmp BYTE PTR bfsrc[ebx], '.'
    je dot
    jmp processNextInstruction
    plus:
    inc BYTE PTR bfcells[eax]
    jmp processNextInstruction
    minus:
    dec BYTE PTR bfcells[eax]
    jmp processNextInstruction
    fwd:
    inc eax
    jmp processNextInstruction
    back:
    dec eax
    jmp processNextInstruction
    open:
    mov loopStack[ecx*4],ebx
    inc ecx
    jmp processNextInstruction
    close:
    dec ecx
    cmp BYTE PTR bfcells[eax], 0
    je processNextInstruction
    mov ebx,loopStack[ecx*4]
    inc ecx
    jmp processNextInstruction
    dot:
    mov dl, BYTE PTR bfcells[eax]
    mov BYTE PTR charBuf[0], dl
    mov BYTE PTR charBuf[1],0anything
    push eax
    push ecx
    invoke StdOut, addr charBuf
    pop ecx
    pop eax
    jmp processNextInstruction
    processNextInstruction:
    inc ebx
    cmp BYTE PTR bfsrc[ebx], 0
    je done
    jmp processInstruction
    done:
    invoke StdOut, addr newline
    mov eax, 0
    printNext:
    cmp eax, 100
    jge reset
    push eax
    invoke dwtoa, BYTE PTR bfcells[eax], addr charBuf
    invoke StdOut, addr charBuf
    invoke StdOut, addr space
    pop eax
    inc eax
    jmp printNext
    reset:
    invoke StdOut, addr newline
    invoke StdOut, addr hr
    invoke StdOut, addr newline
    jmp start

    exit:
    invoke ExitProcess,0
EvalBf endp
end EvalBf

Answer 10

Turtlèd interpreting CT, 49 bytes

I might be able to golf this

Also, this doesn't output anything useful. it just halts if and only if the given CT program halts.

this is one I made a while ago actually (then golfed some now)

!-l[*+.r_]' !l[ l]r[ u.(;d' u)d(1[ r].[ l])( r)+]

How it works:

Turtlèd uses grid cells. When I say "write something on the grid" I mean that a contiguous group of characters is placed on the grid. example

[ ][ ][ ][ ][ ][ ][ ]
[ ][H][E][L][L][O][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]

onto the program

data is inputted first:

!-l[*+.r_]' 

this is essentially a cat program. it writes the input onto the grid.

then the commands are inputted:

!

what it does with these commands:

these commands are "productions". if the leftmost data bit is a 1, it copies the production onto the end of the data string. otherwise nothing happens. then the leftmost data bit is removed, and it uses the next production with the next left most data bit. the program halts when there are no bits in the data string. A way to do these productions is to deal with the bits and end of productions separately. this is what our program does. it separately copies bits from the command string on to the end of the data string, and separately deletes bits from the datastring

on to how this program does it. after inputting the commands, the turtle/grid pointer moves back to the leftmost bit of the datastring. it then goes into a loop

[ u.(;d' u)d(1[ r].[ l])( r)+]

what it does in this loop, is it moves up from the leftmost datastring, and writes down the current command character (u.). if it is ;, the end of a production, it moves down and deletes the leftmost data bit beneath it and moves back up ((;d' u)). then, either way, it moves down one (d). if the bit there was not deleted, it means it must check whether to copy a bit from the commands at the end. so, if this character that is or was the leftmost databit is a 1, it will move to the end of the right end of the data string, copy the bit from the command string, and move back to the space left of the leftmost data bit ((1[ r].[ l])). now, it is either on the leftmost databit, which was a zero, or left of the leftmost databit. so, we move right if on a space (( r)). then, the command pointer is incremented so we will write down the next command in the next iteration of the loop. If there is no more datastring, this means we will be on a space and the loop will end. otherwise we rerun the loop.

Answer 11

Pip interpreting cyclic tag systems, 16 bytes

YqWyyPBg@++vXPOy

Takes the productions of the tag system as command-line arguments and the initial data string from stdin.

The above code is kinda hard to verify because it doesn't produce any output (so the only observable behavior is "terminates" vs. "doesn't terminate"). Therefore, here's an ungolfed version that outputs the data string after each step, and also terminates after 20 steps so TIO doesn't have to deal with tons of output from infinite loops: Try it online!

Cyclic tag systems

Cyclic tag systems are an extremely simple yet Turing-complete computational model. They consist of a list of productions that define operations on a data string. The productions and data string consist of 1's and 0's.

At each step, the leftmost character of the data string is removed.

• If the character is 1, the current production is appended to the right side of the data string.
• If the character is 0, nothing is appended.

In either case, the current production moves to the next production in the list, cyclically: if we were at the last production, we loop around to the first. Execution continues until the data string is empty.

Explanation

                  g is list of cmdline args; v is -1 (implicit)
 q                Read a line of stdin for the data string
Y                 and yank it into the y variable
  Wy              While data string is nonempty:
       g@++v       Retrieve the next production from g (using cyclic indexing)
             POy   Pop the first character of y
            X      String-multiply: result is the production if the first character of y
                   was 1, or empty string if it was 0
    yPB            Push that string to the back end of y

Answer 12

Perl → Three Star Programmer variant, 26 + 1 = 27 bytes

++$a[$a[$a[$_]]]for@F;redo

Try it online! (This link contains a header that exits the program after a set number of iterations (so that TIO doesn't time out), and to print the internal state every iteration (so that it does something observable).)

Run with -a (1 byte penalty, as you can fit it in before the -M5.010 to produce -aM5.010).

Specifically, this implements Three Star Programmer in which commands are separated by spaces and no comments are allowed in the file, without I/O extensions. (These changes make no difference to the language's Turing-completeness, obviously.) There isn't a proof of Turing-completeness for Three Star Programmer online, but it is Turing-complete (I've been sharing a sketch proof of its Turing-completeness with other esoprogrammers, but stopped working on the language when I discovered that it was actually fairly easy to program in once you'd gotten over the original shock).

The program doesn't really need much explanation; Three Star Programmer has a very simple specification, and this is a direct translation of it. The only subtle points: @F is the input to the program in array form (this is a consequence of -a); and redo will repeat the entire program as it's in an implicit loop (also a consequence of -a).

Answer 13

BF/P" implemented in a Turing Machine, 842 bytes

Transition table (linked because of length)

Transition table, less golfed version

Turing Machine simulator I used

This certainly isn't going to win any awards for length, but it's something I've always wanted to do, since BF is so similar to a Turing Machine. Each cell stores a value from 0x0-0xF. The width is however far the Turing Machine website can go without crashing your browser. The , and . functions (input and output) are not defined, so it's a bit more like P" than true BF.

To run it, paste the transition table into the Turing Machine simulator, set the input to some BF code, and press run.

The tape of the TM stores both the BF code and the BF data, with a single space in the middle. It keeps track of its position in the code by modifying the character that it is currently running ([ -> (, etc) and its position in the data with a ^ in front of the cell. Once it reads a command character, it moves until it hits the caret, moves one cell to the right, and performs the appropriate function. Then it goes back, looking for one of the "modified" command characters in the BF code, and moves on to the next one, repeating the whole process. Once it runs out of code, it halts.

The best way to understand how it works is by running the ungolfed version, putting it on step mode, and watching which lines lead to which others and what each state/block of lines does.

The golfed and ungolfed versions are exactly alike in terms of how they work, but the ungolfed version has more human-friendly names and is broken up into sections.

Answer 14

ResPlicate variant -> Python 2, 47 bytes

l=input()
while l:l=l[2+l[0]:]+l[2:2+l[0]]*l[1]

This function interprets a variant of ResPlicate

• for which a program is a python list of even length with even elements at even indices.
• with no I/O.
• for which trying to copy more values than exist in the remainder of the queue simply copies the remainder of the queue (i.e., the copied bit is not padded with zeroes to the required length).

The last change means that some ResPlicate programs (which meet the first condition) will not behave the same in this variant, but fortunately, the BCT interpreters do not require the removed functionality, and so the language remains TC.

Try it online! This TIO has a print wedged into it to show that it works and a header that kills the program after 1 second and an example that manages to generate more output than TIO can handle in that one second.

Answer 15

C implementing the (2,3) Turing Machine, 236 205 bytes (46 31 less if you don't care about awkward inputs)

Thanks to Appleshell for -11 bytes, VisualMelon for -12 bytes, and Johan du Toit for -7 bytes.

CeilingCat made a version that uses only 144 bytes, see here.

(I've added a few line breaks here so you don't have to scroll, but normally most of those would be deleted)

#define c char
j;i;k;c s,d[256];c main(){c*p=d+128;gets(d);
for(;k<256&&d[k];)d[k++]-=48;for(;++j<256;)
{c t=*p;*p=-t*t+(2-s)*t+1+s;p+=(s^t==0)*2-1;s=s?t%2:!t%3;
for(i=0;++i<256;)printf("%d",d[i]);puts("");}}

Try it online!

To use: Input a string of up to 256 ones, zeros, and twos to initialize the the tape. Any uninitialized values will be zero. (Values other than 0, 1, and 2 may cause undefined behavior.) The program will iterate over 256 steps. The number of steps it iterates over can be increased by modifying the code, but obviously that requires more characters.

It's a pretty long entry, but this is my first time doing one of these and I didn't use a dedicated golfing language. I had a lot of fun, even if it turned out longer than I expected.

A lot of the bytes are from dealing with input and output, and I lost a whole 42 bytes by making it accept 0, 1, and 2 instead of NUL, SOH, STX. (To change that, delete k; from the front and for(;k<256&&d[k];)d[k++]-=48; from the second line.)

The transistion table, especially the line *p=-t*t+(2-s)*t+1+s; (which sets the values on the tape) could probably be compressed more as well.

Answer 16

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.

Answer 17

Jelly → Couplet 2C variant, 3 bytes (infinite loop) or 4 bytes (halting)

ṃVß
ṃV¥Ƭ

Try it online!

Takes the initial string from the left-hand argument, and the replacement table from the right-hand argument (this is a map from numbers to strings encoded as a Jelly array, i.e. the element at index 1 is the key for value 1, and so on). Replacement strings are encoded as numbers in big-endian base n, where n is the size of the alphabet (which must be a power of 10).

The language implemented by this program is fairly powerful, and doesn't seem to exactly correspond to any of the existing languages, but is powerful enough to almost directly implement Couplet 2C via using replacement strings that consist of two copies of the same symbol (except at the end of the string, where they have an odd length), and using only symbols that have no leading zeroes. As such, it is trivially Turing-complete. The halt state is a "trivial infinite loop" (i.e. repeating a previous state) rather than having a separate halt symbol.

Explanation

ṃVß   ṃV¥Ƭ
ṃ     ṃ      Convert {the left argument} into digits
               in base (element count of {the right argument}),
               then map them using {the right argument} as the map
 V     V     Concatenate the digits of the result
  ß          Recursive call to the main function
         Ƭ   Loop until a previous result is repeated
        ¥      over the previous two commands

Jelly's ṃ is powerful enough that there's more than one way to combine it with a single other built-in, and a loop, in order to create a Turing-complete language. In an earlier answer, I used Ḍ, which created a very powerful language but had trouble halting. Using V creates a different very powerful language which finds halting much easier.

The basic idea is that when the size of the replacement table is a power of 10, ṃ is effectively splitting a number into substrings of a given length, and mapping those substrings through the replacement table; then V concatenates the resulting substrings. This operation is pretty similar to that done by a tag system, but doesn't implement tag systems directly because it doesn't remember the length of the string across iterations (whereas in, say, 2-tag, a common programming technique is to create a string that's either an odd or an even number of characters long to change which commands run in the next iteration). You can implement Couplet 2C pretty easily, though, by using two copies of the same symbol and rebracketing them:

xxyyzz0         string looks like this
x xy yz z0      using ṃ to convert into digits in base 100^n
aa bb cc dd0    using ṃ to map via a replacement table
aabbccdd0       using V to concatenate digits

The halt state of Ƭ – a repeat of a previous state – is a little tricky to achieve (and different from Couplet 2C's "natural" halt state), but by varying the behaviour of the end of the string it is possible to make it work. (One possible way to make the halt state work: compile a Turing machine into a cellular automaton into full 2C into Couplet 2C, and have the ends of the tape stay in a stable place by alternating between growing and shrinking, except when the tape head is there. This will quickly cause a halt of the Turing machine to enter a repeat of a previous state in the 2C program.)

One potential controversy with this answer: V in Jelly is overloaded: when acting on a list of numbers, it concatenates their digits; but when acting on a string, it is an eval function. It isn't being used as an eval function here, but it is still a little uncomfortable to use a builtin that is represented by the same character as the eval builtin (and I think internally Jelly implements it by concatenating the string representations of the numbers and then using an eval to convert the number from its string format to an actual number). I assume the question was intending to ban the use of eval to evaluate code, as opposed to parsing integers from strings, but it is possible that it ends up inadvertently disallowing this style of answer.

Answer 18

Jelly → 2-Tag system, 8 bytes

µḢị⁴⁸;Ḋß

Try it online!

I have a bounty going favouring practical languages, but thought I might as well try to win the original task while I was at it (as I can't exactly win my own bounty).

Implements a variant of tag systems with no halt state, as it isn't needed for Turing completeness. The states are numbered from 1, consecutively, and the initial string comes before the program.

For example, Wikipedia gives an example of a tag system {a,b,c}, {a → bc, b → a, c → aaa} with initial string aaa; in this input format, that's [1,1,1], [[2,3],[1],[1,1,1]]. (Tag systems don't have a fixed syntax, and this seems like a reasonable way to do it.)

The TIO link has an added Ṅ ("write internal state and a newline to stdout") in order to show that the program is in fact working.

Explanation

µḢị⁴⁸;Ḋß
           {implicit: initialise internal state from first argument}
µ          Disregard the second command-line argument by default
 Ḣ         Take the first element, removing it from the internal state
  ị⁴       Use the value to index into the second argument
    ⁸;     Prepend (the rest of) the internal state
      Ḋ    Discard the first element of the internal state
       ß   Loop forever

Answer 19

Vyxal interpreting Thue variant, 1 byte

¢

Try it Online!

¢ is a builtin that performs infinite replacement. When given a string \$s\$, a list of targets \$[t_1, t_2 ... t_n] \$, and a list of replacements \$[r_1, r_2 ... r_n]\$ it replaces \$t_1\$ with \$r_1\$, \$t_2\$ with \$r_2\$ and so on, repeatedly, until no more replacements can be performed.

As it turns out, this is sufficient for Turing-Completeness as it can interpret a variant of Thue. A Thue program consists of a series of replacement rules, which replace one string with another, and an initial string to which the replacements are performed.

The only difference between this language and Thue is that, while the Thue spec mandates a single replacement be performed at a time, this language performs as many replacements as possible in parallel. This turns out to be equivalent, though, as it can be treated as performing a series of replacements.

This language takes input as a list of replacement strings, a list of target strings, and the initial string on which replacements are to be performed. The TIO link contains a binary-to-unary converter.

Answer 20

Röda implementing Fractran, 114 112 106 bytes

1 byte saved thanks to @fergusq by rearranging parameters

f&n,a{x=1{x=0;(a/" ")()|[_/`/`]|[parseInteger(_[0],_1[1])]|{|q,w|{n*=q/w;x=1}if[n%w<1,x<1]}_,_}while[x>0]}

Try it online!

Call the function like so: f reference_to_input program. The output will be stored in the location of the input.

Answer 21

Lua interpreting Brainf***, 467 bytes

b,r,a,i,n,s=0,io.read,{0},1,1,"><+-.,[]"c,f=r(),{function()n=n+1;a[n]=a[n]or 0;end,function()n=n-1;a[n]=a[n]or 0;end,function()a[n]=a[n]+1;end,function()a[n]=a[n]-1;end,function()io.write(string.char(a[n]))end,function()a[n]=io.read():byte()end,function()i=a[n]~=0 and i or c:find("]",i)end,function()if a[n]~=0 then b,x=1,""repeat i=i-1 x=c:sub(i,i)b=x=="["and b-1 or x=="]"and b+1 or b until b==0 and x=="["end end}repeat f[s:find(c:sub(i,i),1,1)]()i=i+1 until i>#c

I know there's still some slimming down I can do later, but here's where my first pass ended. Takes the brainf code from standard input.

Answer 22

Clojure, 82 81 bytes (Turing Machine)

Update: removed a space from t{} s.

#(loop[p 0 t{}s 1](if-let[[S M N](%[(or(t p)0)s])](recur(+ p M)(assoc t p S)N)t))

Implements the Turing Machine as a loop, returns the tape when the halting state is reached. In state transition rules this is indicated by ommitting the transition state. This settins N to nil and the subsequent if-let will abort as the corresponding state transition is not found from the input hash-map %. Actually any value for this state will do, such as :abort, 0 or -1.

Ungolfed with an example 3-state 2-symbol busy beaver from Wikipedia.

(def f #(loop[pos 0 tape {} state 1]
          (if-let [[sym move next-state](%[(get tape pos 0)state])]
            (do (println [pos tape state])
                (recur(+ pos move)(assoc tape pos sym)next-state))
            tape)))

(f {[0 1] [1  1 2]
    [0 2] [1 -1 1]
    [0 3] [1 -1 2] 
    [1 1] [1 -1 3]
    [1 2] [1  1 2]
    [1 3] [1  1]})

{0 1, 1 1, -1 1, -2 1, -3 1, 2 1}

Try it online.

On a single core of 6700K this runs the 5-state 2-symbol busy beaver (47.1 million steps) in about 29 seconds, or 1.6 million steps / second.

Answer 23

C (clang) interpreting Brainfuck, 187 182 bytes

t[99],*p=t,c,i,l;f(*t){for(i=0;c=t[i];i++){c^62?c^60?c^43?c^45?c^46?c^44?c^91:(*p=getchar()):putchar(*p):--*p:++*p:--p:++p;if(c==93&&*p)for(l=1;l>0;)c=t[--i],c==91?l--:c==93?l++:0;}}

Try it online!

Answer 24

><> interpreting "Craw><>", 4 bytes

iiip

Try it online!

Craw><> is a language I just made up defined by the above implementation. It's almost obvious that you can translate all ><> programs into Craw><>. Pretty sure someone had this idea before me.

Answer 25

Clojure, 75 bytes (Cyclic tag system)

Update 1: replaced some? with nil?.

Update 2: Fixed a missing S in else branch of if s.

#(loop[[p & P](cycle %)[s & S]%2](if(nil? s)S(recur P(if s(concat S p)S))))

Implements the cyclic tag system, returns nil if the program halts, loops forever otherwise. Clojure really shines here with infinite lazy sequences (such as cycle) and destructuring. Ones and zeros are indicated as true and false values. When the data string runs out s becomes nil.

Ungolfed:

(def f #(loop[[p & P] (cycle %) [s & S] %2 i 5]
          (do
            (pprint [p (concat [s] S)])
            (if (and (some? s) (pos? i))
              (recur P (if s (concat S p) S) (dec i))))))

Example results:

(f [[false]] [true true])
[[false] (true true)]
[[false] (true false)]
[[false] (false false)]
[[false] (false)]
[[false] (nil)]

(f [[false true true] [true false] [true false true]] [true])
[[false true true] (true)]
[[true false]      (false true true)]
[[true false true] (true true)]
[[false true true] (true true false true)]
[[true false]      (true false true false true true)]
[[true false true] (false true false true true true false)]

Answer 26

CJam → ResPlicate Variant, 15 14 13 bytes

^{-1 byte thanks to @ais523}

l~{(/((*+e_}h

The variant is the same as the one in this answer, except that the number of items taken off the queue is one less than the top number on the queue.

The l~{ ... }h part just takes an array as input and repeats until that array is empty.

Explanation for the main loop:

    e# Stack:             | [3 2 1 1 2 2 2 1]
(   e# Pop first element: | [2 1 1 2 2 2 1] 3
/   e# Split chunks:      | [[2 1 1] [2 2 2] [1]]
(   e# Pop first:         | [[2 2 2] [1]] [2 1 1]
(   e# Pop first:         | [[2 2 2] [1]] [1 1] 2
*   e# Repeat array:      | [[2 2 2] [1]] [1 1 1 1]
+   e# Concatenate:       | [[2 2 2] [1] 1 1 1 1]
e_  e# Flatten:           | [2 2 2 1 1 1 1 1]

Answer 27

Headass interpreting BCT, 84 bytes

U[{U+)]ORO:RO};N-)-E:{UON)}:]+E.{UO+):};UP{N)UO}:E.U[{U+)]ORO:RO};UO^{N)UO}:D)E:]O[E

Try it here! Code will need to be copied, and executed like this:

srun("U[{U+)]ORO:RO};N-)-E:{UON)}:]+E.{UO+):};UP{N)UO}:E.U[{U+)]ORO:RO};UO^{N)UO}:D)E:]O[E",<your bct program here>)

where the program is formatted as individual bits delimited by comma, and the code separated from the datastring by a -1. for example, the bct program 111000|111 would be executed like this:

srun("U[{U+)]ORO:RO};N-)-E:{UON)}:]+E.{UO+):};UP{N)UO}:E.U[{U+)]ORO:RO};UO^{N)UO}:D)E:]O[E",1,1,1,0,0,0,-1,1,1,1)

The program prints bits deleted by the 0 command, but this can be disabled for -1 byte by removing the P in the program. Halts by throwing a Headass error.

I chose classic Headass over it's younger, ascii-based brother Headascii because it allowed me to take -1s as inputs, which is conveniently close to 0, as is 1.

Before I get into the explanation I just want to say that if I were allowed to choose a TC subset of this lang I'd be golden, having to validate the input cost me like 5 bytes T_T

Code breakdown:

U[{U+)]ORO:RO};N-)-E:{UON)}:]+E     Block 0

U[                                  Store the first command
  {          }                      Loop
   U+)                              If the next number in the program is -1,
      ]O                              Push the stored command to the end of the
                                       program string
        RO                            Push the -1 to the end of the program string
          :   ;                       And then leave the loop
                                    Else
           RO                         Leave it alone and continue
               N-)                  If the data string is empty
                  -E                  Go to block -1 (exit with error)
                    :               Else
                     {UON)}:          Ready the rest of the data for the next block
                            ]+E       Then go to either block 1 or 2 based on if
                                       the stored command was 0 or 1 respectively

.{UO+):};UP{N)UO}:E                 Block 1 (handles 0)

.                                   Block separator
 {UO+):};                           Read through the numbers until after the -1 delimiter
         UP                         Print and discard the first bit of the data string
           {N)UO}:                  Ready the rest of the data for the next block
                  E                 Go to block 0

.U[{U+)]ORO:RO};UO^{N)UO}:D)E:]O[E  Block 2 (handles 1)

.                                   Block separator
 U[{U+)]ORO:RO};                    Same as in block 0
                UO^                 Store the first bit of the data string
                   {N)UO}:          Ready the rest of the data for the next block
                          D)        If the first bit of the data string is 0
                            E         Then go to block 0
                             :      Else
                              ]O      Push the stored bit from the command string
                                       to the end of the data string
                                [E    Go to block 0

My heftiest explanation yet. Whew!

Answer 28

Chip, 20+3 = 23 bytes (Rule 110)

AZZ
>}/a
`)\'E~Zte*f

+3 for flag -z

Try it online!

This submission isn't perfect, as Chip doesn't (yet) have any looping ability, so the output must be passed in as the input to simulate multiple generations, with something like this (of course, you could run that loop indefinitely, and Chip can handle arbitrarily long input, so this combination is Turing Complete).

This implementation take input and given output in the form of ASCII 0s and 1s. The logic here is as follows:

p := value of left neighbor cell    AZZ
q := value of current cell          AZ
r := value of right neighbor cell   A

q' := ((r xor q) and p) or          >}/a
      ((r or q) and ~p)             `)\'

The remainder of the elements are for housekeeping: e*f causes ASCII numeral output, and E~Zt terminates execution two bytes after the input is exhausted (since the width grows by 2 each generation).

Answer 29

Vyxal implementing "add minimum to transpose", 4 bytes

{:g+

Try it Online! (prints each iteration)

{    # Forever
   + # Add to each
 :g  # Corresponding element of minimum row

See this answer for a better explanation of why this is turing-complete.

Answer 30

JavaScript interpreting Rule 110, 131 bytes (99 bytes?, 28 bytes?)

a=(p,q,r)=>q+r+q*r+p*q*r
b=l=>{r="";for(i=0;i<l.length-2;i++)r+=a(l[i],+l[i+1],+l[i+2])%2;return r}
c=(l,n)=>!n?l:c(b(0+l+0),n-1)

As you can see, the code defines 3 functions, a, b and c. Perhaps it's possible to save bytes by combining them in 1 function (I don't see how), but it's good that there separate because each of them already fulfills this challenge in some sense.

Function atakes 3 numbers as input and computes some weird polynomial of them. When these 3 numbers are 0or 1they can bee seen as Rule 110 cells. The parity of the output of a can then be seen as the value of the middle cell in the next generation. So in some sense, this simple function is already a Rule 110 'interpreter' (28 bytes):

a=(p,q,r)=>(q+r+q*r+p*q*r)%2

We can then create a new function b that evaluates a on every character of a string of ones and zeros. This bis then, in a better way than a, a Rule 110 interpreter. Taking mod 2 after the evaluation of a saves brackets (99 bytes):

a=(p,q,r)=>q+r+q*r+p*q*r
b=l=>{r="";for(i=0;i<l.length-2;i++)r+=a(l[i],+l[i+1],+l[i+2])%2;return r}

To actually compute a function with Rule 110, the user must specify the starting state and the number of generations after which the output will 'appear'. We can make a third function c that takes a string of ones and zeros, and a positive integer n, that then evaluates bon the string, ntimes. Like this we can really see Rule 110 as a programming language, where a program is an intitial state and a number n, and the output is the state after ngenerations. The function cis now an actual interpreter for that programming language so the final code for this challenge is what I presented above.