Rule 110 marble computer

Marble based computer by Jim Lewis, CEO of emachineshop.com
Shorter, less technical version:
https://youtu.be/X7atZzczIAo

Transcript:
For several years I've been thinking about building a mechanical computer that demonstrates the Rule 110 principle. In this video I'll show my marble machine which I call the Rule 110 Marble Computer. Many marble machines have been built by others. Some of them demonstrate a computing function such a binary counter I did several years ago. A classic toy called the Digi-Comp II could do basic arithmetic. But none of them are capable of general programmable computing. The device I built is capable of general computing if extended to many more bits. Rule 110 is a system based on a series of binary digits which change according to very simple rules. Each bit changes based only on its own value and the value of its two neighbors. Rule 110 is called a one dimensional finite state automata. Here are the rules. If there are three zeros the center bit changes to 0. 001 becomes 1. 010 becomes 1. 011 becomes 1. 100 becomes 0. 101 becomes 1. 110 becomes 1. And 111 becomes 0. So let's say we start with 110001. That's our program. We take the bits in groups of 3 and apply the rule. So 110 becomes 1. 100 becomes 0. 000 becomes 0 and 001 becomes 1. In my computer I'm leaving the end bits fixed so we drop them down. So the new pattern is 110011. The way the rule 110 computer runs is by updating the bits repeatedly. But what's cool is that with enough bits you can program a rule 110 machine to do anything. Rule 110 was discovered by mathematician Steve Wolfram during careful review of the 256 possible similar bit-mapping rules. Why 256? Because the 8 rule bits could be any of 256 possible choices. So let's see how all this works in the marble computer. The balls act as electricity would in a normal computer. When pointing to the left each flipper is a 1 and to the right is a 0. The white flippers represent the state of main four units and these end flippers represent the bits at either end of the computer. The computer is run by rocking back and forth. Before we start up the computer, we have to program it. We do that by setting the bits. Such as 1,1,0,0,0,1 as in the example I gave previously. Matthew Cook proved that Rule 110 is turing complete which means that a rule 110 based computer can compute anything given enough bits and time. To the best of my knowledge a rule 110 based computer is currently the simplest known type of computer and as far as I know, this marble machine is the first purely mechanical implementation of a rule 110 computer. As far as future plans, I'm planning to look for a science center, university or another public location where I can build a large scale version to help the public learn more about Rule 110. Each bit is made of the base, the ball, 4 links and 8 flippers. The base was machined at eMachineShop out of 6061 aluminum and powder coated metallic blue. After I designed the computer I began to wonder how many states it could go thru given a selected initial state. So I wrote a program in python to simulate a rule 110 computer. The first version of the program was able to analyze up to about 12 bits in a reasonable amount of time. After about 10 optimizations of the algorithm I got up to 25 bits. To analyze a 25 bit rule 110 computer without optimization requires computing the states of all 25 bits, 33 million times and then counting the length of the program run before it repeats a state, starting at each of those 33 million states. So here are the results. A one bit computer can step thru all 2 states. A 2 bit computer can step thru all 4 states. A 3 bit version can step thru only 7 of the 8 possible states. A 4 bit version like the one I built can step thru up to 10 states … if started at state 101001. As for larger machines, the maximum states increases only gradually with the number of bits. For example a 10 bit version can at most sequence thru 63 states before repeating. Empirically the maximum sequence appears to be about N raised to the power 1.84. I was hoping to find a sudden large jump where some clever program figured out how to generate a much longer sequence but so far such a program has not materialized. Finding such a program might be informative because Cook's proof of completeness used a computation method that is clever but very slow. There might be a better way of programming rule 110 computers that is faster and uses less bits. Discovering such a method could potentially move rule 110 into more practical computing domains - perhaps ultra nano molecular scale computers or some such future technology. Other possible avenues of exploration include using rules other than 110 and referencing bits other than the immediate neighbors.

Background music: http://www.bensound.com

Видео Rule 110 marble computer канала Jim Lewis