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]

References

• [BA04] Selmer Bringsjord and Konstantine Arkoudas, The modal argument for hypercomputing minds, Theoretical Computer Science 317 (2004), no. 1-3, 167 – 190, Super-Recursive Algorithms and Hypercomputation.
• [BBC98] G. Brassard, S. L. Braunstein, and R. Cleve, Teleportation as a quantum computation, Physica D 120 (1998), 43–47.
• [BS10] John Baez and Mike Stay, Algorithmic thermodynamics, preprint, 2010.
• [Dav06] Davis, Why there is no such discipline as hypercomputation.
• [For09] Lance Fortnow, The status of the p versus np problem, Communications of the Association of Computing Machinery 52 (2009), no. 9, 78–86.
• [LV93] Li and Vitanyi, An introduction to kolmogorov complexity, 1993.
• [MGG01] Andrés Moreira, Annahí Gajardo, and Eric Goles, Dynamical behavior and complexity of langton’s ant, Complex. 6 (2001), no. 4, 46–51.
• [Pre01] Preskill, Quantum information theory lecture notes, 2001.
• [She09] Alexander Shen, Algorithmic information theory and foundations of probability.
• [Svo05] Karl Svozil, Quantum logic. a brief outline.
• [TS02] Christof Teuscher and Moshe Sipper, Hypercomputation: hype or computation?, Commun. ACM 45 (2002), no. 8, 23–24.
• [Zus70] K. Zuse, Calculating space, Massachusetts Institute of Technology Technical Translation AZT-70-164-GEMIT (Project MAC). Cambridge (1970).