[OkayPhysicist]

Any system that can represent a NAND gate is Turing complete. In Minecraft, connecting two inputs to the same branch of redstone wire is an OR gate, and a redstone torch on a block acts as a NOT gate. Two inputs, both inverted, into an OR gate gives a NAND.

[kibwen]

It's even slightly simpler than that, NOR is also functionally complete, so you can just negate the OR.