Take the 2-minute tour ×
Arqade is a question and answer site for passionate videogamers on all platforms. It's 100% free, no registration required.

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

share|improve this question
12  
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
21  
Obligatory xkcd reference: xkcd.com/505 –  Agos Apr 17 '11 at 9:22
1  
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
add comment

3 Answers

up vote 62 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.

share|improve this answer
29  
Awesome. Incredibly sad, but awesome. –  Rushyo Apr 17 '11 at 12:23
2  
@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
3  
@Kortuk uh oh, EE.SE people (¬_¬) –  Nick T Mar 24 '12 at 22:27
1  
@NickT, Dropped by to see what you had been up to since I had not seen you around and had to say something. I just want to see this guy make a 5 stage piped mips processor with ram and lets play some games! Hope all goes well. –  Kortuk Mar 25 '12 at 1:39
7  
Imagine if an enderman takes one of those grass blocks. I wanna see you debugging it. –  Jefffrey Mar 5 '13 at 1:47
show 3 more comments

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:

share|improve this answer
4  
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. –  rodarmor Dec 1 '13 at 9:54
    
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 at 12:58
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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