Code Golf: Shortest Turing-complete interpreter.

Posted by ilya n. on Stack Overflow See other posts from Stack Overflow or by ilya n.
Published on 2009-06-28T00:32:28Z Indexed on 2010/06/13 19:42 UTC
Read the original article Hit count: 371

I've just tried to create the smallest possible language interpreter. Would you like to join and try?

Rules of the game:

  • You should specify a programming language you're interpreting. If it's a language you invented, it should come with a list of commands in the comments.
  • Your code should start with example program and data assigned to your code and data variables.
  • Your code should end with output of your result. It's preferable that there are debug statements at every intermediate step.
  • Your code should be runnable as written.
  • You can assume that data are 0 and 1s (int, string or boolean, your choice) and output is a single bit.
  • The language should be Turing-complete in the sense that for any algorithm written on a standard model, such as Turing machine, Markov chains, or similar of your choice, it's reasonably obvious (or explained) how to write a program that after being executred by your interpreter performs the algorithm.
  • The length of the code is defined as the length of the code after removal of input part, output part, debug statements and non-necessary whitespaces. Please add the resulting code and its length to the post.
  • You can't use functions that make compiler execute code for you, such as eval(), exec() or similar.

This is a Community Wiki, meaning neither the question nor answers get the reputation points from votes. But vote anyway!

© Stack Overflow or respective owner

Related posts about computer-science

Related posts about code-golf

  • Code Golf: Collatz Conjecture

    as seen on Stack Overflow - Search for 'Stack Overflow'
    Inspired by http://xkcd.com/710/ here is a code golf for it. The Challenge Given a positive integer greater than 0, print out the hailstone sequence for that number. The Hailstone Sequence See Wikipedia for more detail.. If the number is even, divide it by two. If the number is odd, triple… >>> More

  • Code Golf - p day

    as seen on Stack Overflow - Search for 'Stack Overflow'
    The Challenge The shortest code by character count to display a representation of a circle of radius R using the *character, followed by an approximation of p. Input is a single number, R. Since most computers seem to have almost 2:1 ratio you should only output lines where y is odd. The approximation… >>> More

  • Code Golf - PI day

    as seen on Stack Overflow - Search for 'Stack Overflow'
    The Challenge The shortest code by character count to display a representation of a circle of radius R using the *character. Followed by an approximation of pi Input is a single number, R Since most computers seem to have almost 2:1 ratio you should only output lines where y is odd. The approximation… >>> More

  • Code Golf: Triforce

    as seen on Stack Overflow - Search for 'Stack Overflow'
    This is inspired by/taken from this thread: http://www.allegro.cc/forums/thread/603383 The Problem Assume the user gives you a numeric input ranging from 1 to 7. Input should be taken from the console, arguments are less desirable. When the input is 1, print the following: *********** *********… >>> More

  • Code Golf: Tic Tac Toe

    as seen on Stack Overflow - Search for 'Stack Overflow'
    Post your shortest code, by character count, to check if a player has won, and if so, which. Assume you have an integer array in a variable b (board), which holds the Tic Tac Toe board, and the moves of the players where: 0 = nothing set 1 = player 1 (X) 2 = player 2 (O) So, given the array b… >>> More