Lezione 28

Disuguaglianza di Kraft applicata alle lunghezze dei programmi di un calcolatore universale. Relazione fra complessità di Kolmogorov ed entropia (per stringhe i.i.d.). Complessità dei numeri naturali. Prelavenza dei numeri (e delle stringhe) algoritmicamente complesse. Definizioni di stringa algoritmicamente complessa. Definizione di incomprimibilità.