Lezione 27

Differenza fra le complessità su calcolatori diversi. Stime dall'alto sulla complessità di una stringa.

Lezione 26

Introduzione alla complessità di Kolmogorov. Macchine di Turing. Calcolatore universale. Definizione di complessità di Kolmogorov (o algoritmica) e di complessità di Kolmogorov condizionale.
Un po' di (quasi recente) preistoria informatica: il Commodore VIC-20 (suo spot pubblicitario USA) e il suo acerrimo rivale, il Sinclair ZX81. Il successivo e più famoso Commodore 64: suo manuale d'istruzioni, con il capitolo sul linguaggio macchina.