Tell me more ×
Arqade is a question and answer site for passionate videogamers on all platforms. It's 100% free, no registration required.
up vote 78 down vote favorite
9

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
10  
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
17  
Obligatory xkcd reference: xkcd.com/505 – Agos Apr 17 '11 at 9:22

2 Answers

up vote 53 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
aww yeah, Bytejacker. – Mana♦ Apr 17 '11 at 1:48
26  
Awesome. Incredibly sad, but awesome. – Rushyo Apr 17 '11 at 12:23
1  
@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
2  
@Kortuk uh oh, EE.SE people (¬_¬) – Nick T Mar 24 '12 at 22:27
1  
Imagine if an enderman takes one of those grass blocks. I wanna see you debugging it. – Jeffrey Mar 5 at 1:47
show 3 more comments
up vote 4 down vote

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

Edit: Here's a neat example of an implementation:

share|improve this answer

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.