Elementi di Calcolabilità e Complessità

Come avevo già annunciato in un precedente articolo, questa serie di articoli riguardante la teoria della calcolabilità e della complessità, rappresenta il mio tentativo di superare l’esame dell’Università di Pisa, per aiutarmi ad affrontare il blocco psicologico che ho nei confronti dello studio di questa materia.

Per proteggere il briciolo di onestà intellettuale che resta in serbatoio, vorrei subito precisare che questi articoli seguiranno la struttura del corso di Elementi di Calcolabilità e Complessità, così come insegnato al corso “triennale” di informatica dell’Università di Pisa. Chiedo subito venia se copierò una parte sostanziale delle dispense fornite dal professore: molte definizioni e enunciati di teoremi lo saranno sen’altro, ma saranno almeno annotate con le mie osservazioni e in parte riscritte, in modo da renderle più digeribili al mio cervello che già fatica a capire le cose ovvie, banali, naturali e facili, tantomeno composizioni complicate di asserzioni banali. Spero che questo non causi problemi a nessuno (in realtà basta che non li crei a me, perché a diffondere il contenuto di questi articoli non ritengo sia possibile danneggiare nessuno, anzi).

Purtroppo il tempo che sono riuscito a strappare alla mia routine giornaliera composta da varie e infinite distrazioni, non mi è stato sufficiente a digerire e memorizzare bene alcuni concetti di base che mi sono costati il non superamento dell’esame che ho tentato lo scorso 9 Febbraio. D’altra parte so bene che un esame non si prepara in un mese… quindi eccomi di nuovo alle prese con questi articoli.

Per non sovraccaricare troppo la pagina principale del blog con decine di articoli sulla calcolabilità, ho creato questo elenco migliorandone ampiamente l’organizzazione.