# Turing-Complete Language Interpreter

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!

• I would also recommend a rule that the implemented language must be different than the language that you use to implement it, to prevent trivial eval-like solutions. Feb 25, 2017 at 22:12
• Actually, you might want to just ban eval commands/functions, as some languages have built-ins to evaluate code in another language. Feb 25, 2017 at 22:15
• @arodebaugh For future challenges, you can post your idea in the sandbox where you can get feedback and iron out details like that before the challenges goes live and gets answered. Feb 25, 2017 at 22:23
• OK, you should probably be a little more specific and say something like "You may not simply execute code, via any method" to avoid other trivial answers like the Bash + perl one. Feb 25, 2017 at 23:06
• Relevant video: On The Turing Completeness of PowerPoint (SIGBOVIK) May 7, 2017 at 0:52

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

• And the usual "rundown of things that are meaningful and would save bytes but the Brachylog interpreter can't handle it": the first five bytes could be expressed as ~dp (which doesn't mean quite the same thing but is close enough to still be Turing-complete), except that the Brachylog interpreter doesn't know how to reverse d yet.
– user62131
May 17, 2017 at 0:55

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

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

• After thinking about this some more, we could get this down to three bytes using ḋ and ṙ rather than × and ị; the resulting language is not quite the same language as Tip, but it's pretty similar and almost certainly Turing-complete for the same reason. Unfortunately, ḋ isn't implemented in M, and I can't find any way to make Jelly do arbitrary-precision calculations when either of the inputs is a non-integer real number. If anyone knows any other golfing languages where this construction might work, though, feel free to give it a go. Jul 12, 2018 at 14:37

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

• If I'm understanding correctly, this has a fixed board size? In that case, I think it can't be Turing-complete, can it? May 8, 2017 at 19:00
• Any particular call to the function has a fixed board size, but that board size can be arbitrarily large. (Note that the second half of the post describes an example of observing the code in action, not the actual code itself.) May 8, 2017 at 23:23
• What I'm saying is that for GoL to be Turing-Complete, it has to be capable of a pattern that grows infinitely. (Such as a glider gun.) If this implementation can't grow the array from one step to another, but wraps it toroidally instead, then it fails the infinite-growth test. May 17, 2017 at 20:23
• That's a reasonable perspective, to be sure. But implementations of programming languages on physical computers don't even satisfy that test! One could be content with a (hypothetical) sequence of physical computers with more and more memory, each one capable of calculating one more value of that computable function; at that point, though, one should be equally content with a (hypothetical) sequence of inputs to such a GoL program. May 17, 2017 at 20:27

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

• Dang nice job. I was hoping to win the bounty but good job May 12, 2017 at 21:52

# 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  • Usually assembly answers are counted in the size of the resulting machine code, so you don't need to golf the assembly at all, just minimize the number/size of instructions. May 11, 2017 at 4:56 • @RobertFraser uhh I don't know how to count that :P May 11, 2017 at 10:13 • Actually, at first I somehow read the title as "x86 asm implemented in Brainfuck" and was kinda impressed :) May 11, 2017 at 20:06 • @Quetzalcoatl That would be impressive May 11, 2017 at 20:45 • pls golf variable/label names ty Apr 15, 2018 at 0:56 # 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. # 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. • Try to golf this more! Feb 28, 2017 at 17:29 # 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  • hey, I just remembered that you don't need to input the data string; it can just be 1 source: esolangs links to this arxiv.org/abs/1312.6700 . I will edit my answer soon, and if this helps your answer you should (tbh your input seems golfy enough actually) May 8, 2017 at 10:50 # 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).

• I think it makes more sense for the arrow to mean "is reduced to" than "interprets". May 11, 2017 at 2:31

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

• The post length limit is more than enough to fit the transition table Apr 15, 2018 at 0:57

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

• Why not l=input()? Would be a byte shorter. May 8, 2017 at 1:29

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

• Wow, and this is your first code golf here! Wonderful! May 7, 2017 at 3:47
• You can shorten the global variable declarations like this: k,j;c s,d[256]; (int is implicit in C, then you can also move i to global declaration to save 3 bytes more) May 7, 2017 at 4:34
• @Appleshell Thanks, I'll do that.
– a52
May 7, 2017 at 5:48
• You can move the string null-terminal check inside the for loop. In-lining k++ and removing the {} saves a couple more bytes: for(;k<256&d[k];)d[k++]-=-48; Because j is just a timekeeper (value never used) you can replace it (and i) with k by counting backwards: you know k==256 after the first loop, so count down to zero in the second for(;k>0;), which leaves k==-1, so the last loop can become for(;++k<256;). (Disclaimer: I usually golf C#, but this seemed to compile). May 7, 2017 at 6:43
• @VisualMelon I determined the problem. I needed to use k<256&&d[k], not &, because d[k] was being evaluated at k==256. Also, since k was no longer guaranteed to be 256 after that loop, I had to reset it afterwards in order to guarantee 256 steps. (If you (that is, VisualMelon) have any other suggestions, we should probably put them in chat so we don't get too many comments)
– a52
May 8, 2017 at 17:17

# 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}, {abc, ba, caaa} 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


# Röda implementing Fractran, 114112 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.

• The semicolon after e[1] is redundant. Also you can save one byte by changing parameter order: f&n,a. May 7, 2017 at 6:35
• @fergusq Thanks for the f&n,a trick, and I was just about to remove that semi-colon when you commented :) May 7, 2017 at 6:38

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

• +1 for the brains, it's always fun when golfers assign to a list of variables. May 8, 2017 at 23:48

## 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}


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.

## 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!

• Welp, there was bound to be an answer using BF. May 8, 2017 at 18:07
• 214 bytes Fixes some bus so Eric Bosman's mandelbrot works Sep 21, 2021 at 14:41
• @ceilingcat I don't think that it needs to be a fully functional interpreter to be Turing complete ;-)
– jdt
Sep 21, 2021 at 15:25
• @jdt Sure, but clause 6: "Each submission must be fully working that means that every feature that your chosen language has must be present". Mandelbrot is a core feature of the lang :P Feb 4 at 5:29

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

• "translate", no - Jo King's tried and failed. But the subset of programs you can create is definitely TC. Aug 11 at 12:22
• @emanresuA That's about inputting a fish program, clear the interpreter, and put the fish program there at the same time. That's much harder!
– null
Aug 11 at 12:42

## 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)]


# CJam → ResPlicate Variant, 1514 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]

• You don't really need the increment here. Just specify that block lengths should be incremented by 1 in the original program; that doesn't hurt the Turing-completeness of ResPlicate (there are TC constructions in which block lengths and repeat counts are never mixed with each other).
– user62131
Jun 11, 2017 at 6:22

# 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!

• while debugging, a fun little issue i kept running into was that ), used for branching, would branch properly but always set the current register to 0. That shocked me, because I didn't remember there being any (more) bugs in my language. It turns out im so used to golfing that I'd forgotten the original use of the command. in general, A(B) is used to compare A to B. The default value for A if ( is not present just happens to be 0. I hate debugging i hate debugging i hate debugging i hate debugging i ha Feb 4 at 5:33

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

# Vyxal implementing "add minimum to transpose", 4 bytes

{:g+


Try it Online! (prints each iteration)

{    # Forever
:g  # Corresponding element of minimum row


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

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

• Does this compute 110 with the proper background? An earlier answer of mine was deleted because it did not have the background. May 7, 2017 at 1:04
• @WheatWizard the background is part of the input, your answer shouldn't have nbeen deleted for that May 7, 2017 at 1:06
• The background should be infinite, can you take infinite input? May 7, 2017 at 1:11
• @WheatWizard it doesnt have to be infinite, it has to be able to be made arbitrarily big, and it can May 7, 2017 at 1:13
• Rule 110 is not Turing complete if you decide the generation in advance, and you do need infinite input in the construction I know about. Even if someone found a construction with a finite initial state, you cannot know the memory or time needed before the program runs, because then you could solve the Halting Problem. May 7, 2017 at 14:42

# JS -> Newline 854 bytes

(function(d){var b=0;var n=!0;var c=[];var h=[];var e=0;var l=[];var m=0;var f=2;var a=0;var g=!1;var k=function(a){if(a===1)return!1;if(a%2===0&&a!==2)return!1;if(a%3===0&&a!==3)return!1;if(a%5===0&&a!==5)return!1;if(a%7===0&&a!==7)return!1;for(var b=7;b<d.round(d.sqrt(a))+1;b++)if(a%b===0)return!1;return f=a,!0;};var j=0;var i=0;var o=function(q){var o=d.__split(q,'\n');d.println(o);for(var n=0;n<o.length;n++)if(n>=f^2&&n<=f+1^2&&k(n)){f=n;for(var p=0;p<o[n].length;p++){if(o[n]==='+'&&(a+=c[b],b++),o[n]==='-')if(g===!0&&a<=0)break;else a-=c[b],b++;if(o[n]==='*'&&(a*=c[b],b++),o[n]==='/'&&(a/=c[b],b++),o[n]==='s'&&(a=d.sqrt(a)),o[n]==='%'&&(a%=c[b],b++),o[n]==='a'&&l.push(a),o[n]==='g'&&(a=c[b],b++),o[n]==='q'&&c.push(a),o[n]==='i'&&a++,o[n]==='d')if(g===!0&&a<=0)break;else a--;o[n]==='r'&&(g=!0),o[n]==='w'&&(g=!1),o[n]==='['&&(j=n),o[n]===']'&&a>0&&(n=j,h[e]--),o[n]==='{'&&(i=n),o[n]==='}'&&h[e]>0&&(n=i,h[e]--),m=a,o[n]==='k'&&e++;}}};});


• I think you posted this answer to the wrong challenge. Did you mean to post it to this challenge?
– user62131
May 8, 2017 at 15:20
• In that case, you need to modify the implementation to aim for the different victory condition; this is code-golf, not popularity-contest. For example, you have plenty of variable names that could clearly be shorter, meaning that this solution isn't a serious contender. You could perhaps delete it for now and then undelete it when you have time to golf it.
– user62131
May 8, 2017 at 15:26
• Nonetheless, answers that don't make a serious attempt to optimize for the victory condition are against the rules. That's a good enough reason to delete it until you can make it conform to the rules.
– user62131
May 8, 2017 at 15:30
• You can combine all the var statements: var b=0,n=!0,c=[],h=[],e=0,l=[],m=0,f=2,a=0,g=!1; May 16, 2017 at 22:32
• Pls remove all var ty Apr 15, 2018 at 0:56

# JavaScript: Lambda Calculus (123 114)

Represented using Debruijn Indicies in Duples.

V=function b(c,d){if(!isNaN(c)){for(;--c;)d=d[1];return d[0]}return 0==c[0]?e=>b(c[1],[e,d]):b(c[0],d)(b(c[1],d))}


The S combinator is [0, [0, [0, [[3, 1], [2, 1]]]]]

K is [0, [0, 2]]

I is [0, 1]

Edit: Shaved 9 bytes by replacing "number"==typeof c with !isNaN(c)

# Nim: Three Star Programmer, 138 bytes

import strutils
var
r:array[100,int]
while 1<0:
for i in 0..<p.len:r[r[r[p[i].parseInt]]]+=1


A simple implementation, with 100 memory locations, enough for demonstration purposes.

## Clojure, 87 bytes (Rule 110)

Credit for the parity code goes to Jens Renders! I was really struggling on how to express this and I was going to go with converting [p q r] from binary to an integer and use a lookup table.

#(iterate(fn[S](for[[p q r](partition 3 1(concat[0]S[0]))](mod(+ q(* q(+ 1 p)r)r)2)))%)


Here partition and Clojure's destructuring makes the logic application quite simple. This function returns an infinite sequence of states, so the caller is responsible to take as many as they need or just nth to skip to a specific state. If paddings with zero were two elements instead of just one then the tape would constantly grow, avoiding boundary issues. Now it stays the original width.

Example:

(def f #(iterate(fn[S](for[[p q r](partition 3 1(concat[0]S[0]))](mod(+ q(* q(+ 1 p)r)r)2)))%))

(pprint (take 5 (f '(0 0 0 0 0 1 1 1 0 0 1 0 0))))
((0 0 0 0 0 1 1 1 0 0 1 0 0)
(0 0 0 0 1 1 0 1 0 1 1 0 0)
(0 0 0 1 1 1 1 1 1 1 1 0 0)
(0 0 1 1 0 0 0 0 0 0 1 0 0)
(0 1 1 1 0 0 0 0 0 1 1 0 0))

• If you only ever work with the original width, this can't possibly be Turing-complete, because it only has finite memory storage. (In fact, all known Turing-completeness constructions from Rule 110 require the "padding" that's used to expand the width as the program goes on to have a pattern specified from user input, and different on the left and on the right, rather than just using zeroes.)
– user62131
May 8, 2017 at 15:36
• I see, that makes its simulation rather difficult then. Clojure's cycle would be able to construct the infinite padding pattern, but executing the first step would take infinite amount of time :/ May 8, 2017 at 15:44
• Come to think of it, it wouldn't be too tricky to take those padding pattern as additional arguments and expand the simulated tape by 1 block left and right. The speed of information here is 1 block / iteration so we just need to simulate the "light cone" around the central block which has the asymmetric structure. (CMIIW) May 8, 2017 at 16:00

# APL (Dyalog Unicode), 15 bytesSBCS

Full program which implements a generalised one-dimensional cellular automaton executor. This includes Rule 110 which is Turing complete. Prompts stdin for initial state, number of iterations (or ≡ to continue until stable or {⍵≡⎕←⍺} to display all intermediate values until stable), and rule-set.

⎕∊⍨∘(⊢∘⊂⌺3)⍣⎕⊢⎕


Try it online! (4 iterations of Rule 110)

⎕ prompt for initial state and

⊢ yield that (separates the state from the number of iterations)

⍣⎕ prompt for number of iterations and apply the following function that many times:

() apply the following tacit function:

⌺3 get all length-3 neighbourhoods (with info on whether they are at the edge) and apply the following tacit function to each pair:

⊂ enclose the neighbourhood

∘ and

⊢ yield that (discarding the info about being at the edge)

∘ then

∊⍨ check if they are members of

⎕ prompt for list of neighbourhoods leading to being on in the next iteration