Questions in Information Theory II: Complexity and Algorithmic Complexity

Wednesday, October 13th, 2010 | Author:

See also: Questions part I - Information and Entropy

Questions part II - Complexity and Algorithmic Complexity [LV93]

  1. Can we capture the concepts of simplicity, Occam’s razor and complexity by the notion of algorithmic complexity? [LV93] [She09]

    “What is simplicity? Simplicity is the shortest path to a solution.” – Ward Cunningham, 2004

    “To repeat, we consider a computer program to be a theory for its output, that is the essential idea, and both theory and output are finite strings of bits whose size can be compared. And the best theory is the smallest program that produces that data, that precise output. That’s our version of what some people call Occam’s
    razor.” – Gregory Chaitin, 2008

  2. What is the relation between algorithmic complexity and entropy? [LV93] [BS10]
  3. How is semantics (e.g. of the number pi) related to algorithmic complexity?
  4. How does complexity arise from syntactic information? [MGG01]
  5. Do different degrees of complexity correspond to qualitative differences in cognitive/reactive behaviour?
  6. Is the Church-Turing hypothesis true and if so, does it matter?
    Is neural computation fundamentally distinct from electronic computation?
    Is hypercomputation possible? [TS02] [BA04] [Dav06]

    “A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine.” – Alan Turing, 1948

  7. How can one define computability without referring to Turing machines?
  8. P vs. NP: is P=NP or not? [For09]
    Is there a practical benefit of P=NP or of a proof of this?
  9. Is the concept of a non-deterministic Turing machine implementable by natural computing just like deterministic Turing machines are implementable by home computers?
  10. Would it be a good idea to adapt the concept of non-deterministic Turing machines to real non-deterministic systems?
  11. Can we tell for a general physical system whether it is a Turing machine? [Zus70]

    “All processes, whether they are produced by human effort or occur spontaneously in nature, can be viewed as computations.” – Stephen Wolfram, 2002

  12. Can a Turing machine simulate itself?
  13. Does classical computer science “apply” to quantum computation? [Pre01] [Svo05] [BBC98]



Leave a Reply