154

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)?

Improve this question
6
  • 20
    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, 2011 at 8:39
  • 36
    Obligatory xkcd reference: xkcd.com/505
    – Agos
    Apr 17, 2011 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, 2013 at 20:11
  • 1
    @Phoshi luckily that's not the case anymore!
    – tuskiomi
    Nov 8, 2016 at 18:04
  • 2
    @Agos Another relevant XKCD: xkcd.com/1636
    – Fabian Röling
    Nov 20, 2017 at 13:29

5 Answers 5

Reset to default
27

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!

Improve this answer
7
  • 1
    Minecraft isn't exactly 3-space though. There's a height limit. Does this limit its turing completeness?
    – user170887
    Dec 19, 2016 at 18:45
  • 3
    @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, 2016 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?
    – user170887
    Dec 19, 2016 at 18:58
  • @XeroOl I'd watch that tutorial. =)
    – Daniel Wagner
    Dec 19, 2016 at 19:19
  • 1
    @XeroOl I know I'm 3 years too late; but in the most strict sense, no finite system can be Turing complete.
    – adrian
    Jan 28, 2019 at 3:27
95

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.

Improve this answer
4
  • 44
    Awesome. Incredibly sad, but awesome.
    – Rushyo
    Apr 17, 2011 at 12:23
  • 4
    What is the speed of the CPU? 0.5 Hz?
    – user1381
    Oct 1, 2011 at 18:43
  • 5
    @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, 2012 at 16:46
  • 44
    Imagine if an enderman takes one of those grass blocks. I wanna see you debugging it.
    – Shoe
    Mar 5, 2013 at 1:47
11

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:

Improve this answer
4
  • 23
    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, 2013 at 9:54
  • 3
    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, 2014 at 12:58
  • 6
    By this logic, computers aren't Turing Complete either.
    – BlueRaja - Danny Pflughoeft
    Feb 16, 2015 at 1:27
  • 2
    -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, 2015 at 18:18
3

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).

Improve this answer
1
  • 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, 2016 at 13:25
0

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)

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .