Prior to the groundbreaking work of Alan Turing himself, mathematicians had reduced all the branches of mathematics under a single umbrella framework -- now called Set Theory.
The methods used to uncover set theory were procedures of very rigorous proof writing. This is as type of proof-writing where individual characters in the written proof are accounted for. Every single line of the proof can be shown as a direct inductive inference from earlier lines. Today this type of proof-writing is called a "Hilbert-Style Proof". If you take a university course on the topic, you may hear them called
Well-formed Formulas, or even
Sentential Logic.Prior to this time, mathematical proofs were far more intuitionistic, and they were allegedly derived from the flashes of genius in the mathematicians mind. One famous example is Leonard Euler and how he wrote proofs about infinite series. His methods would make any high school teacher cringe, because they lacked the "rigor" of modern methods. But things were looser and less formalized back then.
Proof-writing became so formal and compartmentalized, that men of the early 20th century began to toy with the idea that proofs could be written mechanically, by a machine. One such mathematician who really took the idea and ran with it was Alonzo Church. Another one of these men: Alan Turing.
Sir Alan Turing imagined an actual metal machine with moving parts, that moved a tape through a reader. The tape would contain a linear list of bits of 1 or 0. The machine would read the tape and change its gear settings based on what it read. The machine could erase and write bits onto the tape. Turing never built one. He didn't intend to either, as he was thinking about how such a machine as it would perform mathematically. So its speed was considered to be fast enough for any application, and its tape infinitely long.
The mathematical model of the 'reader' in a turing machine is now called Finite State Automata. Church and Turing began to realize that if the FSA in their Turing machine had a rich enough suite of states and transitions, that it could run any algorithm that any other computing machine can run. In their own writing, they said that any idealized computing machine (be it the tape-reader thing, or whatever else) was capable of realizing the entire class of
Recursively-Enumerable Functions. In our modern tech jargon, we say that a Turing Complete machine can emulate any other computer. It is important to note that there is no stipulation of how difficult this would be to do in practice, nor how long it would actually take to run an algorithm using such emulation. There is also no stipulations about how finely-constructed its inner circuits must be, or how the underlying circuitry is represented on the tape. ( for more digression on this subject see Busy Beaver functions :
https://www.youtube.com/watch?v=CE8UhcyJS0I )
From Tape to Workstation. A Turing machine would build up sections of its tape to act as "RAM" and "Hard drive" and a "calling stack". Then there would be a part of the tape to store something resembling an "operating system". Because the writing and reading of bits on a tape is not "addition", subroutines would be written in the simplified state-transition language of the TM to emulate addition. Then other subroutines would be built up to eventually emulate an Arithmetic Logic Unit (or ALU). Armed with a functioning ALU (in software of all things) the Turing Machine could begin to emulate a genuine CPU. Because it can add, it can now keep track of this incredibly useful thing called an "instruction pointer". The processors inside our cellphones today perform all of this with physical circuitry -- but a Turing Machine does not come packaged with such luxuries.
Eventually the TM would segregate part of its tape to store instructions. Those instructions in turn would cause the Turing Machine to run subroutines, and eventually realize programs that look something like our modern algorithms. Before long, the TM could compute trillions of vector operations (per second?), allowing it to
run CrysisCellular Automata Throughout the 20th century, a number of heavy-hitter scientists contributed their 2 cents to descriptions of machines which can compute anything, (such as Von Neumann's "universal constructor" and other oddities.) As the decades passed, smarty pantses continued to find simpler and simpler rules which can compute anything.
In the year 2000, the simplest Turing-Complete rule was discovered. It is called
Rule 110. It is a 2-state 3-neighbor totalistic cellular automata. It operates in a 1-dimensional array of cells. The visuals for Rule 110 are not showing the rule itself, but "slices" of its grid states stacked on top of each other , with time running downwards.
The simpler a rule is, the more heinously difficult it becomes to construct even the simplest of useful logical functions using them. It would be an
enormous feat to produce a NAND gate using Rule 110. The starting state alone would likely be thousands of cells wide. It should be emphasized that all that careful programming and tweaking would be required to even realize a single primitive logic gate. Very careful design and care is required to make a logic gate, let alone more complex algorithmic features. For comparison, a modern CPU in 2016 contains around 450 million gates. On top of that, physical computers already have lots of engineered aspects going for them. They have RAM segregated from CPU by a motherboard, and a BUS, and peripherals in slots. Cellular Automata have none of that luxurious jazz, and would need to emulate it somehow.
Some people may claim that there is something inherent in simple Cellular Automata that makes them "physically natural" in some way. The above numbers show that this claim is unfounded -- even unreasonable.Conway's Game of Life (heretofore ConwayGOL) is now proven to be Turing complete. But it's universal computing ability was for a long time only assumed to be true by the community. The proof involves showing that there exists a pattern which emulates the functionality of Rule 110. In general, if rule X can emulate Rule 110, then it follows that rule X is Turing Complete.
ConwayGOL is a 2-state 8-neighbor sum-symmetric rule. One might ask how 'simple' ConwayGOL is compared to Rule 110. On first glance, they appear "just about equal". This is very far from the truth. If you re-write ConwayGOL as a 2-state 8-neighbor
totalistic rule, its rule table is an array of 512 bits. That is far larger than the paltry 8 bits of Rule 110's entire totalistic table.
ConwayGOL gets a lot of press due to its very simple description. But it is only one possible rule out of the 2-state sum-symmetric rules which operate on 2D grids. Sum-symmetric rule definitions follow the convention of Birth-and-Survive, written B and S respectively. "Birth" means an off cell becomes on in the next cycle. "Survive" means an on-cell remains on in the next cycle. If a rule is not mentioned in the convention, the cell does a default behavior of ""remaining dead" or "dying".
ConwayGOL is
B3/S23Here is a list of 2D grid rules s-s, which are now proven to be Turing Complete, as of Jan 2017.
- Code: Select all
B3/S238 (Eightlife)
B3/S237
B3/S2378
B38/S237
B38/S2378
B37/S23
B37/S237
B37/S238
B378/S237
B378/S2378
B36 /S23
B36 /S238
B368/S23
B368/S238
In the last few years, other Cellular Automata on grids have been found that appear to be even simpler than Conway. One of them is a block-cellular-automata that updates the grid by localized rotations. It only has 1 rule. It was investigated by Russian mathematician Dmitry Shintyakov. It appears to be very complex, but there is yet no proof of its Turing Completeness.
It's entire rule is
Rotate clockwise by 90° every block with exactly 1 alive cell.
That's it. It's eerie to know that an algorithm that simple can be so complex.
For more see :
http://dmishin.blogspot.com/2013/11/the-single-rotation-rule-remarkably.html