MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 added structures that realize universal computation

How about models of computation?

  • Turing machines
  • Register machines
  • Cellular automata
  • $\mu$-recursive functions
  • The untyped $\lambda$-calculus
  • Unrestricted grammars
  • Term-rewriting systems
  • Recursively-enumerable subsets of $\mathbb{N}$
  • $\ldots$

To this list we can add finite presentations of semigroups and groups, diophantine sets, and many other mathematical structures that realize universal computation.

show/hide this revision's text 1 [made Community Wiki]

How about models of computation?

  • Turing machines
  • Register machines
  • Cellular automata
  • $\mu$-recursive functions
  • The untyped $\lambda$-calculus
  • Unrestricted grammars
  • Term-rewriting systems
  • Recursively-enumerable subsets of $\mathbb{N}$
  • $\ldots$