Communication
Install
Faster access than browser!

# Kolmogorov complexity

In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined programming language) that produces the object as output. [1]

71 relations: Algorithmic information theory, Algorithmic probability, Algorithmically random sequence, Andrey Kolmogorov, ASCII, Axiomatic system, Bayesian probability, Berry paradox, Big O notation, Bit, Blum axioms, Cantor's diagonal argument, Chaitin's constant, Chris Wallace (computer scientist), Code golf, Combinatorial proof, Complexity, Computable function, Computation, Computer program, Computer science, Data compression, Data structure, Demoscene, Discrete uniform distribution, Entropy (information theory), Formal system, Fractal, Full employment theorem, Gödel numbering, Gödel's incompleteness theorems, Geometric series, Grammar induction, Gregory Chaitin, Halting problem, Incompressible string, Inductive reasoning, Interpreter (computing), Java virtual machine, Jürgen Schmidhuber, Kolmogorov structure function, Leonid Levin, Levenshtein distance, Lisp (programming language), Marcus Hutter, Markov information source, Martingale (probability theory), Mathematics, Matthew effect, Measure (mathematics), ... Expand index (21 more) »

## Algorithmic information theory

Algorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information.

## Algorithmic probability

In algorithmic information theory, algorithmic probability, also known as Solomonoff probability, is a mathematical method of assigning a prior probability to a given observation.

## Algorithmically random sequence

Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm.

## Andrey Kolmogorov

Andrey Nikolaevich Kolmogorov (a, 25 April 1903 – 20 October 1987) was a 20th-century Soviet mathematician who made significant contributions to the mathematics of probability theory, topology, intuitionistic logic, turbulence, classical mechanics, algorithmic information theory and computational complexity.

## ASCII

ASCII, abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication.

## Axiomatic system

In mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems.

## Bayesian probability

Bayesian probability is an interpretation of the concept of probability, in which, instead of frequency or propensity of some phenomenon, probability is interpreted as reasonable expectation representing a state of knowledge or as quantification of a personal belief.

The Berry paradox is a self-referential paradox arising from an expression like "The smallest positive integer not definable in under sixty letters" (note that this defining phrase has fifty-seven letters).

## Big O notation

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

## Bit

The bit (a portmanteau of binary digit) is a basic unit of information used in computing and digital communications.

## Blum axioms

In computational complexity theory the Blum axioms or Blum complexity axioms are axioms that specify desirable properties of complexity measures on the set of computable functions.

## Cantor's diagonal argument

In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers.

## Chaitin's constant

In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number) or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will halt.

## Chris Wallace (computer scientist)

Christopher Stewart "Chris" Wallace (26 October 1933 – 7 August 2004) was an Australian computer scientist and physicist.

## Code golf

Code golf is a type of recreational computer programming competition in which participants strive to achieve the shortest possible source code that implements a certain algorithm.

## Combinatorial proof

In mathematics, the term combinatorial proof is often used to mean either of two types of mathematical proof.

## Complexity

Complexity characterises the behaviour of a system or model whose components interact in multiple ways and follow local rules, meaning there is no reasonable higher instruction to define the various possible interactions.

## Computable function

Computable functions are the basic objects of study in computability theory.

## Computation

Computation is any type of calculation that includes both arithmetical and non-arithmetical steps and follows a well-defined model, for example an algorithm.

## Computer program

A computer program is a collection of instructions for performing a specific task that is designed to solve a specific class of problems.

## Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

## Data compression

In signal processing, data compression, source coding, or bit-rate reduction involves encoding information using fewer bits than the original representation.

## Data structure

In computer science, a data structure is a data organization and storage format that enables efficient access and modification.

## Demoscene

The demoscene is an international computer art subculture focused on producing demos: self-contained, sometimes extremely small, computer programs that produce audio-visual presentations.

## Discrete uniform distribution

In probability theory and statistics, the discrete uniform distribution is a symmetric probability distribution whereby a finite number of values are equally likely to be observed; every one of n values has equal probability 1/n.

## Entropy (information theory)

Information entropy is the average rate at which information is produced by a stochastic source of data.

## Formal system

A formal system is the name of a logic system usually defined in the mathematical way.

## Fractal

In mathematics, a fractal is an abstract object used to describe and simulate naturally occurring objects.

## Full employment theorem

In computer science and mathematics, a full employment theorem is a theorem which states that no algorithm can optimally perform a particular task done by some class of professionals.

## Gödel numbering

In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number.

## Gödel's incompleteness theorems

Gödel's incompleteness theorems are two theorems of mathematical logic that demonstrate the inherent limitations of every formal axiomatic system containing basic arithmetic.

## Geometric series

In mathematics, a geometric series is a series with a constant ratio between successive terms.

## Grammar induction

Grammar induction (or grammatical inference) is the process in machine learning of learning a formal grammar (usually as a collection of re-write rules or productions or alternatively as a finite state machine or automaton of some kind) from a set of observations, thus constructing a model which accounts for the characteristics of the observed objects.

## Gregory Chaitin

Gregory John Chaitin (born 15 November 1947) is an Argentine-American mathematician and computer scientist.

## Halting problem

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever.

## Incompressible string

An incompressible string is a string with Kolmogorov complexity equal to its length, so that it has no shorter encodings.

## Inductive reasoning

