Universality: Church-Turing Thesis
Roughly speaking:
The "C" programming
language, run
on a computer with infinite memory,
is the most
powerful computational system possible!
(assuming the
absence of god-like beings)
But to avoid
wars ... it also says the same thing about
Assembler, BASIC,
COBOL, Prolog, and even JAVA.
More precisely
the following models are all equivalent in
the sense of
what they can compute:
* Turing Machines
(DTM) - Automata but with read/write
bidirectional tapes
* Multi-tape
TM
* RAM / RASP
- abstractions of your PC
* Infinite
register machine
* Cellular Automata - arrays
of automata linked to one another
And it claims (the unprovable thesis)
that no realizable
system can be made more powerful.