Ask HN: What is the smallest possible language?

by sethhovestol on 2/6/2014, 12:31:38 AM with 9 comments
I've been thinking about languages recently, and I'm wondering what the most simple Turing complete language needs. By this I mean flow control (if/else) and recursion or loops (or the beloved Y combinator). What would be a list of these features?

  • by valarauca1 on 2/6/2014, 12:34:27 AM

    The mov operator in x86 assembly is technically Turning Complete onto itself [1]. I believe you'd be hard pressed to get smaller then that.

    [1] http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

  • by tsuyoshi on 2/6/2014, 12:48:06 AM

    This type of language is called a Turing Tarpit: http://esolangs.org/wiki/Turing_tarpit

  • by ggchappell on 2/6/2014, 12:43:17 AM

    A fair amount of research has gone into this question. A number of very simple Turing-complete languages are known.

    valarautical mentioned x86 mov. Another is an assembly-ish language with two instructions: (1) decrement and (2) branch if <= 0. Another is the Lambda Calculus. The only thing it has is lambda (and variables and function application, if you want to consider those to be things). Lisp with only QUOTE, ATOM, EQ, CAR, CDR, CONS, and COND is another example (and perhaps even that list is not minimal; I'm a little vague on this).

  • by dbieber on 2/16/2014, 6:58:17 AM

    Are you familiar with Brainfuck? http://en.wikipedia.org/wiki/Brainfuck It has just 8 symbols and looks like gibberish when you actually write it. I think you'll find it to be an amusing example of a very small Turing complete language.