Teoria degli algoritmi

La Teoria degli algoritmi è una branca della logica che applica i processi di deduzione e induzione tipici della logica formale alla computabilità e risolubilità in passi finiti di un algoritmo e, in generale, permette di analizzare le strutture logiche delle relazioni presenti negli algoritmi stessi. Dopo un’introduzione generale al concetto di computabilità, si analizzano le caratteristiche delle funzioni ricorsive, attraverso le loro proprietà generali e l’analisi della tesi di Church. Vengono poi analizzati, attraverso esempi significativi, gli algoritmi di Markov e la loro computabilità. Si passa poi ad una discussione dettagliata della macchina di Turing, della quale viene fornita la definizione, il concetto di “calcolo”, la computabilità degli algoritmi secondo tale macchina e vengono forniti degli esempi esplicativi. Vengono infine presi in analisi i semisistemi di Thue e le loro relazioni con le macchine di Turing.