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), ..., Ming Li, Multiple discovery, Natural number, Pascal (programming language), Paul Vitányi, Pigeonhole principle, Probability, Programming language, Proof by contradiction, Proof of impossibility, Randomness, Ray Solomonoff, Sankhya (journal), Self-extracting archive, Solomonoff's theory of inductive inference, String (computer science), Turing completeness, Turing machine, Universal Turing machine, Up to, Upper and lower bounds. Expand index (21 more) » « Shrink index
Algorithmic information theory is a subfield of information theory and computer science that concerns itself with the relationship between computation and information.
In algorithmic information theory, algorithmic probability, also known as Solomonoff probability, is a mathematical method of assigning a prior probability to a given observation.
Intuitively, an algorithmically random sequence (or random sequence) is an infinite sequence of binary digits that appears random to any algorithm.
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, abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication.
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 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 is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.
The bit (a portmanteau of binary digit) is a basic unit of information used in computing and digital communications.
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.
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.
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.
Christopher Stewart "Chris" Wallace (26 October 1933 – 7 August 2004) was an Australian computer scientist and physicist.
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.
In mathematics, the term combinatorial proof is often used to mean either of two types of mathematical proof.
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 functions are the basic objects of study in computability theory.
Computation is any type of calculation that includes both arithmetical and non-arithmetical steps and follows a well-defined model, for example an algorithm.
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 deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.
In signal processing, data compression, source coding, or bit-rate reduction involves encoding information using fewer bits than the original representation.
In computer science, a data structure is a data organization and storage format that enables efficient access and modification.
The demoscene is an international computer art subculture focused on producing demos: self-contained, sometimes extremely small, computer programs that produce audio-visual presentations.
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.
Information entropy is the average rate at which information is produced by a stochastic source of data.
A formal system is the name of a logic system usually defined in the mathematical way.
In mathematics, a fractal is an abstract object used to describe and simulate naturally occurring objects.
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.
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 are two theorems of mathematical logic that demonstrate the inherent limitations of every formal axiomatic system containing basic arithmetic.
In mathematics, a geometric series is a series with a constant ratio between successive terms.
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 John Chaitin (born 15 November 1947) is an Argentine-American mathematician and computer scientist.
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.
An incompressible string is a string with Kolmogorov complexity equal to its length, so that it has no shorter encodings.
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.
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.
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 (born 17 January 1963) is a computer scientist who works in the field of artificial intelligence.
In 1973 Kolmogorov proposed a non-probabilistic approach to statistics and model selection.
Leonid Anatolievich Levin (Леони́д Анато́льевич Ле́вин; Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American computer scientist.
In information theory, linguistics and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences.
Lisp (historically, LISP) is a family of computer programming languages with a long history and a distinctive, fully parenthesized prefix notation.
Marcus Hutter (born April 14, 1967) is a German computer scientist.
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.
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 (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.
The Matthew effect, Matthew principle, or Matthew effect of accumulated advantage can be observed in many aspects of life and fields of activity.
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 is a CRC Chair Professor in Bioinformatics, of Computer Science at the University of Waterloo.
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.
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 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 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.
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 is the measure of the likelihood that an event will occur.
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.
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 is the lack of pattern or predictability in events.
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.
Sankhyā: The Indian Journal of Statistics is a quarterly peer-reviewed scientific journal on statistics published by the Indian Statistical Institute (ISI).
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.
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.
In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable.
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.
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.
In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input.
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.
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.
Algorithmic complexity theory, Algorithmic entropy, Chaitin Complexity, Chaitin's incompleteness theorem, Chaitin-Kolmogorov randomness, Chaitin–Kolmogorov randomness, Compressibility (computer science), Conditional complexity, K-complexity, Kolgomorov complexity, Kolmogorov Complexity, Kolmogorov randomness, Kolmogorov-Chaitin complexity, Kolmogorov-Chaitin randomness, Kolmogorov–Chaitin complexity, Kolmogorov–Chaitin randomness, Program-size complexity, Stochastic complexity.