Journal Article

Computation with multiple CTCs of fixed length and width

Yakaryılmaz, Abuzer, Say, A. C. Cem

2012

Overview

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 decided by polynomial time probabilistic and quantum computers that can send a single classical bit to their own past. We show that, given a time machine with constant negative delay, one can implement CTC-based computations without the need to know about the runtime beforehand. Chaining multiple instances of such fixed-length CTCs, the power of postselection can be endowed to deterministic computers, all languages in can be decided with no error in worst-case polynomial time, and all Turing-decidable languages can be decided in constant expected time. We provide proofs of the following facts for weaker models: Augmenting probabilistic computers with a single CTC leads to an improvement in language recognition power. Quantum computers under these restrictions are more powerful than their classical counterparts. Some deterministic models assisted with multiple CTCs are more powerful than those with a single CTC.

• Publisher: Springer Netherlands,Springer Nature B.V
• Subject: Algorithms / Artificial Intelligence / Complex Systems / Computation / Computer Science / Computer simulation / Constrictions / Delay / Evolutionary Biology / Mathematical models / Polynomials / Probabilistic methods / Probability theory / Processor Architectures / Quantum computers / Quantum theory / Theory of Computation