Relativistic Computers and Non-Uniform Complexity Theory

0404692 - UIVT-O 20020158 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Wiedermann, Jiří - van Leeuwen, J.
Relativistic Computers and Non-Uniform Complexity Theory.
Unconventional Models of Computation. Berlin: Springer, 2002 - (Calude, C.; Dinneen, M.; Peper, F.), s. 287-299. Lecture Notes in Computer Science, 2509. ISBN 3-540-44311-8. ISSN 0302-9743.
[UMC'02. Unconvential Models of Computation /3./. Kobe (JP), 15.10.2002-19.10.2002]
Grant CEP: GA ČR GA201/02/1456
Grant ostatní: ALCOM-FT(XE) IST-1999-14186
Výzkumný záměr: AV0Z1030915
Klíčová slova: relativistic computing * Turing machine * computability * arithmetical hierarchy
Kód oboru RIV: BA - Obecná matematika

Recent research in theoretical physics on 'Malament-Hogarth space-times' indicates that so-called relativistic computers can be conceived that can carry out certain classically undecidable queries in finite time. We observe that the relativistic Turing machines which model these computations recognize precisely the \delta_2\ sets of the Arithmetical Hierarchy. We also show further results concerning the complexity - theoretical analysis of relativistic computations.
Trvalý link: http://hdl.handle.net/11104/0124931