Official Everybody Edits Forums

Do you think I could just leave this part blank and it'd be okay? We're just going to replace the whole thing with a header image anyway, right?

You are not logged in.

Donate!

pls donate


#1 2015-02-13 04:38:28

green_meklar
Guest

Universal Turing machine

(The link to the map is below, but first an infodump regarding its significance.)
The concept

I was primarily inspired by accounts of building working calculators, computers and such in games like Dwarf Fortress and Minecraft. Some time ago, I myself had managed to make elementary cellular automaton rule 110 run flawlessly in a StarCraft map, thereby demonstrating that StarCraft is also Turing-complete. So it was natural for me to think of building a Turing-complete system in Everybody Edits.

Before attempting the project, I did some googling to see if anyone else had beaten me to the punch. I found no indication that anything like this had ever been attempted in Everybody Edits. Naturally, if someone else has done a project like this or knows of someone who has, by all means, drop a link in this thread!
The plan

Clearly the system cannot be made with just blocks. It has to involve both blocks and smileys somehow; and ideally, it should run with no human input after the smileys are initially set up. Now, most blocks (basic blocks, platforms, gravity, etc) don't interact in complex ways with smileys. Even coin doors and portals are too simple, since you can't reverse the state of a coin door (with respect to any particular smiley) and a portal only ever has one exit. However, keys and key doors might have the required properties. If a smiley is accelerated along a gravity track, and then skids (under normal gravity) across a floor with a key door in it, it will either fall through the key door or not, depending on whether another smiley recently touched the corresponding key. This means that the locations of smileys can be used to determine the locations of other smileys. That is the sort of self-modifying feedback mechanism that hints at Turing-complete behavior. It is also convenient that keys and key doors, unlike coin doors and portals, are always available in infinite quantity, thus an infinite amount of shop energy would not be required to build an infinitely large system.

What sort of system should be implemented? A DFA would not properly demonstrate universality. Another cellular automaton would probably use too many smileys. But an actual Turing machine, with its 1-dimensional data storage, might be feasible. One smiley would represent the head state, by orbiting in one of several chambers leading to different tracks with different patterns of keys on them. Other smileys would represent the symbols on the tape. However, because we are limited to 3 types of keys, there is no straightforward way to arbitrarily select a particular smiley from a tape longer than length 3. But what we can do instead is just have a particular cell on the tape that represents the active cell, and have all the smileys on the tape move backwards or forwards by 1 space at the end of each step. In that case, the smiley entering the active cell will be the trigger for the computation in each step, touching the appropriate keys to update the state, its own symbol on the tape, and the direction in which the tape moves. The simplest way is probably to equip the active cell with portals that move the smiley away into the 'processor' and then back. In order to represent the different symbols, we can simply make multiple tapes, independent except for the active symbol smiley which may enter the processor from one tape and exit onto another tape.

The Turing machine I picked was the universal 2-state 4-symbol machine described by Neary and Woods in 2007, which emulates elementary cellular automaton rule 110. It has the following transition rules (where states are numbered 0 to 1 and symbols are numbered 0 to 3):
Symbol 0:
- State 0: Left, state 0, symbol 2.
- State 1: Right, state 0, symbol 3.

Symbol 1:
- State 0: Left, state 1, symbol 3.
- State 1: Left, state 1, symbol 2.

Symbol 2:
- State 0: Left, state 0, symbol 3.
- State 1: Right, state 1, symbol 0.

Symbol 3:
- State 0: Left, state 0, symbol 3.
- State 1: Right, state 1, symbol 1.

It is 'weakly universal' in the sense that it has to start with an infinite repeating pattern on the tape in order to achieve Turing-complete behavior. There is a known universal machine with 2 states and 3 symbols, but it requires an infinite non-repeating pattern on the tape, and it seemed a bit pointless to use it because key doors represent binary logic and so choosing between 3 symbols would require just as many keys as choosing between 4 symbols anyway (this turned out not to matter, but I still managed to fit the 4-symbol tape into my wide world and since it can be seen as a stronger demonstration of universality at the expense of only 5 more portals, I went with it).

