Minecraft has the redstone wires mechanism that can be used to build circuits. Is Minecraft Turing-Complete, i.e. can it be used to simulate a Turing Machine (if we ignore the problem of infinite memory)?

  • 18
    There's also the problem of not having infinite space - go more than a few chunks away and bits of your thing will get unloaded – Phoshi Apr 17 '11 at 8:39
  • 33
    Obligatory xkcd reference: xkcd.com/505 – Agos Apr 17 '11 at 9:22
  • 4
    It depends on what you understand under Turing complete. With the formal definition Minecraft is not Turing complete. But neither is your computer or any other real device because you need infinite memory for that. In the more common sense that Turing complete is being used, meaning it is a universal computer then yes, Minecraft is Turing complete. – Plankalkül Sep 20 '13 at 20:11
  • @Phoshi luckily that's not the case anymore! – tuskiomi Nov 8 '16 at 18:04
  • 1
    @Agos Another relevant XKCD: xkcd.com/1636 – Fabian Röling Nov 20 '17 at 13:29
up vote 88 down vote accepted

Notch himself has said in an interview that yes, the Redstone blocks in Minecraft allow construction of Turing-complete Machines.

A couple people have even constructed ALUs and CPUs, for instance the following one. The creator was planning on adding a memory array to allow programming it.

  • 38
    Awesome. Incredibly sad, but awesome. – Rushyo Apr 17 '11 at 12:23
  • 3
    What is the speed of the CPU? 0.5 Hz? – rightfold Oct 1 '11 at 18:43
  • 4
    @WTP, that seemed about the speed he could clock it at, but based on the delay on some of the register changes I am sure it would have race conditions in that case and probably needs a much slower speed or a pipeline. – Kortuk Mar 24 '12 at 16:46
  • 31
    Imagine if an enderman takes one of those grass blocks. I wanna see you debugging it. – Shoe Mar 5 '13 at 1:47

I know this question is a bit old, but all the other answers seem quite complex to me, while the answer itself can be quite simple: nor gates are universal, redstone torches are nor gates, and all graphs can be embedded in 3-space; so yes, Minecraft is Turing complete!

  • Minecraft isn't exactly 3-space though. There's a height limit. Does this limit its turing completeness? – XeroOl Dec 19 '16 at 18:45
  • 2
    @XeroOl Good point. Still, I think it's okay: using the analogy from the link, it's not important that book pages be able to go in any direction, just that there be infinitely many directions for them to go. In minecraft (ignoring the "only loaded chunks" restriction, as I think most other answers ultimately are doing too) you still have that, at least. – Daniel Wagner Dec 19 '16 at 18:51
  • Do you think it would be possible to use a flatworld as an infinite memory tape and build a slime block machine that acts like a turing machine? – XeroOl Dec 19 '16 at 18:58
  • @XeroOl I'd watch that tutorial. =) – Daniel Wagner Dec 19 '16 at 19:19

I'm afraid that any finite-sized redstone building (even in an infinite world) can only store as much bits of data as the amount of redstone put in it, therefore it's not Turing Complete.

If you're talking about infinite-sized redstone buildings, well, you can quite easily build conway's game of life in minecraft, which is turing complete. The "quite easily" won't work if we were in a 2D Minecraft space, and there, well, that's an interesting question :)

Here's a neat example of an implementation:

  • 17
    It is true that any finite system is not turing complete, but that is usually ignored when talking about turing completeness. For example, any modern computer with a finite amount of storage is not turing complete. – Casey Rodarmor Dec 1 '13 at 9:54
  • 2
    If Conway's Game of Life is Turing complete and it works in Minecraft, wouldn't that automatically make Minecraft Turing complete? – The Guy with The Hat Feb 11 '14 at 12:58
  • 3
    By this logic, computers aren't Turing Complete either. – BlueRaja - Danny Pflughoeft Feb 16 '15 at 1:27
  • -1; redstone is absolutely turing complete. As BlueRaja said, if minecraft isn't considered TC due to finiteness, then all computers are not TC – Daenyth Oct 7 '15 at 18:18

Vanilla Minecraft is most likely Turing Complete due to the combination of command block cloning (for unbounded memory), teleportation (for chunk loading), and block update detection (a component for self-identifying cloning devices).

  • Minecraft's resdstone is not a turing complete machine, and by itself cannot construct a turing complete machine - as explained in the video - but redstone is a turing comple language, as in: it can be used to write programs of arbitrary length that can do all that a turing machine can do with program of arbitrary length. And when I say arbitrary length, I particulary mean it is finite. This is how turing completness is understood for programming languages. Otherwise we would have to say that there is no such thing as a turing complete language because the language cannot create memory. – Theraot Jan 12 '16 at 13:25

Yes with spawner/end portal(to duplicate item) for infinite memory. Here I don't say about command block because if commands are considered there can only be finite entities(UUID 128 bit)

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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