Informatica Teorica: Calcolabilità

Vincenzo Manca

I corsi dei primi tre anni, specialmente quelli di tipo matematico, algoritmico e programmativo.

La comprensione delle basi matematiche dei modelli di calcolo classici e delle classi di linguaggi formali, fino alle proposte emergenti in letteratura orientate a nuovi paradigmi di calcolo.

Il corso intende: i) Fornire un'analisi matematica dei vari paradigmi di calcolo secondo la trilogia automa-funzione-sistema formale. ii) Approfondire l'analisi delle più importanti classi di linguaggi formal= i e dei relativi sistemi di riscrittura (RE, CS, CF, LIN, REG, OL, MAT, HL, ..= =2E) con le loro varianti più importanti ed i principali risultati di equivalenza, normalizzazione, chiusura e decidibilità. iii) Presentare un quadro unificante dei vari formalismi di manipolazione simbolica e di alcuni recenti modelli di calcolo che sono alla frontiera della ricerca attuale (DNA e Molecular Computing).

This course intends i) to provide a mathematical analysis of different computational paradigms, according to the trilogy automaton-function-formal system; ii) to analyze the main classes of formal languages (RE, CS, CF, LIN, REG, OL, MAT, HL, ...) with their important variants and relevant results of normalization, closure and decidability; iii) to present a unifying framework for formalisms of symbolic manipulation and for some recent computation models that are emerging in the actual research (DNA e Molecular Computing).

Definizioni matematiche dei modelli di calcolo basati su automa, sistema formale e classe induttiva di funzioni.
Universalità e teoremi di equivalenza.
Gerarchia aritmetica.
Sistemi formali per grammatiche e automi: teoremi di equivalenza.
Analisi della Gerarchia di Chomsky: Linguaggi fondamentali, Teoremi dell' inclusione stretta, Teorema di Kleene sulla regolarità, Teorema di Nerode sulla minimalità, Teoremi elementari di chiusura, Teorema di Sawitch, Teorema di Shannon.
Meccanismi di regolazione: classi notevoli definite tramite regolazione.
Automi e trasduttori.
Cenni ai Sistemi di Post, di Lindenmayer, di Marcus, e di Head.
Modelli di stringhe e Teorie monoidali: universalità e rappresentabilità.
Sistemi di derivazione e formalismi tradizionali.
Basi e motivazioni biochimiche del calcolo basato sullo 'splicing'.
Lemmi di regolarità e universalità sullo 'splicing'.
Cenni sugli sviluppi e sulle applicazioni dei sistemi di manipolazione simbolica.