So, how to make use of the 3 types of keys? First, the simplicity of the tape is paramount, so let the green key be reserved for signaling the tape to move when each computation step is done. The active symbol smiley will, upon moving into its section of the tape, enter the portal corresponding to its symbol (a different portal on each of the 4 parallel tapes), taking it to one of 4 processors, one for each symbol. As it enters the processor, it will touch the red key, opening the red door and letting the state smiley drop from either of its 2 chambers into the corresponding track, which determines whether or not it will touch the blue key. Depending on whether the blue door was opened, the active symbol smiley will drop into one of 2 tracks in its processor (8 such tracks in total). Both the state smiley and the active symbol smiley will wait for the red door and blue door to timeout (to ensure that they have been reset). The active symbol smiley will then, depending on what track it is on, either touch the red key or not and the blue key or not, and finally touch the green key before going through another portal back to the tape. Depending on whether the state smiley touched the red key this second time, the state smiley will return to one or the other of its chambers. The green key relases all the tape smileys from their chambers, and depending on whether the active symbol smiley touched the blue key, they (including the active symbol smiley) will move either forwards or backwards (bearing in mind that the machine head moving to the right is equivalent to the smileys moving to the left, and vice versa). Finally, the tape smileys will all wait for the green door to timeout, in order to ensure they will orbit properly in the next tape chamber until the next active symbol smiley touches the green key again.

Since of course we can't really have an infinite tape in an Everybody Edits map, I instead made a tape of length 8 that uses portals to wrap around on both ends. This uses an extra 16 portals. In principle, an infinite tape using my design would require only 20 portals, and a larger, slower design could eliminate the portals entirely. The wide world is actually large enough to fit a tape of length at least 20 or so, but I didn't want to have that many browser tabs open, so I stuck with the tape of length 8 (requiring a total of 9 smileys, 1 for the state and 8 for the tape).
The map

Once I had envisioned the logic and determined the usage of the 3 key types, building the machine was surprisingly quick and straightforward. I did make a few mistakes involving the directions of portals and positions of doors, but I believe I've fixed all of those.

Here is the state mechanism:

State.png

State 1 is on the left, state 0 is on the right.

Here is the processor (there are 4 of these):

Processor.png

The processor shown above has both red keys and both blue keys in place, in order to show where they would go. In reality, the red key is only present when that track is supposed to cause the state smiley to enter state 1 (otherwise it enters state 0), and the blue key is only present when that track is supposed to cause the head to move right (otherwise it moves left). The horizontal track in the processor is just there to ensure enough delay for the state smiley to complete its orbit and touch the blue key before the active symbol smiley reaches the blue door, and could probably be made shorter than it is.

Here is a single unit of tape storage (each of the 4 parallel tapes has 7 of these):

Storage.png

Here is a special 'loader' unit of tape (each of the 4 parallel tapes has 1 of these, each linked to its corresponding processor by portals):

Loader.png

It is convenient that the tape storage and the tape loader are exactly the same size (9X11).

Here is a link to the map itself, for anyone who wants to see how the entire machine looks. Testing it the other day also doubled as an accidental guestbombing, so a bunch of people joined. Since the map had a different name at that time, I don't think any of them figured out what was really going on in there. //forums.everybodyedits.com/img/smilies/tongue
The weird stuff

You know how, when you join a world where the spawn point is above a gigantic drop, you see every other player who hasn't manually moved yet drop from the spawn point alongside you? And how a player who is blocking key doors that timed out on your screen will move inside the solid doors in a jerky manner? And how another player doing a very precise jump may at first appear to fall into the abyss, but then teleport up into a safe zone? It seems that, in the interest of conserving network resources, not all of another player's movements are updated for you, but rather predicted based on a physical simulation run on your own computer, and only synchronized when the player moves manually. Most of the time we don't even notice the difference. In some cases (like those I just mentioned above), it is temporarily amusing.

But my machine runs entirely without any manual movement. Thus, the smiley locations are synchronized very rarely, if at all, even while the smileys are continually moving through complex patterns involving key doors and portals. This has the strange effect of causing smileys to occasionally end up on the wrong part of the tape from the point of view of the other smileys, and after several steps of the simulation, each tab I have open sees rather different configurations of smileys in the machine, often with multiple smileys orbiting in the exact same unit of tape storage (which, physically speaking, should never happen).

