The Full Wiki

More info on Rule 110

Rule 110: Quiz


Question 1: Around 2000, Matthew Cook verified a 1985 conjecture by ________ by proving that Rule 110 is Turing complete, i.e., capable of universal computation.
Stephen WolframMathematicsRichard FeynmanEngland

Question 2: The original emulation of a ________ contained an exponential time overhead due to the encoding of the Turing machine's tape using a unary numeral system.
Finite-state machineContext-free grammarAutomata theoryTuring machine

Question 3: Cook proved that Rule 110 was universal (or ________) by showing it was possible to use the rule to emulate another computational model, the cyclic tag system, which is known to be universal.
Turing completenessProgramming languageTuring machineProgramming paradigm

Question 4: For a nontechnical discussion of Rule 110 and its universality, see Stephen Wolfram's book, ________ (NKS).
A New Kind of SciencePhilosophy of scienceEmergenceScientific method

Question 5: Neary and Woods (2006) modified the construction to use only a ________ overhead, thus proving Rule 110 P-complete.
PolynomialField (mathematics)Prime numberAlgebra

Question 6: ________ (2002) A New Kind of Science.
EnglandRichard FeynmanStephen WolframMathematics

Question 7: The Rule 110 cellular automaton (often simply Rule 110) is an ________ with the following rule table:
Mersenne primeRule 30Elementary cellular automatonWolfram code

Question 8: Rule 110 is arguably the simplest known ________ system.
Programming paradigmTuring machineTuring completenessProgramming language

Got something to say? Make a comment.
Your name
Your email address