Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Todd Ebert:

TR02-056 | 19th September 2002
Todd Ebert, Wolfgang Merkle, Heribert Vollmer

On the Autoreducibility of Random Sequences

A binary sequence A=A(0)A(1).... is called i.o. Turing-autoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs either A(x) or a don't-know symbol on any given input x, and outputs A(x) for infinitely many x. If in addition ... more >>>

ISSN 1433-8092 | Imprint