×

Computation with narrow CTCs. (English) Zbl 1330.68080

Calude, Cristian S. (ed.) et al., Unconventional computation. 10th international conference, UC 2011, Turku, Finland, June 6–10, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21340-3/pbk). Lecture Notes in Computer Science 6714, 201-211 (2011).
Summary: We examine some variants of computation with closed timelike curves (CTCs), where various restrictions are imposed on the memory of the computer, and the information carrying capacity and range of the CTC. We give full characterizations of the classes of languages recognized by polynomial time probabilistic and quantum computers that can send a single classical bit to their own past. Such narrow CTCs are demonstrated to add the power of limited nondeterminism to deterministic computers, and lead to exponential speedup in constant-space probabilistic and quantum computation.
For the entire collection see [Zbl 1215.68010].

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI arXiv