Complexitat de Kolmogórov

De Viquipèdia
Dreceres ràpides: navegació, cerca

La complexitat de Kolmogórov (el nom de matemàtic Andrei Kolmogórov), 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ó[modifica | modifica el codi]

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 Kolmogórov  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 Kolmogórov, 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[modifica | modifica el codi]

Complexitat de Kolmogórov 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 Kolmogórov 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 Kolmogórov.

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

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