Decision problems for groups with application of some extensions to cryptography

In this thesis, I’m interested in computability theory and its relation to decision problems in group theory. Mathematically, computability theory originates from the concept of an algorithm, it is a recent branch of Mathematics and Theoretical Computer Science; it started in 1936, the date in which Alonzo Church, Alan Turing and Emil Post each published fundamental work on formalizing the notions of mechanical procedure, algorithms, computable functions and computable partial functions. This formalization leads to the discovery of uncomputability in logic, computer science and mathematics. In mathematics the existence of uncomputable sets implies that many interesting problems have no algorithmic solutions, especially combinatorial problems in groups, even when these groups are given by a finite presentation.

In questa tesi, ho focalizzato la mia attenzione sulla teoria della computazione e le sue relazioni coi problemi decisionali nella teoria dei gruppi. In Matematica, la teoria della computabilità nasce dal concetto di algoritmo, e si la si può considerare come una branca recente della Matematica e l’informatica teorica; il suo inizio può essere fatto risalire al 1936, data in cui Alonzo Church, Alan Turing e Emil Post pubblicarono lavori fondamentali sulla formalizzazione delle nozioni di procedura meccanica, algoritmi, funzioni computabili e funzioni parzialmente computabili. Questo formalismo condusse alla scoperta dell’incalcolabilità in logica, informatica e matematica. In matematica, l’esistenza di insiemi incalcolabili implica che diversi problemi interessanti non posseggono soluzioni algoritmiche, soprattutto problemi combinatori in gruppi, Anche quando tali gruppi hanno delle presentazioni finite.