Announcement: Be excellent to each other.


Caravel Forum : Caravel Boards : General : Universality of DROD 2.0 (Not done by a professional... or an amateur, even.)
New Topic New Poll Post Reply
Poster Message
Niccus
Level: Smiter
Rank Points: 308
Registered: 07-02-2006
IP: Logged

File: Cellular Automata Emulator.hold (4.2 KB)
Downloaded 40 times.
License: Public Domain
icon Universality of DROD 2.0 (+5)  
I would like to note that I am currently sleepy. You'll probably see some sort of silly mistake. Notify me, please?

DROD 2.0 is universal. It can compute anything in an unreasonable amount of time.

DROD is a very very curious challenge to program. You have practically infinite amount of places to store information (infinite rooms in infinite levels), but permanent memory is too permanent (Room completion, Level completion, Mastery is unusable to my knowledge). Other possible ways to store information is by Beethro's sword (Limited to one bit of information, some logic possible by bombs and tunnels, takes too much space) or by location of room entry.

Fortunately, despite horrendous limitations, it is possible to emulate a universal system in DROD, without even using characters , orbs, multiple levels, or potions.

In particular, DROD can emulate all possible elementary cellular automatons. Since DROD can emulate Rule 110, DROD is universal. (from Wolfram's A New Kind of Science, explanation is available here)
The representation is a bit different from regular CAs (cellular automatons), even though each single room in DROD still represents a single cell. Instead of single cells switching back and forth between "alive" and "dead" states in a line, the representation of CAs in DROD take place in a more widely seen graphical format, with the history of all cells visible. The next iteration of the CA is done on the next row of rooms. (Go to the linked pages... see those pretty triangles? It's just like that.)

So... how?

-----

The plan is to have unit cells that do almost all the work. Beethro "scans" a cell, and follows a path depending on whether or not the current room is solved. The process is done three times (for the three cells which determine the state of a cell in the next generation). There will be eight paths in the end, each leading to the ruleset. The ruleset determines which paths lead to a path which changes the state of the particular cell in the next generation which the scanned cells affect. In the end of this changing of the cell's state (or if the path ends up not affecting that cell), the process begins anew starting a cell to the right.
In the end of the row of cells, Beethro is sent back through a special path going all the way back to the left edge of the level. The path leads to the next row, and the entire process repeats. An ending cell (with stairs) can be placed at a particular column.
The left and right edge cells are regarded as "0", though they can be modified to be "1" or even an explicit sequence of 1s and 0s -- though all of the information entered should only be the initial sequence of cells, the width of the "universe," and the number of generations to go through.

-----

The important elements:



This is the splitter. It splits paths, according to whether or not the current room is solved. Nifty mechanism, thanks to infinite supply of slayers.



This is the ruleset. The left column of tunnels denote "live" while the right column denote "dead." The ruleset follows the regular binary representation of elementary CA rules.



This is the marker, which tags a cell in the next generation as "alive." It spans three rooms for trivial reasons, and leads to a path which starts the scanning cycle anew.

Then there's the network of tunnels, possessing no particular function other than to lead Beethro to the right direction. I'll let you look at them in the .hold attached.

-----

Look in the .hold. It shows the parts necessary, etc. In the unit cell, the brain marks the cell as dead (how ironic). Delete brains in the first row of cells accordingly to mark cells as alive.
The ruleset is modifiable to any of the elementary cellular automatons. Try rule 0 for a lesson in futility!
An example level is also shown. It can be modified as you wish to add/reduce cells, it should be intuitive.
The right edge might be a bit counterintuitive (the ruleset is barebones), but it should be trivial to modify.

The level in action:







Oh, and I think the cells aren't quiiiiite *perfect* just yet. They did go through about 5 hours of creating and testing though.

[Last edited by Niccus at 09-19-2006 12:40 AM : Fixes]
08-10-2006 at 04:42 AM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Chaco
Level: Smitemaster
Rank Points: 3533
Registered: 10-06-2005
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
Nifty.

One question though - what (if anything) does this particular level compute?

____________________________
Quick links to my stuff (in case you forgot where it was):
Click here to view the secret text

08-10-2006 at 05:52 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Niccus
Level: Smiter
Rank Points: 308
Registered: 07-02-2006
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
The level is just a short short example... Computing 2+2 by this method would take, oh, more rooms than all the released holds so far (Maybe even with the architecture and beta holds counted).
08-10-2006 at 05:57 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Chaco
Level: Smitemaster
Rank Points: 3533
Registered: 10-06-2005
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
After going through the entire hold, I agree - that was really long.

It did produce those magical triangles that (apparently) can compute 2+2 with enough of them.

EDIT:

There are a few spots (most notably in the "go to the cell above you" ruleset) where you can escape the tunnel system by moving diagonally. A few well-placed walls should fix this.

____________________________
Quick links to my stuff (in case you forgot where it was):
Click here to view the secret text


[Last edited by Chaco at 08-10-2006 06:14 PM]
08-10-2006 at 06:12 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Niccus
Level: Smiter
Rank Points: 308
Registered: 07-02-2006
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
Whoops, fixed.

Surely it's understandable after several hours of constant tinkering...?
08-11-2006 at 01:53 AM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Taytanchik Ranti
Level: Roachling
Rank Points: 11
Registered: 04-16-2005
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
Err, how do you actually calculate with that thing? I see, that you can create nice pictures, but calculate - how would that work?


Did you use rule 238 for the picture in the first post?

____________________________
ali li pona!
08-12-2006 at 02:12 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Syntax
Level: Smitemaster
Rank Points: 1218
Registered: 05-12-2005
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
Taytanchik Ranti wrote:
Did you use rule 238 for the picture in the first post?
Nah... 239
08-12-2006 at 02:41 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Taytanchik Ranti
Level: Roachling
Rank Points: 11
Registered: 04-16-2005
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
Err, yes of course. How could I miss THAT! Might be because it was 4:30AM but that's just a guess. ;)

EDIT:
Wait a second. It's rule 110, as I actually should have known from the first post "Since DROD can emulate Rule 110,..."

Hm, looks like I mixed up the red and white rooms several times. My logic always tries to tell me, that the red rooms are 1 and the whites are 0, though it's vice versa. Well, it took a while, but finally I got it. ;)

Yet, I'd like to know, how to calculate with these cellular automatons.

____________________________
ali li pona!

[Last edited by Taytanchik Ranti at 08-12-2006 06:12 PM]
08-12-2006 at 06:05 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Niccus
Level: Smiter
Rank Points: 308
Registered: 07-02-2006
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
I linked to it in the original post... This is the first leg of the trip. Computing ANYTHING useful with this method takes an astronomical amount of time.

Fortunately, it can compute anything.

Just not in my lifetime.

But if you have Wolfram's New Kind of Science, switch to ch.11

[Last edited by Niccus at 08-12-2006 08:31 PM]
08-12-2006 at 08:30 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Briareos
Level: Smitemaster
Avatar
Rank Points: 3515
Registered: 08-07-2005
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
Niccus wrote:
But if you have Wolfram's New Kind of Science, switch to ch.11
What, "the process of reorganization under the bankruptcy laws of the United State Machine?" :lol

np: James Figurine - You Again (Mistake Mistake Mistake Mistake)

____________________________
"I'm not anti-anything, I'm anti-everything, it fits better." - Sole
R.I.P. Robert Feldhoff (1962-2009) :(
08-12-2006 at 09:51 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts Quote Reply
Kevin_P86
Level: Smitemaster
Avatar
Rank Points: 534
Registered: 06-28-2005
IP: Logged
icon Re: Universality of DROD 2.0 (+2)  
It is often possible to "cheat" the splitters and take the "wrong" path. Specifically, the ones in the top-right of many of the rooms when the green door is down.

____________________________
+++++[>+++++<-]>[>+++>++++>+++++<<<-]>.>+.>-------.<++++.+++++.
08-24-2006 at 11:31 PM
View Profile Send Private Message to User Send Email to User Show all user's posts This architect's holds Quote Reply
Daneel
Level: Delver
Rank Points: 35
Registered: 04-12-2006
IP: Logged
icon Re: Universality of DROD 2.0 (+2)  
I think there are easier ways to prove universality. It should not be too difficult using orbs, walls and arrows to force Beethro to run a turing machine. Anyway, this universality implies that DROD is PSPACE complete (and hence as hard [given absurdly large rooms] as any other computer game).
09-18-2006 at 07:45 AM
View Profile Show all user's posts Quote Reply
Niccus
Level: Smiter
Rank Points: 308
Registered: 07-02-2006
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
Daneel wrote:
I think there are easier ways to prove universality. It should not be too difficult using orbs, walls and arrows to force Beethro to run a turing machine. Anyway, this universality implies that DROD is PSPACE complete (and hence as hard [given absurdly large rooms] as any other computer game).

You'll have to go more in-depth in that idea... From the sounds of it, a universal turing machine would require multiple rooms per point at the tape. The number of states and colors would be rather high...

I've explored other ways of expressing data before using multiple paths. Bombs work well (with Beethro's orientation being a sort of one-bit, maaaaybe two-bit RAM), but tends to be bulky.

Of course, I haven't explored the use of characters yet, so...
09-19-2006 at 12:05 AM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
coppro
Level: Smitemaster
Rank Points: 1306
Registered: 11-24-2005
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
Niccus wrote:
But if you have Wolfram's New Kind of Science, switch to ch.11

You need to stop watching television, my friend.
09-19-2006 at 12:21 AM
View Profile Show all user's posts Quote Reply
Niccus
Level: Smiter
Rank Points: 308
Registered: 07-02-2006
IP: Logged
icon Re: Universality of DROD 2.0 (+1)  
coppro wrote:
Niccus wrote:
But if you have Wolfram's New Kind of Science, switch to ch.11

You need to stop watching television, my friend.

Huh?

Anyways, fixed that bug, plus another one involving the last cell before the ending room.
09-19-2006 at 12:40 AM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Daneel
Level: Delver
Rank Points: 35
Registered: 04-12-2006
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
Niccus wrote:
Daneel wrote:
I think there are easier ways to prove universality. It should not be too difficult using orbs, walls and arrows to force Beethro to run a turing machine. Anyway, this universality implies that DROD is PSPACE complete (and hence as hard [given absurdly large rooms] as any other computer game).

You'll have to go more in-depth in that idea... From the sounds of it, a universal turing machine would require multiple rooms per point at the tape. The number of states and colors would be rather high...

I've explored other ways of expressing data before using multiple paths. Bombs work well (with Beethro's orientation being a sort of one-bit, maaaaybe two-bit RAM), but tends to be bulky.

Of course, I haven't explored the use of characters yet, so...

The basic idea of simulating a Turing machine is as follows:

You have a number of large blocks representing the tape.

Beethro enters a block and is forced to leave through one of a number of exits {1,..,n}. Only the exit corresponding to the current turing machine state is open. Again Beethro must go through an exit this time labeled by the symbols that could be at that point on the tape and again only the one corresponding to the current symbol is open.

Next to proceed, Beethro must go through an "airlock" forcing him to push a couple of orbs. Orb1, makes the appropriate changes to the state (by opening and closing appropriate doors), the symbol at our current location (again by changing doors), opens D1 and closes D2. O2 opens D2 and closes D1. Beethro then proceeds to his next location (an adjacent tape location) determined by his path (which has specified state and symbol already).

O1.........O2

B.....D1................D2

We can ignore planarity constraints either through the use of tunnels or through appropriate use of orbs. Lastly, we use arrows to ensure that Beethro never backtracks (once he reaches O1, he can't go back).
09-19-2006 at 06:50 AM
View Profile Show all user's posts Quote Reply
Sillyman
Level: Smiter
Avatar
Rank Points: 339
Registered: 09-08-2006
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
But how could you transfer data between rooms? Infinite/potentially infinite tape is required...

____________________________
Who, me?
FNORD
11-19-2006 at 04:04 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
Niccus
Level: Smiter
Rank Points: 308
Registered: 07-02-2006
IP: Logged
icon Re: Universality of DROD 2.0 (0)  
Sword orientation + bombs and location of entry.

...All bulky, but I think they're the only thing that work.
11-19-2006 at 04:15 AM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
New Topic New Poll Post Reply
Caravel Forum : Caravel Boards : General : Universality of DROD 2.0 (Not done by a professional... or an amateur, even.)
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.