Universal Turing Machine implemented in Minecraft redstone logic

This is a Universal Turing Machine implemented in Minecraft. The video is running at 60 times normal speed, in other words, each minute is an hour of run time. The total run for this tape took just over 13 hours.

A Universal Turing Machine is a Turing Machine with a fixed action table that can be used to simulate any other Turing Machine. Both the description of the other Turing Machine and its data are encoded onto the tape of the Universal Turing Machine. So a Universal Turing Machine can calculate any computable function.
http://en.wikipedia.org/wiki/Universal_turing_machine

I have drawn from the particular machine that was created by Paul Rendell for his Game of Life implementation, because I had similar goals - that it be reasonably simple, but also not take too many cycles to perform the simulation. Apart from reversing the tape and changing the symbol encoding, it is essentially the same machine, with 13 states and 8 symbols.
http://rendell-attic.org/gol/utm/utmprog.htm

The Turing Machine being simulated simply duplicates a string of symbols, effectively a unary multiply by 2. The data being operated on is a string of three symbols. The entire run takes over six thousand actions of the Universal Turing Machine, not bad by UTM standards, but painfully slow in this Minecraft implementation. Most of the time is spent shuttling back and forth between the program section and the data section on the tape, each time an action is simulated.
http://rendell-attic.org/gol/utm/utmtm.htm

Here are the parts in more detail:

The tape is a sequence of blocks. The colors have no significance to the operation, they just help show the motion of the tape.

I have marked the division between the stored program and the data using red blocks. Towards the right end of the tape is the data being operated on. And to the left end is the encoded program of the Turing machine being simulated.

The head reads the symbol from the tape in place, using redstone torches underneath the tape. These bits and their inverse are conveyed to the action table, where they can be matched by placing torches on the columns. In some cases, I have left out torches so that more than one symbol can be matched by a single action, which helps to reduce the size of the action table.

Across from the symbol matching rows are the state matching rows. At the head of these rows are the four latches holding the current state of the machine, and again redstone torches are used to match against particular states.

Underneath the matching rows are the wires that trigger when there is a match. At the end of the wire is a redstone torch, used to trigger the next action after the current one is finished, or left out if the machine should halt.

Back from this there is a torch in one of two columns, which triggers the right or left tape shift at the end of the action.

Further along is the set of four torch positions which set the next machine state for each action. I have reserved state zero for the error case when no action matches.

And still further along is the set of three torch positions that define the change to the symbol. For simplicity, these invert bits of the symbol, rather than setting it, which also helps when combining action rows that leave the symbol unchanged.

The outputs are all relayed underneath from the far end of the action table, so that the delay time is the same no matter which action is matched out of the array.

The symbol change outputs feed underneath the head and in from the back. The head uses pistons to change the bit values, pulling back the top block, raising the bottom block and lowering the top block, and then pushing the new bottom block into place. A solid block at the bottom represents a bit value of 1, and a glass block a bit value of 0.

This video features the tracks "Klik" and "Grom" by Jaap Blonk & Radbood Mens available under a Creative Commons License
http://freemusicarchive.org/music/Jaap_Blonk__Radboud_Mens/Bek_Mouth

[Notes]

Symbol encodings:
'0' 000 'A' 100
'1' 001 'B' 101
'C' 010 'D' 110
'M' 011 'X' 111

Initial tape sequence :
M00C0100M1C0100M11C0101M00C1111M00C0001M11C011XBBDBABXAABABA10000000

Final tape sequence:
M00C0100M1C0100XBBDABABXAADBBBBXAADAAABXBBDABBXBBDBABXAABABABABABAB0

Category:

Gaming

Tags:

• universal
• turing
• machine
• minecraft
• redstone
• computer
• UTM

[gmodvin]

And why is it usefull?

[neonsignal]

@gmodvin it is only 'useful' in the sense that a computer is useful; though this is a particularly slow computer! The purpose was to make a functional model, nothing more.

[bacon5897]

Sooo... It's kinda like a tape in a VCR getting read?

[neonsignal]

@bacon5897 yes, although the original conception was of a paper tape (like the sort used in automated telegraph machines) that was also erasable

[bboy02701]

Whats a Turing machine?

[neonsignal]

@bboy02701 A Turing Machine is a thought experiment, a simple device that can be set up ('programmed') to perform any computation. A Universal Turing Machine is a Turing Machine, but programmed in such a way that it can be used to simulate any particular Turing Machine set up. This thought experiment is the foundation of computer science.

[tonberrytoby]

Yo dawg, I heard you like universal computers...

[neonsignal]

@FiniteEight My first take on screen capturing the UTM run failed after about 20 minutes. I had neglected to turn the mode to peaceful: along came a skelly and shot me down from from the viewing platform, and the patiently waiting creeper below in the workings was there to provide the fireworks...

[ascii211]

Can I get a download? I give credit where due and won't steal it! Btw I LOVE redstone creations and this is one of my top 3

[SeirVedMini]

Some little kid is trying to claim this as his own, /watch?v=C8uMnHfxftk

[DSBrekus]

Fantastic.

[LittlePeng9]

@SnakePlisskenPMW According to Church-Turing Thesis it is impossible to increase computational power of Universal Turing Machine, which is belived to be able to compute anything computable. You can only make 3 things:

1. Make tape longer, so machine can store more data

2. Make machine faster by, for example, adjusting minimal repeater delays

3. Make machine more compact by, for example implementing smaller Universal Machine

But you CAN'T give it more computational power

[SnakePlisskenPMW]

could you post a worldsave, i belive i know how to implmate change to this turing device to utilize more computing power

[thevade]

Impressive, but still seems like a big waste of time/life to me..