Formalizes the notions of "emergence" and "self-organization".

Proposes a language in which only all polynomial time computable functions can be programmed. A useful constraint for artificial intelligence based on program search?

Shows the emerging necessity to create a formalized language designed to describe complicated systems of regulation of biochemical processes in living cells.

"Important cybernetic principles seem to have been forgotten, though, only to be periodically rediscovered or reinvented in different domains" — true for some current developments in the cognitive sciences.

Complex systems on the boundary between order and chaos may be those best able to adapt by mutation and selection.

Introduces 'predictive information', a measure of the mutual information between the past and the future of a time series. Unique if all observers with prior distributions limited to local interactions need to arrive at the same measure.

Why is our world compressible? How is induction possible? What is the relation between physical and algorithmic entropy?

"There is no set whose size is strictly between that of the integers and that of the real numbers."

Videos and slides on algorithmic complexity, universal induction and learning theory.

On nonlinear filtering, cellular automata and coherent structures.

Suggests a method to obtain a stable approximation of the Kolmogorov complexity for sequences generated by algorithms which are shorter than typical compiler lengths.

Argues that it is unlikely that complexity has any useful value as applied to "real" objects or systems and that even relativising it to an observer has problems. Proposes that complexity can usefully be applied only to constructions within a language.

"This design of a minimalistic universal computer was motivated by my desire to come up with a concrete definition of Kolmogorov Complexity, which studies randomness of individual objects."

Thesis that proposes a methodology to aid engineers in the design and control of complex self-organizing systems.

A formalization of Occam's Razor in which the best hypothesis for a given set of data is the one that leads to the largest compression of the data. Computable!

Great introduction to algorithmic information theory. Explains Kolmogorov complexity, Solomonoff probability, Levins Kt-complexity, "Martin-Loef" randomness, ...

Computational depth is a measure for the amount of “nonrandom” or “useful” information in a string. Considers the difference of various Kolmogorov complexity measures.

An object’s “logical depth” is the time required by a universal Turing machine to generate it from an input that is algorithmically random. Under what conditions do systems undergo unbounded increase of depth in the limit of infinite space and time?

Applies basic concepts of Kolmogorov compexity theory to the set of possible universes. Ideas on life, true randomness, generalization, and learning in a given universe.

If P!=NP (overwhelmingly likely) and if quantum computers can't solve NP problems in polynomal time (likely), NP-complete problems of sufficient largeness can never be solved by anything obeying the laws of physics. (Approximations are possible.)

If positive solutions to a yes/no problem can be verified quickly in polynomial time, can the answers also be computed quickly in polynomial time? There is no proof one way or the other yet.

States that the Boolean satisfiability problem is NP-complete. The Cook-Levin theorem was the first proof of NP-completeness for any problem.

Shows that, while some intuitions from classical computer science must be jettisoned in the light of modern physics, many others emerge nearly unscathed. Quantum computers can't solve NP-complete problems in polynomial time.

An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms.

Draft of a textbook on computational complexity theory. Basic complexity classes, lower bounds for concrete computational models and more advanced topics.

This course tries to connect quantum computing to the wider intellectual world: The measurement problem, computational complexity, cryptography, Gödel, Turing, Penrose, randomness, ...

About the general problem of searching a landscape for a point with specified properties. In particular, is this problem solvable in a reasonable amount of time using the resources of the physical universe?

Complex systems are (complex) networks of some kind that are held to have behavioural and structural features in common.