Calcolabilità E Complessità Giorno 10 - Teorema di ricorsione di Kleene

Oggi dimostrimao il teorema di ricorsione di Kleene. Questo teorema può essere applicato per la costruzione di quine (ovvero programmi che restituiscono in uscita il codice sorgente del programma stesso senza usare funzioni di I/O), per eliminare la ricorsione (le definizioni ricorsive possono essere convertite in definizioni non ricorsive, poichè la nozione di calcolabilità non richiede la ricorsione, vedi MdT, programmi WHILE) e per dimostrare altri concetti utili per la calcolabilità. Inoltre, esistono collegamenti con la logica mamtematica, la teoria dei sistemi che si auto-riproducono e persino con i virus informatici che si auto-replicano.

Rimosso Sistema Di Commenti

In pratica lo avete sancito voi, o meglio il vostro silenzio. In un anno nessuno ha scritto un commento, proprio 0 spaccato.

Con il vecchio sistema di commenti qualche decina di commenti li avevo anche accumulati, ma con questo nuovo nulla. Spesso commenti non troppo interessanti, tra l’altro. È capitato anche che il sistema si inceppasse e non ho ricevuto per tempo le mail di notifica, rispondendo troppo in ritardo.

Inoltre le interazioni migliori le ho avute via email, visto che qualcuno mi ha contattato direttamente per commentare o chiedere informazioni, oppure per proporre estensioni o modifiche al sito e ciò non è quasi mai successo tramite i commenti. Qualche mentecatto mi ha pure contattato per inserire articoli sponsorizzati in un blog personale… d’altra parte siamo nell’era della monetizzazione e ci sta tutto che alla fine rientrerò pienamente nella classe sociale degli inutili.

Tutte queste ragioni più la lettura di questo articolo che ha rinforzato ancora di più questa idea, mi hanno portato a decidere di rimuovere completamente e senza sostituti il sistema di commenti attuale. Un servizio da mantenere in meno.

Calcolabilità E Complessità Giorno 8 - Macchina di Turing Universale (parte 2)

Ieri sono riuscito ad introdurre la Macchina di Turing Universale, ma non ho finito di caratterizzarla completamente. Sappiamo che esiste per il teorema dell’enunciazione, ma abbiamo bisogno di codificare le MdT in modo da poterle rappresentare su un nastro della MdT universale, insieme alla stringa di input.

Calcolabilità E Complessità Giorno 7 - Macchina di Turing Universale

In questa lezione dimostro alcuni teoremi che ci portano alla costruzione della macchina delle macchine: la Macchina di Turing Universale, capace di simulare qualsiasi altra macchina di Turing.

Si tratta di un concetto molto interessante, anche perché ci avvicina ai computer programmabili a cui siamo abituati ai giorni d’oggi. È affascinante constatare che un’invenzione così importante sia stata realizzata solo dopo lo sforzo e l’inventiva di matematici che ne hanno teorizzato e dimostrato l’esistenza teorica. Soltanto con le successive scoperte e miglioramenti tecnologici è stato possibile concretizzare questo modello astratto nel nostro mondo fisico.

Calcolabilità E Complessità Giorno 6 - Funzioni ricorsive generali

Oggi passiamo ad una nuova classe di funzioni ricorsive: le funzioni ricorsive generali. Come anticipato, attraverso questo schema è possibile definire anche le funzioni parziali.

Ci si può riferire a questa classe anche con il termine funzioni µ-ricorsive, per la presenza dell'operatore di minimizzazione µ che ricerca i minimi numeri naturali di una proprietà data.

Calcolabilità E Complessità Giorno 4 - Funzioni totali e parziali

La scorsa lezione si è interrotta sul problema che nasce dal limitare dominio e codominio dei programmi WHILE ai soli numeri naturali. Per risolvere questo problema abbiamo introdotto il concetto di codifica, realizzato da una funzione invertibile che mette in relazione un dominio qualsiasi con i numeri naturali.

Un esempio di codifica è la codifica a “coda di colomba” o funzione coppia di Cantor, che codifica coppie di numeri naturali come un singolo naturale.