Mathematics Unlimited - 2001 and Beyond

0404158 - UIVT-O 20000246 RIV DE eng M - Část monografie knihy
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
Grant CEP: GA ČR GA201/98/0717
Grant ostatní: ALCOM-FT(XE) IST-1999-14186
Výzkumný záměr: AV0Z1030915
Klíčová slova: Turing machine * non-uniform complexity * Church-Turing thesis * the Internet * evolution
Kód oboru RIV: BA - Obecná matematika

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.
Trvalý link: http://hdl.handle.net/11104/0124425