CMPUT 325 Special 14

    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.

         NEXT