Gli algoritmi di Markov e il problema della parola

Alla base dell’informatica si trovano alcune domande fondamentali riguardanti la natura del concetto di algoritmo e i limiti di ciò che può essere calcolato. Le nozioni di algoritmo e di funzione effettivamente calcolabile sono state a lungo definite solo in maniera intuitiva. La presente tesi introduce due diversi formalismi nel tentativo di fornire una definizione rigorosa: gli algoritmi di Markov e le macchine di Turing. L’idea intuitiva di calcolabilità effettiva si identifica prima con la nozione di “Markov-calcolabilità”, successivamente con quella di “Turing-calcolabilità”. I due approcci risultano equivalenti: si dimostra infatti che la classe delle funzioni Markov-calcolabili coincide con quella delle funzioni Turing-calcolabili. Tale risultato supporta la validità della tesi di Church-Turing, che permette di indagare i limiti degli algoritmi sfruttando le macchine di Turing. Nella seconda parte della tesi queste vengono utilizzate per formalizzare il problema della parola per semigruppi e gruppi e dimostrarne l’indecidibilità. Nel caso dei semigruppi si dimostra il teorema di Markov-Post, che stabilisce l’esistenza di un semigruppo finitamente presentato con problema della parola indecidibile. Infine, utilizzando la teoria delle estensioni HNN e il lemma di Britton, si dimostra il teorema di Novikov-Boone-Britton, che assicura l’esistenza di un gruppo finitamente presentato con problema della parola indecidibile. La validità di tale risultato si fonda sul lemma di Boone, la cui dimostrazione richiede diversi lemmi ausiliari e sarà presentata nei paragrafi finali della tesi.