Jump to ContentJump to Main Navigation

You are looking at 1-4 of 4 items

  • Keywords: lowness properties x
Clear All Modify Search

View:

Lowness properties and K-triviality

André Nies

in Computability and Randomness

Published in print:
2009
Published Online:
May 2009
ISBN:
9780199230761
eISBN:
9780191710988
Item type:
chapter
Publisher:
Oxford University Press
DOI:
10.1093/acprof:oso/9780199230761.003.0005
Subject:
Mathematics, Logic / Computer Science / Mathematical Philosophy

This chapter shows the equivalence of K-triviality and lowness for Martin–Löf randomness. This coincidence extends to other lowness properties, such as being a base for Martin–Löf randomness, and ... More


Classes of computational complexity

André Nies

in Computability and Randomness

Published in print:
2009
Published Online:
May 2009
ISBN:
9780199230761
eISBN:
9780191710988
Item type:
chapter
Publisher:
Oxford University Press
DOI:
10.1093/acprof:oso/9780199230761.003.0008
Subject:
Mathematics, Logic / Computer Science / Mathematical Philosophy

This chapter studies lowness properties of sets not necessarily below the halting problem. The main new notions are all related to traceability. It characterizes lowness for Schnorr, and computable ... More


The complexity of sets

André Nies

in Computability and Randomness

Published in print:
2009
Published Online:
May 2009
ISBN:
9780199230761
eISBN:
9780191710988
Item type:
chapter
Publisher:
Oxford University Press
DOI:
10.1093/acprof:oso/9780199230761.003.0001
Subject:
Mathematics, Logic / Computer Science / Mathematical Philosophy

This chapter studies the complexity of sets of natural numbers. There are two interrelated types of complexity, these are computational and descriptive. In both cases, to understand the complexity of ... More


Computability and Randomness

André Nies

Published in print:
2009
Published Online:
May 2009
ISBN:
9780199230761
eISBN:
9780191710988
Item type:
book
Publisher:
Oxford University Press
DOI:
10.1093/acprof:oso/9780199230761.001.0001
Subject:
Mathematics, Logic / Computer Science / Mathematical Philosophy

The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the complexity aspect. However, computability theoretic ... More


View: