SCHOOL OF ENGINEERING AND COMPUTER SCIENCE

The notion of computation

Here's a not-so-digestable synopsis of the points in this chapter -- Tim Field

• Computation as a Framework
  • a program is something that takes input, operates on it using some predefined rules and produces output
  • the ''initial conditions'' and ''state (after N steps)'' of a CA can be considered the ''input'' and ''output'' of a program
  • abstracting away from the computation details allows you to think about different computing systems

• Computations in CA
  • examples of computation in CA
    • remainder modulo 2 (2 colours, 2 neighbours)
    • (8 colours, 2 neighbours)
    • Sieve of Eratosthenes (16 states, 2 neighbours)
    • the Rules enumerate different sets, e.g.
    • Rules 94, 62 and 190 enumerate multiples of 2, 3 and 4 respectively
    • Rule 129 yields powers of 2
  • so, the output of some CA is traditional math calculations, but what about others, e.g. 30, 45, 73?

• Phenomenon of Universality
  • those examples display different behaviour by changing the rules
  • but, you can change the behaviour by changing the programming, i.e. representing programs as data
    • common knowledge: computers (hardware/software), computer languages (primitives/programs), human languages (morphemes/sentences)
    • Wolframiam science is the extension of this idea to the natural sciences

• Universal CA
  • uses initial conditions to define the rules
    • block of 20 cells in UCA represents each emulated cell (19 colours, 5 neighbours)
    • extended to next-nearest as well
  • can encode more colours by using larger blocks
  • ''nothing fundamental is gained by using rules that are more complicated than for the UCA''

• Emulating Other Systems with CA
  • CA can emulate other computing systems, e.g. mobile automata, Turing machines, substitution systems, register machines, cyclic tag systems, symbolic systems, logic expressions involving AND, OR and NOT, random access memory
  • these last two show how you could implement a traditional logic-gate based computer

• Emulating CA with Other Systems
  • other computing systems can emulate CA
  • arithmetic systems '''emulate''' register machines '''emulate''' CA

• Implications of Universality
  • all these systems emulate each other
  • there's a threshold of universality
  • can discuss ''computation'' in abstract terms

• Rule 110 CA (the passive voice section)
  • complexity of UCA
    • explicit mapping UCA requires 19 colours gives very complex rules
    • 18 colour UCA (70's)
    • 7 colour UCA (80's), but still has 343 distinct cases
    • 2 colour UCA (mid 80's) == Rule 110!
  • how? behaviour of 110 yields localised structures that move and interact in complicated ways
  • proof involves showing that 110 emulates cyclic tag systems by slowing changing the representation of the tag system until it can be emulated

• The Significance of Universality in Rule 110
  • only common examples of universality: practical computers and computer languages
  • complicated in their construction --> intuition is that any system which is universal must be based on complicated rules
  • one of the very simplest possible 256 rules manages to be universal
  • implication: universality may be more common than might otherwise have been thought

• Class 4 Behaviour and Universality
  • Class 4 CA display same behaviour as Rule 110
  • conjecture: all Class 4 CA are universal
  • rule 110 (and its equivalent rules, 124, 137 and 193) and possibly rule 54 are the only Class 4 simple rules
  • can show universality in 2D CA, i.e. Game of Life, but it's much easier to create streams of localised structures which cross

• The Threshold of Universality in CA
  • class 1 and 2 CA never allow transmission of information except over limited distances --> only support processes that involve the correlated action of a limited number of cells
  • conjecture: any system whose behaviour is not somehow fundamentally repetitive or nested is universal
  • difficult in proving universality is emulating some other system
  • conjecture: rule 53 (exhibiting class 3 behaviour) is universal

• Universality in Turing Machines and Other Systems
  • best UTM from 60's is 7 states and 4 colours
  • using rule 110 can set up a UTM with 2 states and 5 colours
  • TMs with 2 states, 2 colours too simple to support universality
  • somewhere between 2,2 and 2,5 lies the threshold of universality
  • conjecture: 2-state, 4-colour TMs are universal
  • conjecture: 14 of the 3*10^6 2-state, 3-colour TMs are universal (they produce considerable complexity and are equivalent)
  • 3-state 2-colour TMs always resolve to a simple form (but maybe more complex initial conditions are needed)

back to Wolframania