- The notion of (effective algorithmic)
**reduction**.

In short, problem*A*is reducible to problem*B*when there exists an effective method*R*(called the reduction) to solve (every instance of) problem*A*assuming a solution for (every instance of) problem*B*.If problem

*A*is not algorithmically solvable, and*A*is reducible to*B*, then problem*B*is also not algorithmically solvable (because, if*B*would be solvable, then so would*A*, viz. via the reduction). - A computational mechanism
*M*is**universal**(also see: Turing complete) when*M*can be used to emulate any other computational mechanism (and in particular a one-tape Turing machine). - Slides for Ch. 17 (Theory of Computation) in
Foundations of Computer Science by Forouzan and Mosharraf
In particular,

*Simple Language*consisting of three statements (incr(X), decr(X), while (X) { statement list }) working on an unlimited set of arbitrary-sized nonnegative integer variables.*Simple Language*is universal. - Conway's Game of Life,
a 2D cellular automaton
- Golly:
a program to explore Conway's Game of Life on various platforms
(Linux, Mac OS X, Windows); includes many complex patterns;

Try: F-pentomino, golly-ticker.rle (in Guns), primer.rle (can download from LifeWiki), twinprimes.rle (in Miscellaneous), Turing-Machine-3-state.rle (in Signal-Circuitry) - Questions: Will a given intial state die out? Stabilize? Become repetitive? Grow/expand forever?
- "What is Life?",
Ch.25, pp.927-961 in
*Winning Ways for Your Mathematical Plays*, Volume 4. by E.R. Berlekamp, J.H. Conway, R.K. Guy. - Life is universal (ibid. p.957).

- Golly:
a program to explore Conway's Game of Life on various platforms
(Linux, Mac OS X, Windows); includes many complex patterns;
- Cellular automaton (CA)

- Elementary cellular automaton (one-dimensional)
- Stephen Wolfram's classification into four classes ("completely dull", "of limited interest", "pseudo-random/chaotic", "interesting/universal")
- Rule 30 (pseudo-random)
- Rule 110 (universal)
- Mathematica code:
ArrayPlot[CellularAutomaton[32, {{1, 0, 1, 1, 0, 0, 1, 1}, 0}, 50]] ArrayPlot[CellularAutomaton[108, {{1, 0, 1, 1, 0, 0, 1, 1}, 0}, 50]] ArrayPlot[CellularAutomaton[30, {{1}, 0}, 100], ImageSize -> Large] ArrayPlot[CellularAutomaton[110, {{1, 0, 1, 1, 0, 0, 1, 1}, 0}, 200], ImageSize -> Large]

- Wolfram's 2-state 3-symbol universal Turing machine (smallest possible)
- Stephen Wolfram.
A New Kind of Science (NKS).
Wolfram Media, 2002.
"... one of the implications of the Principle of Computational Equivalence is that almost any rule whose behavior is not obviously simple should ultimately be capable of achieving the same level of computational sophistication and should thus in effect be universal.

Also see Ch.13, Sec.3: "The Phenomenon of Universality""So far from universality being some rare and special property that exists only in systems that have carefully been built to exhibit it, the Principle of Computational Equivalence implies that instead this property should be extremely common. And among other things this means that universality can be expected to occur not only in many kinds of abstract systems but also in all sorts of systems in nature." (Ch.12, Sec.2, p.718)

- Wang Tiles

Question:- Given a set of Wang tiles, can you tile the infinite plane with this set?

- Diophantine Equations

Questions:- Are there any solutions?
- Are there infinitely many solutions?

- Gödel, Escher, Bach by
Douglas Hofstadter (1979)
- Read it on-line, or download it
- MU Puzzle
(Ch.1, p.41; do not look at the solution; find your own)
- RULE I: If you possess a string whose last letter is
`I`

, you can add on a`U`

at the end. - RULE II: Suppose you have
`M`

*x*. Then you may add`M`

*xx*to your collection. - RULE III: If
`III`

occurs in one of the strings in your collection, you may make a new string with`U`

in place of`III`

. - RULE IV: If
`UU`

occurs inside one of your strings, you can drop it.

`MU`

when you start with`MI`

? - RULE I: If you possess a string whose last letter is
- Typographical Number Theory (TNT, Ch.8), express the predicate "b is a power of 10" in TNT (p.223; this is very instructive, and not so easy, making it resemble a small research project)

- Combinatory Logic

Every lambda function can be expressed by an appropriate composition of S and K combinators, defined by(K x y) = x (S x y z) = (x z (y z))

- E.g.,
`(S K K)`is the identity function, also known as`I`:((S K K) x) = { Currying } (S K K x) = { definition of S } (K x (K x)) = { definition of K } x

Note that`(S K)`complements`K`, in that`((S K) x y) = y`. This is equivalent to`(K I)`, for which also`((K I) x y) = y`. Combinator`(K I)`can serve as representation of the number 0, and the combinator`(S (S (K S) K)`as successor function (that adds 1 to its argument). - Also of interest: Lambda Calculus, and especially also
- Encoding datatypes, like natural numbers, in lambda calculus
- Church encoding (numerals, booleans, pairs, lists)

- E.g.,
- Wireworld
(2D CA)
- Also available in Golly (see above, under Conway's Game of Life)
- Especially, see
`primes.mc`

in the folder "Other-Rules/WireWorld/" (you need to zoom in, when running it)

- Challenge: Write a self-reproducing program
- Rudy Rucker.
The Lifebox, the Seashell, and the Soul: What Gnarly Computation Taught Me About Ultimate Reality, the Meaning of Life, and How to Be Happy.
Basic Books, 2006.

Author's book page - Cristopher Moore, Stephan Mertens
The Nature of Computation,
Oxford University Press, 2011.

Especially, see Chapter 7: The Grand Unified Theory of Computation.

Authors' book page - Is Nature universal?

©2010-2012, Tom Verhoeff (TUE)

Feedback about this page is welcome