commit 73884c9afea11ec02cf1a6cbc8a8919ccd5cae3e
parent 2bdd3fcc33c1d2f8ffb855ec5711fce20a107879
Author: orx <orx@web>
Date: Sun, 10 Jul 2022 22:09:02 +0200
extension with definitions and Chaitin complexity
Diffstat:
1 file changed, 26 insertions(+), 1 deletion(-)
diff --git a/kolmogorov_complexity.mdwn b/kolmogorov_complexity.mdwn
@@ -1,5 +1,30 @@
The Kolmogorov complexity of an information object, such as a piece of text, is the length of the shortest computer program that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity.
+ KU( x) = min { |p| | p ∈ Σ∗0, U( p) = x }
+
+ U - Turing machine
+ Σ - tape alphabet
+ p - program
+
The program (also called minimal description) received in language grammar system common for both sides triggers generative action on receiver side producing the same language information as by transmission originator.
-This computational principle from 1963 can be related to association in psychology and art. With association, previous experience is recalled from memory by a short impulse or pretext. Vladimir Boudnik in Explosionalism (1949) states that image is built layered on previous influences, memories and experiences. Artwork is a shot which explodes in people's heads (like infinite stream of associations).
+ Historically, the first scientific concept of information
+ originates from Shannon (1949) and defines the ammount
+ of information in the object as bit length of transmission
+ needed to choose the right object from predefined set of elements.
+ This is used in prefix-coding schemes, where the most used symbols
+ are encoded with least bits and least used symbols with more bits.
+
+Kolmogorov computational principle from 1963 can be related to association in psychology and art. With association, previous experience is recalled from memory by a short impulse or pretext. Vladimir Boudnik in Explosionalism (1949) states that image is built layered on previous influences, memories and experiences. Artwork is a shot which explodes in people's heads (like infinite stream of associations).
+
+ o
+
+Chaitin complexity is a minor modification of Kolmogorov complexity, which was discovered independently. We presumed that universal turing machine with alphabet Σ0, works with blanks on the tape to recognize end of programme. It can be a problem, because we cannot chain programmes or put data on tape without other delimiters etc. Chaitin complexity, also called self-delimiting complexity HU( x) of string x in universal machine U is a length of shortest self-delimiting program p, according to which U produces x.
+
+ HU( x) = min { | p | | U( p) = x,
+
+ p is self-delimiting programme, that means the end of the programme
+ can be recognized by reading only all of its symbols and nothing else.
+ As a consequence, such a programme has to be non-prefixed.
+
+Chaitin complexity leads to the definition of algorithmic entropy and information complexity.
