A program in mathematical logic that seeks to determine which axioms are required to prove certain theorems of mathematics.

"It is possible to translate any Turing machine into a set of Wang tiles, such that the Wang tiles can tile the plane if and only if the Turing machine will never halt. [..] In a sense, Wang tiles have computational power equivalent to that of a TM."

The Up series consists of seven documentary films that have followed the lives of fourteen British children since 1964, when they were seven years old.

A superseded, or obsolete, scientific theory is a scientific theory that was once commonly accepted but is no longer considered the most complete description of reality by mainstream science; or a falsifiable theory which has been shown to be false.

Shows how the P=NP? problem has a strange, self-referential character that’s not quite like anything previously encountered in mathematics, including in the work of Gödel and Turing.

Unsolved problems in biology, chemistry, cognitive science, computer science, economics, Egyptiology, linguistics, mathematics, medicine, neuroscience, philosophy and physics.

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.

Given our knowledge of the way the world is, how can we know the way the world ought to be? Hume's Guillotine: Such a derivation is impossible.

The set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterisation of the class NP which does not invoke a model of computation such as a Turing machine.

The theory defines sentience as the relationship between the information processing rate (bit/s) of each indivdiual processing unit (neuron), the weight/size of a single unit and the total number of processing units (expressed as mass).

It has been suggested that consciousness is merely a side-effect of neuronal functions, an epiphenomenon of brain states. On the face of it, Libet's experiments offer support to this theory [..].

Alan Turing proved in 1936 that a general algorithm to decide for all program-input pairs whether a program will halt or run forever cannot exist.

For any consistent formal theory that proves basic arithmetical truths, it is possible to construct an arithmetical statement that is true but not provable in the theory. That is, any consistent theory of a certain expressive strength is incomplete.

In a theory with Peano arithmetic, for any formula P, if it is provable that "if P is provable then P", then P is provable.

The Kolmogorov complexity of an object such as a piece of text is a measure of the computational resources needed to specify the object.

For any non-trivial property of partial functions, the question of whether a given algorithm computes a partial function with this property is undecidable.

Finds the shortest path between any two Wikipedia entries.

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

The VC dimension (for Vapnik Chervonenkis dimension) is a measure of the capacity of a statistical classification algorithm.

Claims that any calculation that is possible can be performed by an algorithm running on a computer, provided that sufficient time and storage space are available.

Anthropic bias is a term coined by the philosopher Nick Bostrom, as an expression for the bias arising when "your evidence is biased by observation selection effects".

The tragedy of the commons is a phrase used to refer to a class of phenomena that involve a conflict for resources between individual interests and the common good.

Bayesian inference is statistical inference in which evidence or observations are used to update or to newly infer the probability that a hypothesis may be true.