Rubicon Forum
Welcome, Guest. Please login or register.
October 31, 2014, 10:08:12 PM

Login with username, password and session length
Search:     Advanced search
Forum users can use the crate icon (or [level] and [/level] tags) when writing a post, to make a direct link to a level.
5463 Posts in 238 Topics by 2430 Members
Latest Member: Shreyas
* Home Help Search Login Register
+  Rubicon Forum
|-+  Playing the Game
| |-+  Open Design Challenges (Moderator: Bucky)
| | |-+  The ultimate Rubicon challange...
« previous next »
Pages: [1] Print
Author Topic: The ultimate Rubicon challange...  (Read 3695 times)
Daniel Nilsson
Designer
***
Posts: 55


View Profile
The ultimate Rubicon challange...
« on: October 31, 2006, 02:52:47 PM »

...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 2-states and 5-symbols. 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
Designer
***
Posts: 55


View Profile
The State Machine
« Reply #1 on: October 31, 2006, 02:59:19 PM »

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 hex-digits. This means that two copies of ginkgo's memory registers in hibadig will do nicely.
Logged
Daniel Nilsson
Designer
***
Posts: 55


View Profile
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 hex-digit 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
Operator
**
Posts: 15


View Profile Email
Re: The ultimate Rubicon challange...
« Reply #3 on: November 01, 2006, 02:00:03 AM »

You don't have to specifically emulate the Universal Turing Machine (though it would be nice) to prove that Rubicon is Turing-complete...

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 2-state 5-color turing machine that in turn emulates the automaton, right?  Wink
Logged
Daniel Nilsson
Designer
***
Posts: 55


View Profile
Re: The ultimate Rubicon challange...
« Reply #4 on: November 01, 2006, 10:20:09 AM »

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] Print 
« previous next »
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.0.22 | SMF © 2006-2011, Simple Machines LLC Valid XHTML 1.0! Valid CSS!