Computation with multiple CTCs of fixed length and width

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 probabil...

Full description

Saved in:
Bibliographic Details
Published in:Natural computing 2012-12, Vol.11 (4), p.579-594
Main Authors: Say, A. C. Cem, Yakaryılmaz, Abuzer
Format: Article
Language:English
Subjects:
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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 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.
ISSN:1567-7818
1572-9796
DOI:10.1007/s11047-012-9337-6