# kolmogorov complexity

Published articles for kolmogorov complexity.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## A Proofless Introduction to Information Theory

DevFeed: [A Proofless Introduction to Information Theory](<https://devfeed.tech/articles/a-proofless-introduction-to-information-theory-40377.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2015/02/16/a-proofless-introduction-to-information-theory/>)

Published: 2015-02-16T09:00:00Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Encoding](<https://devfeed.tech/topics/encoding.md>), [digital](<https://devfeed.tech/topics/digital.md>)

Tags: [channel](<https://devfeed.tech/tags/channel.md>), [coding-theory](<https://devfeed.tech/tags/coding-theory.md>), [communication](<https://devfeed.tech/tags/communication.md>), [compression](<https://devfeed.tech/tags/compression.md>), [digital](<https://devfeed.tech/tags/digital.md>), [encoding](<https://devfeed.tech/tags/encoding.md>), [entropy](<https://devfeed.tech/tags/entropy.md>), [error](<https://devfeed.tech/tags/error.md>), [error-correction](<https://devfeed.tech/tags/error-correction.md>), [example](<https://devfeed.tech/tags/example.md>), [explain](<https://devfeed.tech/tags/explain.md>), [hamming](<https://devfeed.tech/tags/hamming.md>), [independent](<https://devfeed.tech/tags/independent.md>), [information](<https://devfeed.tech/tags/information.md>), [information-theory](<https://devfeed.tech/tags/information-theory.md>), [kolmogorov-complexity](<https://devfeed.tech/tags/kolmogorov-complexity.md>), [language](<https://devfeed.tech/tags/language.md>), [markov](<https://devfeed.tech/tags/markov.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [messages](<https://devfeed.tech/tags/messages.md>), [models](<https://devfeed.tech/tags/models.md>), [probabilistic-method](<https://devfeed.tech/tags/probabilistic-method.md>), [problems](<https://devfeed.tech/tags/problems.md>), [shannon](<https://devfeed.tech/tags/shannon.md>), [theory](<https://devfeed.tech/tags/theory.md>)

### AI overview

A proofless introduction to information theory explains noiseless and noisy communication problems, encoding schemes, entropy, and how entropy differs from Kolmogorov complexity.

### Source excerpt

There are two basic problems in information theory that are very easy to explain. Two people, Alice and Bob, want to communicate over a digital channel over some long period of time, and they know the probability that certain messages will be sent ahead of time. For example, English language sentences are more likely than gibberish, and "Hi" is much more likely than "asphyxiation." The problems are: Say communication is very expensive.

## Information Distance -- A Primer

DevFeed: [Information Distance -- A Primer](<https://devfeed.tech/articles/information-distance-a-primer-40294.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/12/04/information-distance-a-primer/>)

Published: 2012-12-04T08:30:08Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Compression](<https://devfeed.tech/topics/compression.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>)

Tags: [compression](<https://devfeed.tech/tags/compression.md>), [computing](<https://devfeed.tech/tags/computing.md>), [information-theory](<https://devfeed.tech/tags/information-theory.md>), [kolmogorov-complexity](<https://devfeed.tech/tags/kolmogorov-complexity.md>), [machine-learning](<https://devfeed.tech/tags/machine-learning.md>), [metric](<https://devfeed.tech/tags/metric.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>), [universality](<https://devfeed.tech/tags/universality.md>)

### AI overview

This primer introduces information distance through Kolmogorov complexity. It explains how the shortest program relating two strings can reflect their shared information and behave similarly to a metric, with applications to compression and machine learning.

### Source excerpt

This post assumes familiarity with our primer on Kolmogorov complexity. We recommend the uninformed reader begin there. We will do our best to keep consistent notation across both posts. Kolmogorov Complexity as a Metric Over the past fifty years mathematicians have been piling up more and more theorems about Kolmogorov complexity, and for good reason. One of the main interpretations of the Kolmogorov complexity function $ K$ is that for a given string $ x$, $ K(x)$ is the best theoretical compression of $ x$ under any compression scheme.

## Kolmogorov Complexity--A Primer

DevFeed: [Kolmogorov Complexity--A Primer](<https://devfeed.tech/articles/kolmogorov-complexity-a-primer-40270.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/04/21/kolmogorov-complexity-a-primer/>)

Published: 2012-04-21T18:23:41Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>)

Tags: [complexity-theory](<https://devfeed.tech/tags/complexity-theory.md>), [computability-theory](<https://devfeed.tech/tags/computability-theory.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [kolmogorov-complexity](<https://devfeed.tech/tags/kolmogorov-complexity.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [primer](<https://devfeed.tech/tags/primer.md>)

### AI overview

This primer introduces Kolmogorov complexity as a way to formalize how random or complex a string is. It defines the concept using the length of the shortest program that outputs a string, then begins developing a more rigorous formulation using binary programs and Turing-machine concepts.

### Source excerpt

The Complexity of Things Previously on this blog (quite a while ago), we've investigated some simple ideas of using randomness in artistic design (psychedelic art, and earlier randomized css designs). Here we intend to give a more thorough and rigorous introduction to the study of the complexity of strings. This naturally falls into the realm of computability theory and complexity theory, and so we refer the novice reader to our other primers on the subject (Determinism and Finite Automata, Turing Machines, and Complexity Classes; but Turing machines will be the most critical to this discussion).

## Other Complexity Classes

DevFeed: [Other Complexity Classes](<https://devfeed.tech/articles/other-complexity-classes-40264.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/02/29/other-complexity-classes/>)

Published: 2012-02-29T17:12:35Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithms, Complexity](<https://devfeed.tech/topics/algorithms-complexity.md>), [Computing](<https://devfeed.tech/topics/computing.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>)

Tags: [complexity](<https://devfeed.tech/tags/complexity.md>), [computational-complexity](<https://devfeed.tech/tags/computational-complexity.md>), [halting-problem](<https://devfeed.tech/tags/halting-problem.md>), [kolmogorov-complexity](<https://devfeed.tech/tags/kolmogorov-complexity.md>), [nondeterminism](<https://devfeed.tech/tags/nondeterminism.md>), [open-questions](<https://devfeed.tech/tags/open-questions.md>), [oracle](<https://devfeed.tech/tags/oracle.md>), [primer](<https://devfeed.tech/tags/primer.md>), [pspace](<https://devfeed.tech/tags/pspace.md>), [turing-machine](<https://devfeed.tech/tags/turing-machine.md>), [turing-machines](<https://devfeed.tech/tags/turing-machines.md>)

### AI overview

This article introduces complexity classes beyond P and NP, including PSPACE and NPSPACE, and discusses oracle-based classes. It explains that PSPACE equals NPSPACE while many relationships among complexity classes remain open.

### Source excerpt

Not Just Time, But Space Too! So far on this blog we've introduced models for computation, focused on Turing machines and given a short overview of the two most fundamental classes of problems: P and NP. While the most significant open question in the theory of computation is still whether P = NP, it turns out that there are hundreds (almost 500, in fact!) other "classes" of problems whose relationships are more or less unknown.

## Random (Psychedelic) Art

DevFeed: [Random (Psychedelic) Art](<https://devfeed.tech/articles/random-psychedelic-art-40252.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2012/01/01/random-psychedelic-art/>)

Published: 2012-01-01T19:11:28Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Python](<https://devfeed.tech/topics/python.md>), [classes](<https://devfeed.tech/topics/classes.md>), [Programming](<https://devfeed.tech/topics/programming.md>), [Code](<https://devfeed.tech/topics/code.md>)

Tags: [art](<https://devfeed.tech/tags/art.md>), [classes](<https://devfeed.tech/tags/classes.md>), [code](<https://devfeed.tech/tags/code.md>), [color](<https://devfeed.tech/tags/color.md>), [how-to](<https://devfeed.tech/tags/how-to.md>), [kolmogorov-complexity](<https://devfeed.tech/tags/kolmogorov-complexity.md>), [pixel](<https://devfeed.tech/tags/pixel.md>), [primer](<https://devfeed.tech/tags/primer.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [random-number-generators](<https://devfeed.tech/tags/random-number-generators.md>)

### AI overview

A Python tutorial that introduces objects and classes while constructing randomized psychedelic art. It explains how images are represented as pixel grids with RGB color values and uses mathematical functions to generate colors.

### Source excerpt

And a Pinch of Python Next semester I am a lab TA for an introductory programming course, and it's taught in Python. My Python experience has a number of gaps in it, so we'll have the opportunity for a few more Python primers, and small exercises to go along with it. This time, we'll be investigating the basics of objects and classes, and have some fun with image construction using the Python Imaging Library.

## False Proof--All Numbers are Describable in at Most Twenty Words

DevFeed: [False Proof--All Numbers are Describable in at Most Twenty Words](<https://devfeed.tech/articles/false-proof-all-numbers-are-describable-in-at-most-twenty-words-40233.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2011/07/28/false-proof-twenty-word/>)

Published: 2011-07-28T16:03:27Z

Content type: article

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Mathematics](<https://devfeed.tech/topics/mathematics.md>), [Math and Logic](<https://devfeed.tech/topics/math-and-logic.md>), [Statement](<https://devfeed.tech/topics/statement.md>)

Tags: [computer](<https://devfeed.tech/tags/computer.md>), [false-proof](<https://devfeed.tech/tags/false-proof.md>), [kolmogorov-complexity](<https://devfeed.tech/tags/kolmogorov-complexity.md>), [language](<https://devfeed.tech/tags/language.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [program](<https://devfeed.tech/tags/program.md>), [set-theory](<https://devfeed.tech/tags/set-theory.md>), [turing-machine](<https://devfeed.tech/tags/turing-machine.md>), [well-ordering](<https://devfeed.tech/tags/well-ordering.md>)

### AI overview

The article examines a false proof claiming that every natural number can be described in fewer than twenty words. It explains that the contradiction arises from imprecise notions of description and set construction, connecting the issue to Russell's paradox and the Richard-Berry paradox.

### Source excerpt

Problem: Show that every natural number can be unambiguously described in fewer than twenty words. "Solution": Suppose to the contrary that not every natural number can be so described. Let $ S$ be the set of all natural numbers which are describable in fewer than twenty words. Consider $ R = \mathbb{N}-S$, the set of all words which cannot be described in fewer than twenty words. Since $ R$ is a subset of the natural numbers, which is well-ordered, it has a unique smallest element which we call $ r$.