Number of the records: 1
Relativistic Computers and Non-Uniform Complexity Theory
- 1.0404692 - UIVT-O 20020158 RIV DE eng C - Conference Paper (international conference)
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]
R&D Projects: GA ČR GA201/02/1456
Grant - others:ALCOM-FT(XE) IST-1999-14186
Institutional research plan: AV0Z1030915
Keywords : relativistic computing * Turing machine * computability * arithmetical hierarchy
Subject RIV: BA - General Mathematics
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.
Permanent Link: http://hdl.handle.net/11104/0124931
Number of the records: 1