Complexitat de Kolmogórov

La complexitat de Kolmogorov (el nom de matemàtic Andrey Kolmogorov), també anomenat atzar complex o la complexitat algorísmica, és uns Funció (més precisament un tots funcions) per avaluar la complexitat de la computació un nombre o una suite.

Introducció

Penseu en la possibilitat d'una màquina de calcular M pot executar programes. Diuen que aquesta màquina és universal si es pot emular qualsevol altra màquina de calcular. El màquina universal de Turing és un exemple.

Hi ha $P_m$ Tots els programes escrits per a la màquina $M$. Perquè un programa $p/a P_m$, hi ha $l (p)$ la longitud en el nombre d'instruccions de la màquina $M$ i $s (p)$ la seva producció. La complexitat de Kolmogorov $k_m (x)$, o la complexitat algorísmica, un resultat $x = (x_i) _i$ per a una màquina de $M$ és ? nega:

$K_M (x) = \min_{p\in P_M} \{l(p), s(p) = x\}$.

Així que la longitud dels més petits programa escrit per a la màquina $M$ que genera més $x$. Una constant de cadena ha de baixa complexitat, perquè els programes que generen pot ser molt curt.

Segueix sent en quina mesura la funció $k_m (x)$ Depèn de la màquina $M$, ja que molt pot imaginar una màquina amb instruccions simples per generar algun complex suites . La resposta és: no és una màquina universal $U$ (sovint anomenat additiva òptima) tal que per a qualsevol màquina $M$ és una constant $c_M$ la comprovació de qualsevol segueixi $x$ la desigualtat de

$K_U (x)\leq k_m (x)+c_M$

Intuïtivament, $c_M$ és la longitud d'un intèrpret (o emulador), escrit per a la màquina $U$, el llenguatge utilitzat per l' Màquina $M$. Això es coneix com la universalitat de la complexitat de Kolmogorov, que no depèn, en una constant additiva, amb el maquinari subjacent.

La seqüència pot ser considerat com a més "aleatori" de la seva complexitat és gran en relació a la seva mida. Des d'aquesta perspectiva, el p nombres decimals, $i$ o $\sqrt2$ en realitat no són aleatòries perquè hi ha algoritmes molt simples per calcular-les.

Propietats

Complexitat de Kolmogorov no és computable. En altres paraules, no hi ha un programa informàtic que té com a entrada s , i torna K (es) de . Per contradicció, suposem que aquesta funció existeix Kolmá , la mida d'aquesta funció (nombre de caràcters) és conegut i igual a k. A continuació, podria escriure el següent algorisme:

 n : = 1
Mentre    Kolmá (n) <100  k   do:
 n: n = 1 
  Fi Mentre
Escriure  n   

Així, aquest algorisme, escriu el nombre més petit que la complexitat de Kolmogorov major k 100 (aquest nombre és necessàriament perquè només hi ha un nombre finit de molts programes de mides inferiors a 100 K i hi ha un infinit dels nombres naturals).

No obstant això, l'algorisme anterior s'escriu amb caràcters poc menys de 100 k, per la qual cosa és d'una complexitat inferior a 100 K, o que acaba d'escriure un nombre de complexitat més gran que 100 K, la qual cosa és absurd.

Així que no hi ha cap funció que calcula la complexitat de Kolmogorov.

Vegeu també

• Màquina de Turing
• Teoria algorísmica de la informació
• Sèrie aleatòra

Referències

• Una part d'aquest article (o abans) és una adaptació de (Article), sota llicència GFDL.