Pages: [1]



Author

Topic: The ultimate Rubicon challange... (Read 4487 times)

Daniel Nilsson

...create a Universal Turing Machine! Building such a machine would prove that Rubicon is Turing complete and therefore able to compute any computable function. The limited space of Rubicon is a problem though, in addition to probably being to small for the state machine, the storage tape should be infinite. But let's assume that Rubicon was extended to an arbitrary large space. This can be simulated by building the machine in parts. So what parts are needed? A Turing machine consists of:  The tape: An infinite line of memory cells that can be read and written. It can be moved left/right to change the current cell.
 The state machine: Given the current state and the symbol from the current tape cell it moves to a new state, writes a new symbol to the cell and moves the tape left or right.
According to Wikipedia the smallest known universal Turing machine has 2states and 5symbols. So if Rubicon can simulate that it is Turing complete.


« Last Edit: October 31, 2006, 11:03:41 PM by Daniel Nilsson »

Logged




Daniel Nilsson

The state machine can be represented by a read only random access memory. It needs 10 words of memory (5 symbols * 2 states), each word needs to contain a new state, a new symbol and a move instruction. This can easily fit in two hexdigits. This means that two copies of ginkgo's memory registers in hibadig will do nicely.



Logged




Daniel Nilsson


The Tape
« Reply #2 on: October 31, 2006, 03:06:07 PM » 

The tape should be able to store one of 5 symbols in each cell (i.e. one hexdigit is more than enough). There should be a way to get the symbol stored in the current cell and a way to replace it. There must be functions for moving the whole tape left and right. The design must be infinitely extendable in both directions and all inputs and outputs must be on the same side. Any takers? I made a first attempt in daletyc. I ran out of space and it's time to sleep. The tape is stored on the slopes in the middle. The inputs are marked with hazard signs. The crate input is for new symbols to store and the barrel input signals the direction of movement: 1 = left, 0 = right. The output is destroyed by the central furnace because I had no room to get it out of there. The timing is very delicate.


« Last Edit: October 31, 2006, 11:02:15 PM by Daniel Nilsson »

Logged




Nic

You don't have to specifically emulate the Universal Turing Machine (though it would be nice) to prove that Rubicon is Turingcomplete... Try something simpler if the Turing thing gets untestable (That is, if there's no way to properly test it in the space you can use in the applet). Just a recommendation. And you do realize it's much easier to emulate Rule 110 Cellular Automaton directly than emulating the 2state 5color turing machine that in turn emulates the automaton, right?



Logged




Daniel Nilsson

Yes, I am aware that there are easier way to prove Turing completeness than building a Turing machine. But ever since I saw a Conway's game of life Turing machine I have a certain fondness of them. Given the partial implementation of the tape I think I could implement the whole Turing machine given a larger grid.



Logged





Pages: [1]



