What is the minimal set of language features/structures that make it Turing-complete?

  • 24
    Won't it be better to just google it? en.wikipedia.org/wiki/Turing_completeness
    – aml90
    Commented Jan 29, 2012 at 17:04
  • 2
    Hi Curious Cat, welcome to Programmers! Calls for lists aren't on-topic here: I've removed that part out of your question. That said, this quest is extremely broad: is there a specific problem you're working on that has you thinking about Turing-completeness?
    – user8
    Commented Jan 29, 2012 at 21:02
  • 3
    @amalantony: Just as a footnote.
    – Bobby
    Commented Jan 30, 2012 at 9:24
  • For a computer-science perspective, see here.
    – Raphael
    Commented Apr 17, 2017 at 11:15

7 Answers 7


A Turing tarpit is a kind of esoteric programming language which strives to be Turing-complete while using as few elements as possible. Brainfuck is perhaps the best-known tarpit, but there are many.

  • Iota and Jot are functional languages with two and three symbols, respectively, based on the SK(I) combinator calculus.

  • OISC (One Instruction Set Computer) denotes a type of imperative computation that requires only one instruction of one or more arguments, usually “subtract and branch if less than or equal to zero”, or “reverse subtract and skip if borrow”. The x86 MMU implements the former instruction and is thus Turing-complete.

In general, for an imperative language to be Turing-complete, it needs:

  1. A form of conditional repetition or conditional jump (e.g., while, if+goto)

  2. A way to read and write some form of storage (e.g., variables, tape)

For a lambda-calculus–based functional language to be TC, it needs:

  1. The ability to abstract functions over arguments (e.g., lambda abstraction, quotation)

  2. The ability to apply functions to arguments (e.g., reduction)

There are of course other ways of looking at computation, but these are common models for Turing tarpits. Note that real computers are not universal Turing machines because they do not have unbounded storage. Strictly speaking, they are “bounded storage machines”. If you were to keep adding memory to them, they would asymptotically approach Turing machines in power. However, even bounded storage machines and finite state machines are useful for computation; they are simply not universal.

Strictly speaking, I/O is not required for Turing-completeness; TC only asserts that a language can compute the function you want, not that it can show you the result. In practice, every useful language has a way of interacting with the world somehow.

  • For imperative languages, are simple variables enough? I was under the impression that some kind of collection (e.g. arrays or linked lists) would be necessary.
    – luiscubal
    Commented Jan 12, 2014 at 23:08
  • 1
    @luiscubal you need to be able to specify an arbitrary amount of data. With simple variables you can represent the amount of data that the variables themselves have. What if you need to represent N+1 different pieces of data. One could argue that with tricks like Fractran plays, you could do it even in simple variables... but that's not quite what you're asking.
    – user40980
    Commented Jan 13, 2014 at 18:07
  • Isn't it required the language must support ENDLESS loops?
    – sergiol
    Commented Feb 23, 2017 at 2:15
  • Re, "every useful language has a way of interacting with the world." Algol 60 did not have any defined way of interacting with the world. All of your I/O in an Algol 60 program was done by calling library functions, and the library functions could be completely different in different implemenations. But, I hereby recuse myself from any discussion of whether or not Algol 60 was "useful." Commented Aug 9, 2017 at 17:41
  • Isn't imperative point 1. actually two parts? Conditional branching, and the ability to loop/move?
    – naught101
    Commented Mar 10, 2022 at 22:52

From a more practical standpoint: if you can translate all programs in a Turing-complete language into your language, then (as far as I know), your language must be Turing-complete. Therefore, if you want to check whether a language you designed is Turing-complete, you could simply write a Brainf*** to YourLanguage compiler and prove/demonstrate that it can compile all legal BF programs.

