Mathematics Unlimited - 2001 and Beyond

0404158 - UIVT-O 20000246 RIV DE eng M - Monography Chapter
van Leeuwen, J. - Wiedermann, Jiří
The Turing Machine Paradigm in Contemporary Computing.
Mathematics Unlimited - 2001 and Beyond. Berlin: Springer, 2001 - (Engquist, B.; Schmid, W.), s. 1139-1155. ISBN 3-540-66913-2
R&D Projects: GA ČR GA201/98/0717
Grant - others:ALCOM-FT(XE) IST-1999-14186
Institutional research plan: AV0Z1030915
Keywords : Turing machine * non-uniform complexity * Church-Turing thesis * the Internet * evolution
Subject RIV: BA - General Mathematics

The classical Church-Turing thesis asserts that every algorithm can be described by means of a standard Turing machine. Computations as performed e.g. by current PC or large distributed systems do not fit under this paradigm. We propose an extension of the above thesis towards non-uniform interactive computations that states that every computation of that sort can be described as an interactive TM with advice. Examples range from standard PC with upgradable hardware, up to the Internet.
Permanent Link: http://hdl.handle.net/11104/0124425