Content deleted Content added
Sentence was copy-pasted from paper and was suggesting the topic was going to be developed but it isn't, instead now points out to the relevant review papers. |
IznoRepeat (talk | contribs) m add WP:TEMPLATECAT to remove from template; genfixes |
||
Line 46:
Let <math>U: 2^* \to 2^*</math> be a computable function mapping finite binary strings to binary strings. It is a universal function if, and only if, for any computable <math>f: 2^* \to 2^*</math>, we can encode the function in a "program" <math>s_f</math>, such that <math>\forall x \in 2^*, U(s_fx) = f(x) </math>. We can think of <math>U</math> as a program interpreter, which takes in an initial segment describing the program, followed by data that the program should process.
One problem with plain complexity is that <math>C(xy) \not < C(x) + C(y)</math>, because intuitively speaking, there is no general way to tell where to divide an output string just by looking at the concatenated string. We can divide it by specifying the length of <math>x</math> or <math>y</math>, but that would take <math>O(\min(\ln x, \ln y))</math> extra symbols. Indeed, for any <math>c > 0</math> there exists <math>x, y</math> such that <math>C(xy) \geq C(x) + C(y) + c</math>.<ref>(Downey and Hirschfeldt, 2010), Theorem 3.1.4
Typically, inequalities with plain complexity have a term like <math>O(\min(\ln x, \ln y))</math> on one side, whereas the same inequalities with prefix-free complexity have only <math>O(1)</math>.
Line 67:
The prefix-free complexity of a string <math>x</math> is the shortest prefix code that makes the machine output <math>x</math>:<math display="block">K(x) := \min\{|c| : c \in S, U(c) = x\}</math>
==Invariance theorem==
Line 168 ⟶ 169:
* <math>K(x | y) \leq K(x) \leq K(x, y) \leq \max( K(x|y) + K(y), K(y|x) + K(x)) \leq K(x) + K(y) </math>
* <math>K(xy) \leq K(x, y)</math>
Note that there is no way to compare <math>K(xy)</math> and <math>K(x|y)</math> or <math>K(x)</math> or <math>K(y|x)</math> or <math>K(y)</math>. There are strings such that the whole string <math>xy</math> is easy to describe, but its substrings are very hard to describe.
Line 174:
'''Theorem. (symmetry of information)''' <math>K(x, y) = K(x | y, K(y)) + K(y) = K(y, x)</math>.
'''Proof.''' One side is simple. For the other side with <math>K(x, y) \geq K(x | y, K(y)) + K(y)</math>, we need to use a counting argument (page 38 <ref>{{Cite book |last=Hutter |first=Marcus |title=Universal artificial intelligence: sequential decisions based on algorithmic probability |date=2005 |publisher=Springer |isbn=978-3-540-26877-2 |series=Texts in theoretical computer science |___location=Berlin New York}}</ref>).
'''Theorem. (information non-increase)''' For any computable function <math>f</math>, we have <math>K(f(x)) \leq K(x) + K(f)</math>.
Line 357:
* List all strings of length <math display="inline">\leq 2n + 1</math>.
* For each such string <math display="inline">x</math>, enumerate all (prefix-free) programs of length <math>K(x)</math> until one of them does output <math display="inline">x</math>. Record its runtime <math display="inline">n_x</math>.
* Output the largest <math display="inline">n_x</math>.
Line 366 ⟶ 365:
* Run the program <math display="inline">p_{n}</math>, and record its runtime length <math display="inline">BB(n)</math>.
* Generate all programs with length <math display="inline">\leq 2n</math>. Run every one of them for up to <math display="inline">BB(n)</math> steps. Note the outputs of those that have halted.
* Output the string with the lowest lexicographic order that has not been output by any of those.
Let the string output by the program be <math display="inline">x</math>.
The program has length <math display="inline">\leq n + 2\log_2 n + O(1)</math>, where <math>n</math> comes from the length of the Busy Beaver <math display="inline">p_{n}</math>, <math>2\log_2 n</math> comes from using the (prefix-free) [[Elias delta code]] for the number <math>n</math>, and <math>O(1)</math> comes from the rest of the program. Therefore,<math display="block">K(x) \leq n + 2\log_2 n + O(1) \leq 2n</math>for all big <math display="inline">n</math>. Further, since there are only so many possible programs with length <math display="inline">\leq 2n</math>, we have <math display="inline">l(x) \leq 2n + 1</math> by [[pigeonhole principle]].
Line 377 ⟶ 374:
== Universal probability ==
Fix a universal Turing machine <math>U</math>, the same one used to define the (prefix-free) Kolmogorov complexity. Define the (prefix-free) universal probability of a string <math>x</math> to be<math display="block">P(x) = \sum_{U(p) = x} 2^{-l(p)}</math>In other words, it is the probability that, given a uniformly random binary stream as input, the universal Turing machine would halt after reading a certain prefix of the stream, and output <math>x</math>.
Note. <math>U(p) = x</math> does not mean that the input stream is <math>p000\cdots</math>, but that the universal Turing machine would halt at some point after reading the initial segment <math>p</math>, without reading any further input, and that, when it halts, its has written <math>x</math> to the output tape.
Line 441 ⟶ 438:
[[Category:Measures of complexity]]
[[Category:Computational complexity theory]]
[[Category:Data compression]]
| |||