57
\$\begingroup\$

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!

\$\endgroup\$
18
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ Commented Feb 25, 2017 at 22:12
  • 1
    \$\begingroup\$ Actually, you might want to just ban eval commands/functions, as some languages have built-ins to evaluate code in another language. \$\endgroup\$ Commented Feb 25, 2017 at 22:15
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ Commented Feb 25, 2017 at 22:23
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Feb 25, 2017 at 23:06
  • 2
    \$\begingroup\$ Relevant video: On The Turing Completeness of PowerPoint (SIGBOVIK) \$\endgroup\$
    – sergiol
    Commented May 7, 2017 at 0:52

37 Answers 37

1
2
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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)

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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))
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$
    – user62131
    Commented May 8, 2017 at 15:36
  • \$\begingroup\$ 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 :/ \$\endgroup\$
    – NikoNyrh
    Commented May 8, 2017 at 15:44
  • \$\begingroup\$ 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) \$\endgroup\$
    – NikoNyrh
    Commented May 8, 2017 at 16:00
1
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.