For a while I thought this was causing the machine to break. However, after I fixed a mistake in the design of the tape storage units, the machine now seems to work properly...but only if you trust each smiley's own perception of where it is. It seems that, although the smileys' locations are not properly synchronized, the signals from the keys are, so every smiley will see the keys activate at the right time (even if it doesn't see a smiley touch the key) and respond in the physically correct way. Which means that although no one smiley can be trusted to see an accurate configuration in the machine, aggregating the positions of all the smileys from their own respective viewpoints gives you the actual, correct configuration.

For my machine, all that means is that it works properly, in a sense. However (and I don't have a solid theory for this, but) it might be possible to construct a machine that actually makes use of this effect in order to create different, yet still computationally meaningful, configurations from the viewpoints of different smileys. If someone builds a working quantum computer in Everybody Edits, I will bow down and worship them. //forums.everybodyedits.com/img/smilies/big_smile
I apologize for any mistakes in my logic or physics. If someone has found a mistake, please tell me so that I may have a chance to correct it.

#2 2015-02-13 04:38:27

Muftwin
Guest

Re: Universal Turing machine

great! what does it do tho?...

#3 2015-02-13 04:38:26

Fdoou
Guest

Re: Universal Turing machine

tl;dr and I don't know what turing is.

#4 2015-02-13 04:38:25

Different55
Forum Admin
Joined: 2015-02-07
Posts: 15,995

Re: Universal Turing machine


"Sometimes failing a leap of faith is better than inching forward"
- ShinsukeIto

Offline

#5 2015-02-13 04:38:24

green_meklar
Guest

Re: Universal Turing machine

Incidentally, tomorrow (June 23) will also be Alan Turing's 100th birthday.

#6 2015-02-13 04:38:23

Different55
Forum Admin
Joined: 2015-02-07
Posts: 15,995

Re: Universal Turing machine

Should've released it tomorrow.


"Sometimes failing a leap of faith is better than inching forward"
- ShinsukeIto

Offline

#7 2015-02-13 04:38:22

MIHB
Guest

Re: Universal Turing machine

Anybody want to translate this?

#8 2015-02-13 04:38:21

imgood9
Member
From: 'Murica
Joined: 2015-02-28
Posts: 472

Re: Universal Turing machine

tl;dr

And I don't know what you're talking about at all.


Go vote. Register here. Do it for America.

Offline

#9 2015-02-13 04:38:20

FloddyFosh
Guest

Re: Universal Turing machine

Awesome stuff!

I think alot of people don't understand though what you are talking about //forums.everybodyedits.com/img/smilies/tongue. I'm learning this stuff in 2nd year University. Haha..

How do you know about Turing Machines? Is it because of interest or did you learn it already?

#10 2015-02-13 04:38:19

Different55
Forum Admin
Joined: 2015-02-07
Posts: 15,995

Re: Universal Turing machine

As far as I can tell he made a computer in EE.


"Sometimes failing a leap of faith is better than inching forward"
- ShinsukeIto

Offline

#11 2015-02-13 04:38:18

Muffy
Guest

Re: Universal Turing machine

My head hurts...

#12 2015-02-13 04:38:17

soccerfreak006
Guest

Re: Universal Turing machine

maybe afk's? or ways to see what people are doing without playing?

#13 2015-02-13 04:38:16

FloddyFosh
Guest

Re: Universal Turing machine

Have you seen the amazing Turing Machine on Google?

#14 2015-02-13 04:38:15

green_meklar
Guest

Re: Universal Turing machine

Should've released it tomorrow.

Well, I'm going to be away from my PC for about 3 weeks starting in early July. So I wanted to post early to have more time to get responses and fix any problems with the machine. Besides, I only noticed the coincidence about the date later.

How do you know about Turing Machines?

The same way anyone else would know? I mean, this stuff is not exactly secret. //forums.everybodyedits.com/img/smilies/tongue

#15 2015-02-13 04:38:14

swordsman
Guest

Re: Universal Turing machine

Mind blown... and I thought the calculator was complex...

#16 2015-02-13 04:38:13

coolguy5649
Guest

Re: Universal Turing machine

I can't go inside it...:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(

green_meklar 1423798708162724

Board footer

Powered by FluxBB

[ Started around 1571424111.8391 - Generated in 0.116 seconds, 10 queries executed - Memory usage: 1.36 MiB (Peak: 1.51 MiB) ]