Inductive reasoning (as opposed to ''deductive'' reasoning or ''abductive'' reasoning) is a method of reasoning in which the premises are viewed as supplying some evidence for the truth of the conclusion.

## Interpreter (computing)

In computer science, an interpreter is a computer program that directly executes, i.e. performs, instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program.

## Java virtual machine

A Java virtual machine (JVM) is a virtual machine that enables a computer to run Java programs as well as programs written in other languages and compiled to Java bytecode.

## Jürgen Schmidhuber

Jürgen Schmidhuber (born 17 January 1963) is a computer scientist who works in the field of artificial intelligence.

## Kolmogorov structure function

In 1973 Kolmogorov proposed a non-probabilistic approach to statistics and model selection.

## Leonid Levin

Leonid Anatolievich Levin (Леони́д Анато́льевич Ле́вин; Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American computer scientist.

## Levenshtein distance

In information theory, linguistics and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences.

## Lisp (programming language)

Lisp (historically, LISP) is a family of computer programming languages with a long history and a distinctive, fully parenthesized prefix notation.

## Marcus Hutter

Marcus Hutter (born April 14, 1967) is a German computer scientist.

## Markov information source

In mathematics, a Markov information source, or simply, a Markov source, is an information source whose underlying dynamics are given by a stationary finite Markov chain.

## Martingale (probability theory)

In probability theory, a martingale is a sequence of random variables (i.e., a stochastic process) for which, at a particular time in the realized sequence, the expectation of the next value in the sequence is equal to the present observed value even given knowledge of all prior observed values.

## Mathematics

Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.

## Matthew effect

The Matthew effect, Matthew principle, or Matthew effect of accumulated advantage can be observed in many aspects of life and fields of activity.

## Measure (mathematics)

In mathematical analysis, a measure on a set is a systematic way to assign a number to each suitable subset of that set, intuitively interpreted as its size.

## Ming Li

Ming Li is a CRC Chair Professor in Bioinformatics, of Computer Science at the University of Waterloo.

## Multiple discovery

The concept of multiple discovery (also known as simultaneous invention) is the hypothesis that most scientific discoveries and inventions are made independently and more or less simultaneously by multiple scientists and inventors.

## Natural number

In mathematics, the natural numbers are those used for counting (as in "there are six coins on the table") and ordering (as in "this is the third largest city in the country").

## Pascal (programming language)

Pascal is an imperative and procedural programming language, which Niklaus Wirth designed in 1968–69 and published in 1970, as a small, efficient language intended to encourage good programming practices using structured programming and data structuring. It is named in honor of the French mathematician, philosopher and physicist Blaise Pascal. Pascal was developed on the pattern of the ALGOL 60 language. Wirth had already developed several improvements to this language as part of the ALGOL X proposals, but these were not accepted and Pascal was developed separately and released in 1970. A derivative known as Object Pascal designed for object-oriented programming was developed in 1985; this was used by Apple Computer and Borland in the late 1980s and later developed into Delphi on the Microsoft Windows platform. Extensions to the Pascal concepts led to the Pascal-like languages Modula-2 and Oberon.

## Paul Vitányi

Paul Michael Béla Vitányi (born 21 July 1944) is a Dutch computer scientist, Professor of Computer Science at the University of Amsterdam and researcher at the Dutch Centrum Wiskunde & Informatica.

## Pigeonhole principle

In mathematics, the pigeonhole principle states that if items are put into containers, with, then at least one container must contain more than one item.

## Probability

Probability is the measure of the likelihood that an event will occur.

## Programming language

A programming language is a formal language that specifies a set of instructions that can be used to produce various kinds of output.

In logic, proof by contradiction is a form of proof, and more specifically a form of indirect proof, that establishes the truth or validity of a proposition.

## Proof of impossibility

A proof of impossibility, also known as negative proof, proof of an impossibility theorem, or negative result, is a proof demonstrating that a particular problem cannot be solved, or cannot be solved in general.

## Randomness

Randomness is the lack of pattern or predictability in events.

## Ray Solomonoff

Ray Solomonoff (July 25, 1926 – December 7, 2009) was the inventor of algorithmic probability, his General Theory of Inductive Inference (also known as Universal Inductive Inference),Samuel Rathmanner and Marcus Hutter.

## Sankhya (journal)

Sankhyā: The Indian Journal of Statistics is a quarterly peer-reviewed scientific journal on statistics published by the Indian Statistical Institute (ISI).

## Self-extracting archive

A self-extracting archive (SFX/SEA) is a computer executable program which contains compressed data in an archive file combined with machine-executable program instructions to extract this information on a compatible operating system and without the necessity for a suitable extractor to be already installed on the target computer.

## Solomonoff's theory of inductive inference

Ray Solomonoff's theory of universal inductive inference is a theory of prediction based on logical observations, such as predicting the next symbol based upon a given series of symbols.

## String (computer science)

In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.

## Turing completeness

In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine.

## Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

## Universal Turing machine

In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input.

## Up to

In mathematics, the phrase up to appears in discussions about the elements of a set (say S), and the conditions under which subsets of those elements may be considered equivalent.

## Upper and lower bounds

In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set (K, ≤) is an element of K which is greater than or equal to every element of S. The term lower bound is defined dually as an element of K which is less than or equal to every element of S. A set with an upper bound is said to be bounded from above by that bound, a set with a lower bound is said to be bounded from below by that bound.

## References

Hey! We are on Facebook now! »