Abstract
Computer Science has witnessed the emergence of a plethora of different
logics, models and paradigms for the description of computation. Yet, the
classic Church-Turing thesis may be seen as indicating that all general models
of computation are equivalent. Alan Perlis referred to this as the Turing
tarpit, and argued that some of the most crucial distinctions in computing
methodology, such as sequential versus parallel, deterministic versus
non-deterministic, local versus distributed disappear if all one sees in
computation is pure symbol pushing. How can we express formally the difference
between these models of computation?
Original language | English |
---|---|
Journal | Mathematical Structures in Computer Science |
Volume | 13 |
Issue number | 4 |
Pages (from-to) | 481-484 |
ISSN | 0960-1295 |
Publication status | Published - 2003 |