To clarify, I mean that in addition to an interpreter for YourLanguage, you write a compiler (in any language) that can compile any BF program to YourLanguage (keeping the same semantics, of course).

  • 13
    Yes, that would definitely be the most practical way to approach it. </sarcasm> Commented Jan 29, 2012 at 18:27
  • 16
    @RobertHarvey has a point, but the general idea is quite vital. Brainfuck is proven to be turing-complete and very simple as programming languages go. For non-esoteric programming languages, implementing a brainfuck interpreter may be much easier and faster than giving a rigorous proof out of nowhere (I can implement BF in a couple of lines of Python, but I'm not sure where to start with a formal proof that Python is turing complete); and dozens of esoteric brainfuck-inspired languages are known to be turing complete because it's known how they map to brainfuck.
    – user7043
    Commented Jan 29, 2012 at 18:53
  • 8
    @RobertHarvey: Why not? Surely someone designing their own language would be able to write a BF compiler to it (if it was imperative, and find a suitable other language otherwise).
    – Komi Golov
    Commented Jan 29, 2012 at 18:53
  • 7
    @delnan: You will have to prove, however, that your BF interpreter correctly implements the BF specification, IOW you will have to prove that your BF interpreter is, in fact, a BF interpreter and not an interpreter for a BF-like language that might or might not be Turing-complete. Commented Jan 31, 2012 at 1:52
  • 2
    @DarekNędza, that's just a natural consequence of how Turing Completeness is defined; any extension of a Turing Complete language will still be Turing Complete.
    – Komi Golov
    Commented Oct 9, 2015 at 14:59

A system can only be considered to be Turing complete if it can do anything a universal Turing machine can. Since the universal Turing machine is said to be able to solve any computable function given time, Turing complete systems can, by extension, also do so.

To check to see if something is Turing complete, see if you can implement a Turing machine inside it. In other words, check to see if it can simulate the following:

  1. The ability to read and write "variables" (or arbitrary data): Pretty much self explanatory.
  2. The ability to simulate moving the read/write head: It isn't enough to just be able to retrieve and store variables. It must also be possible to simulate the ability to move the tape's head in order to reference other variables. This can often be simulated within programming languages with the usage of array data structures (or equivalent) or, in the case of certain languages such as machine code, the ability to reference other variables through the use of "pointers" (or equivalent).
  3. The ability to simulate a finite state machine: Although not mentioned often, Turing machines are actually a variation of the finite state machines often used within AI development. Alan Turing said the purpose of the states is to simulate a person's "various modes of problem solving".
  4. A "halt" state: Although it's often mentioned a set of rules must be able to repeat itself in order to count as being Turing complete, that isn't really a good criteria since the formal definition of what an algorithm is state algorithms must always eventually conclude. If they can't conclude in some way, either it isn't Turing complete, or said algorithm isn't a computable function. Turing complete systems that technically can't conclude due to the way they work (like game consoles, for example) get around this limitation by being able to "simulate" a halting state in some fashion. Not to be confused with the "halting problem", an undecidable function that proves it's impossible to build a system that could detect with 100% reliability if a given input will cause another system to not conclude.

These are the true minimum requirements for a system to be considered Turing complete. Nothing more, nothing less. If it can't simulate any of these in some fashion, it's not Turing complete. The methods other people proposed are only means to the end as there's several Turing complete systems that doesn't have those features.

Note that there's no known way to actually build a true Turing complete system. This is because there's no known way to genuinely simulate the limitlessness of the Turing machine's tape within physical space.


You can't tell if it'll loop infinitely or stop.


Explanation : Given some input, it's impossible to tell in every case (using another Turing machine) if the thing is going to loop infinitely or eventually going to stop, except by running it (which gives you an answer if it does stop, but not if it loops!).

This means that you have to be able to store a potentially unlimited amount data in some way - there has to be an equivalent to the infinite tape, no matter how convoluted! (Otherwise there are only a finite number of states and then you can check if you've been through that state previously and eventually stop). Generally, Turing machines can grow or shrink the size of their state by some controllable means.

Since Turing's original universal Turing machine has an unsolvable halting problem, your own Turing complete machine must also have an unsolvable halting problem.

Turing complete systems can emulate any other Turing complete system, so if you can build an emulator for some well known Turing complete system in your system, that proves that your system is also Turing complete.

For instance, suppose you want to prove that Snakes & Ladders is Turing complete, given a board with an infinitely repeated grid pattern (with a different version on top and left side). Knowing that the 2-counter Minsky machine is Turing complete (which has 2 unlimited counters and 1 state out of a finite number), you can construct an equivalent board where the X and Y position on the grid is the current value of the 2 counters and the current path is the current state. Bang! You just proved that Snakes & Ladders are Turing complete.

  • 2
    I don't buy that argument. Just because the halting problem is undecidable for Turing machines does not directly imply that every notation that allows you to specify a program for which the halting problem is undecidable is Turing complete. Only the inverse is obviously true: If the notation is Turing complete, then it is of course possible to write programs for which the halting problem is undecidable.
    – 5gon12eder
    Commented Dec 16, 2015 at 19:11
  • 1
    It's a necessary condition. If you can decide for every program whether it halts then the language isn't Turing complete.
    – gnasher729
    Commented Dec 17, 2015 at 12:04

A programming language is turing complete if you can do any calculation with it. There isn't just one set of features that makes a language turing complete so answers saying you need loops or that you need variables are wrong since there is languages that has neither but are turing complete.

Alan Turing made the universal turing machine and if you can translate any program designed to work on the universal machine to run on your language it's also Turing complete. This also works indirectly so you can say language X is turing complete if all programs for turing complete language Y can be translated for X since all universal turing machine programs can be translated to a Y program.

The time complexity, space complexity, easy of input/output format and easy of writing any program is not included in the equation so such machine can theoretically do all calculations if the calculations are not halted by power loss or Earth being swallowed by the sun.

Usually to prove turing completeness they make an interpreter for any proven to be turing complete language but for it to work you need means of input and output, two things that are really not required for a language to be turing complete. It's enough that your program can alter it's state at startup and that you can inspect the memory after the program is halted.

To make a successful language it needs more than turing completeness though and this is true for even turing tarpits. I don't think BrainFuck would have been popular without , and ..

  • 2
    "A programming language is turing complete if you can do any calculation with it." That's the Church-Turing thesis, not what makes a language Turing-complete.
    – Rhymoid
    Commented May 20, 2014 at 13:47
  • @Rhymoid So you mean nothing is turing complete unless you can make an interpreter? Ie. lambda calculus is not turing complete even if it's turing equalent?
    – Sylwester
    Commented May 20, 2014 at 15:58
  • 1
    I'm still looking for an authoritative definition of the terms Turing-equivalent and Turing-complete (and Turing-powerful). I've already seen too many cases, from people on message boards to researchers in their own friggin' papers, who interpret these terms differently.
    – Rhymoid
    Commented May 20, 2014 at 16:12
  • Anyway, I interpret 'Turing-complete' as being simulation equivalent to a Universal Turing Machine (UTM; which, in turn, is capable of simulating any Turing machine -- hence 'universal'). In Turing's paper from 1936, where he introduced his machines, he defined the notion of a UTM, and gave a sketch of a proof that UTMs are simulation equivalent to Church's lambda calculus. By doing so, he proved that they had the same computational power. The Church-Turing thesis asserts, put simply, that "that's all the computational power you'll ever get".
    – Rhymoid
    Commented May 20, 2014 at 16:19
  • It has two formal definitions for Turing completeness page of Wikipedia. One requires I/O the other doesn't. The one that doesn't say that a machine is turing complete if it can calculate every Turing-computable function. That puts lambda calculus back to being turing complete since you can easily make a equalent program in lambda calculus that calculates the same as any turing machine programs.
    – Sylwester
    Commented May 20, 2014 at 16:19

One necessary condition is a loop with a maximum iteration count that is not determined ahead of the iteration, or recursion where the maximum recursion depth is not determined ahead. As an example, for ... in ... loops as you find them in many newer languages are not enough to make the language turing complete (but they will have other means). Note that this doesn't mean limited number of iterations or limited recursion depth, but that the maximum iterations and recursion depth must be calculated ahead.

For example, the Ackermann function cannot be a computed in a language without these features. On the other hand, a lot of highly complex and highly useful software can be written without requiring these features.

On the other hand, with every iteration count and every recursion depth calculated ahead, not only can it be decided whether a program will halt or not, but it will halt.


i know this is not the formally correct answer, but once you take the 'minimal' out of 'Turing-complete' and put 'practical' back where it belongs, you'll see the most important features that distinguish a programming language from a markup language are

  • variables
  • conditionals (if/then...)
  • loopage (loop/break, while...)

next come

  • anonymous and named functions

to test these assertions, start out with a markup language, say, HTML. we could invent an HTML+ with variables only, or conditionals only (MS did that with conditional comments), or some kind of loop construct (which in the absence of conditionals would probably end up as something like <repeat n='4'>...</repeat>). doing any of these will make HTML+ significantly (?) more powerful than plain HTML, but it would still be more of a markup than a programming language; with each new feature, you make it less of a declarative and more of an imperative language.

the quest for minimality in logic and programming sure is important and interesting, but if i had to teach n00bies young or old 'what is programming' and 'how to learn to program', i'd hardly start out with the full breadth and width of the theoretical foundations of Turing completeness. the whole essence of cooking and programming is doing stuff, in the right order, repeating until ready, as your mom did it. that about sums it up for me.

then again, i never finished my CS.

  • 2
    If you are not sure, you should research it first. fractran is turing complete, as is brainf*ck. Note also that html 5 + CSS 3 is Turing complete because it can implement rule 110.
    – user40980
    Commented Jan 12, 2014 at 15:41
  • 1
    yesyesyes i know. but all the examples given are more or less esoteric (while maybe interesting or surprising), my answer was a pragmatic one, and very probably not minimal at all. i think it's important to point that out—this page was #1 when searching for Turing-completeness on google, the answers here are IMHO of little use for, say, a n00bie who wants to know what distinguishes HTML from PHP or Python. i mean, brainfck is not called brainfck for no reason.
    – flow
    Commented Jan 12, 2014 at 22:11

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.