The Computer Science Colloquium

Nachum Dershowitz
(Tel Aviv University)

"A Proof of the Church-Turing Thesis"

The goal is to formalize the famous Church-Turing Thesis. Specifically, the notion of an "effective model of computation" over an arbitrary countable domain is axiomatized. This is accomplished by modifying Gurevich's "Abstract State Machine" postulates. All such effective computational models, regardless of underlying data structure — and including all standard models, are equivalent to (up to isomorphism), or weaker than, Turing machines. To this end, we employ a quasi-ordering on computational models that captures comparative extensional power.

The Colloquium is supported by generous contributions from the Bloomberg, Information Builders, Inc. and Netlogic, Inc.