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?
Ask HN: What is the smallest possible language?
1–10 of 11 posts
Re: Ask HN: What is the smallest possible language?
#2The mov operator in x86 assembly is technically Turning Complete onto itself [1]. I believe you'd be hard pressed to get smaller then that.
Re: Ask HN: What is the smallest possible language?
#3The 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
I'm impressed. What I'm thinking more of is what types of functions and specific functions do you need? So also add, subtract...
Re: Ask HN: What is the smallest possible language?
#4A 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 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).
Re: Ask HN: What is the smallest possible language?
#5The 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
I'm impressed. What I'm thinking more of is what types of functions and specific functions do you need? So also add, subtract...
All you need is mov (and, technically, a single unconditional branch in each program). You can implement add, subtract, etc. using that.
Perhaps the question you want an answer to is not actually the one you asked? In any case, a programming language does not have to look like ALGOL. Most of the very simple ones do not.
Re: Ask HN: What is the smallest possible language?
#6This type of language is called a Turing Tarpit: http://esolangs.org/wiki/Turing_tarpit
Re: Ask HN: What is the smallest possible language?
#7The 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
I'm impressed. What I'm thinking more of is what types of functions and specific functions do you need? So also add, subtract...
Nothing about Turing completeness requires the presence of functions. You're probably looking for a useful language, but you'll have trouble making that criterion rigorous.
Re: Ask HN: What is the smallest possible language?
#8[deleted]
Re: Ask HN: What is the smallest possible language?
#9This type of language is called a Turing Tarpit: http://esolangs.org/wiki/Turing_tarpit
Why the SKI “programming” language is not included in the list of examples? http://en.wikipedia.org/wiki/SKI_combinator_calculus
Re: Ask HN: What is the smallest possible language?
#10A 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 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).
The lisp example is actually exactly what I'm looking for!