*André Nies*

- 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

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 lowness for weak 2-randomness. To prove the results, the chapter develops the accounting, cost function and decanter methods, and the golden run construction. The Main Lemma, derived from the golden run construction, yields a general way to restrict K-trivial sets.Less

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 lowness for weak 2-randomness. To prove the results, the chapter develops the accounting, cost function and decanter methods, and the golden run construction. The Main Lemma, derived from the golden run construction, yields a general way to restrict K-trivial sets.

*André Nies*

- 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

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 randomness. It also studies strong jump traceability and its relationship to the cost function method of Chapter 5. Many research problems are posed.Less

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 randomness. It also studies strong jump traceability and its relationship to the cost function method of Chapter 5. Many research problems are posed.

*André Nies*

- 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

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 sets, this chapter introduces classes of similar complexity, namely, classes of sets sharing a certain complexity property.Less

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 sets, this chapter introduces classes of similar complexity, namely, classes of sets sharing a certain complexity property.

*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

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 tools can also be used to introduce mathematical counterparts for the intuitive notion of randomness of a set. Recent research shows that, conversely, concepts and methods originating from randomness enrich computability theory. The book is about these two aspects of sets of natural numbers and about their interplay. For the first aspect, lowness and highness properties of sets are introduced. For the second aspect, firstly randomness of finite objects are studied, and then randomness of sets of natural numbers. A hierarchy of mathematical randomness notions is established. Each notion matches the intuition idea of randomness to some extent. The advantages and drawbacks of notions weaker and stronger than Martin-Löf randomness are discussed. The main topic is the interplay of the computability and randomness aspects. Research on this interplay has advanced rapidly in recent years. One chapter focuses on injury-free solutions to Post's problem. A core chapter contains a comprehensible treatment of lowness properties below the halting problem, and how they relate to K triviality. Each chapter exposes how the complexity properties are related to randomness. The book also contains analogs in the area of higher computability theory of results from the preceding chapters, reflecting very recent research.Less

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 tools can also be used to introduce mathematical counterparts for the intuitive notion of randomness of a set. Recent research shows that, conversely, concepts and methods originating from randomness enrich computability theory. The book is about these two aspects of sets of natural numbers and about their interplay. For the first aspect, lowness and highness properties of sets are introduced. For the second aspect, firstly randomness of finite objects are studied, and then randomness of sets of natural numbers. A hierarchy of mathematical randomness notions is established. Each notion matches the intuition idea of randomness to some extent. The advantages and drawbacks of notions weaker and stronger than Martin-Löf randomness are discussed. The main topic is the interplay of the computability and randomness aspects. Research on this interplay has advanced rapidly in recent years. One chapter focuses on injury-free solutions to Post's problem. A core chapter contains a comprehensible treatment of lowness properties below the halting problem, and how they relate to K triviality. Each chapter exposes how the complexity properties are related to randomness. The book also contains analogs in the area of higher computability theory of results from the preceding chapters, reflecting very recent research.