“Information theory must precede probability theory, and not be based on it. By the very essence of this discipline, the foundations of information theory have a finite combinatorial character.” Kolmogorov, A. N. (1983). Combinatorial foundations of information theory and the calculus of probabilities.
Russian mathematical surveys, 38 (4), 29-40.
“it is clear that elements requiring an extremely large number of words for their definition should be considered as having an extremely low probability.” (Borel E., 1909 p. 272).
Questa sezione si distacca dalla probabilità classica che abbiamo fatto in questo corso, ma per vicinanza metto qui l’appunto.
Prefix Complexity
Definizione
$$ K(s) = min_{p}\left\{ \lvert p \rvert : U_{pr}(p) = s \right\} $$L’unica differenza con Kolmogorov complexity è che qui usiamo una macchina di turing con prefix codes.
Intuizione
Una macchina che esegue programmi random può produrre una certa stringa? Definiamo la probabilità come
$$ P(x) = \sum_{p:U(p)=x} 2^{-l(p)} $$Che è un modo per dire generare in modo random certi programmi. Il valore di sopra è simile a
$$ P(x) \approx 2^{-K(x)} $$Per $K$ vedi Kolmogorov complexity. TODO: cercare di capire perché limitarsi solamente alla versione più corta.
Prefix Machine
Da Leonid Levin, risolve il problema di termine di interpretazione, perché prefix codes hanno valore sempre minore di 1 come descritto in Entropy#Krafts Inequality. Se non si escludono, fanno qualcosa di brutto con quel valore di probabilità, perché la somma di tutti avrebbe superato $1$ e non avrebbe soddisfatto gli assiomi La proprietà principale è che non esistono due programmi per questa macchina tale per cui uno sia prefisso di altro.
Self delimiting codes
Con i prefix codes posso avere delle cose self-delimiting, perché so quando un codice finisce e posso interpretarlo per la proprietà dei prefissi.
One example of self-delimiting code is the Gamma Code. Where there are ones to mark the length of the next sequence. You don’t need fixed length bytes in these cases. See wiki for more information.
Definition of prefix complexity
Praticamente per encodare un numero encodiamo la sua lunghezza binaria con un codice e poi concateniamo il numero stesso.
Quindi il codice finale avrebbe lunghezza di
$$ 2\log \log(\lvert s \rvert ) + \lvert s \rvert $$Relazione con complessità normale
$$ C(s) + O(1) \leq K(s) < C(s) + 2\log(C(s)) + O(1) $$La prima diseguaglianza sembra essere presa da Kolmogorov complexity#Teorema dell’invarianza, mentre la seconda dallo stesso teorema più dal fatto che stiamo usando una macchina di Turing con prefissi.
Algorithmic probability
Definizione algorithmic probability
$$ \mathbb{P}(x) = \sum_{p:U(p)=x} 2^{-l(p)} $$TODO: sarebbe carino provare ad esplorare di più questo topic, perché mi sembra abbia belle connessioni con resto. Poi un sacco di questo content è bloggabile.