Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T02:55:28.052Z Has data issue: false hasContentIssue false

Computational randomness and lowness*

Published online by Cambridge University Press:  12 March 2014

Sebastiaan A. Terwijn
Affiliation:
Department of Mathematics and Computer Science, Free University of Amsterdam, de Boelelaan 1081 a, 1081 HV Amsterdam, The Netherlands, E-mail: terwijn@cs.vu.nl
Domenico Zambella
Affiliation:
Department of Mathematics, University of Torino, VIA Carlo Alberto 10, 10123 Torino, Italy, E-mail: domenico@dm.unito.it

Abstract

We prove that there are uncountably many sets that are low for the class of Schnorr random reals. We give a purely recursion theoretic characterization of these sets and show that they all have Turing degree incomparable to 0′. This contrasts with a result of Kučera and Terwijn [5] on sets that are low for the class of Martin-Löf random reals.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2001

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable