View:
- no detail
- some detail
- full detail
The descriptive complexity of strings
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.0002
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy
This chapter develops the theory of plain Kolmogorov complexity, and then of prefix-free Kolmogorov complexity. A main technical tool for later chapters is the Machine Existence (or Kraft–Chaitin) ... More
View:
- no detail
- some detail
- full detail
