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

Nim: Three Star Programmer, 138 bytes

import strutils
var
  r:array[100,int]
  p=readFile(readLine(stdin)).split('\n')
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.

Answer 2

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

Answer 3

APL (Dyalog) → Fractran variant, 15 bytes

(⊃0~⍨××0=1|×)⍣≡

Try it online!

The function takes in the rationals as a list of numbers rather than two lists containing the numerator and the denominator, and outputs the result if the program ends. This implements a variant of Fractran that has the rational 1/1 (= 1) at the end of the program. The 1 has no effect on the Turing-completeness (as far as I understand) because the input to the program only lands on the 1 when none of the other rationals work, and when it does, the input is not changed. This is only used so that the function knows when to end.

The TIO link runs the function for 2 iterations (so that you can see the output as the program does not end) on the first input, and runs the second input until completion, after which it returns the output.

(⊃0~⍨××0=1|×)⍣≡ takes the list of rationals as the left argument, to be referred to as ⊣, and the input as the right argument, to be referred to as ⊢

(⊃0~⍨××0=1|×) function train

• 1|× get the part after the decimal point (modulo 1) of the product × of ⊣ and ⊢

• 0= does it equal 0?

• ×× multiply this result with ⊣ × ⊢, wherever the rational × ⊢ is not an integer, it is replaced with 0

• 0~⍨ remove all 0s

• ⊃ get the first element

⍣ loop until ≡ input does not change, note that the result of (⊃0~⍨××0=1|×) is reused as the input, so if it stops changing (as a result of the 1 at the end) the program stops

Answer 4

Python 3 interpreting I/D machine, 88 87 bytes

x=input()
l=[]
p=0
while 1:
	for i in x:l+=[0];a=i=="I";print(l);l[p]+=1*a;p=l[p]*(a<1)

Try it online!

This code probably can be golfed.

See ais523's answer for an explanation of how I/D machine works and why is it turing-complete.

Ungolfed

x = input()
l = []
p = 0
while 1:
    for i in x:
        l += [0]
        a = i == "I"
        print(l)
        l[p] += 1 * a
        p = l[p] * (a < 1)

Answer 5

Haskell, 50 bytes

p#r=([p#(n*r`div`d)|(n,d)<-p,n*r`mod`d<1]++[r])!!0

Try it online!

Implements FRACTRAN. Function (#) takes two arguments; a list of tuples containing the (numerator, denominator) pairs that specify a fractran program, and the input number