Categorie di funzioni ricorsive

L'obiettivo di questa tesi è la rielaborazione del concetto di funzione computabile mediante un'analisi categoriale, con l'intento di astrarre l'idea intuitiva di funzioni calcolabili. In questo lavoro si intende caratterizzare una categoria costruita a partire proprio da tali funzioni. Il concetto di computabilità riveste un ruolo fondamentale in varie discipline, e il suo studio può essere affrontato secondo approcci più matematici, facendo uso delle funzioni ricorsive, o più computazionali, che sviluppano modelli di macchine capaci di eseguire le istruzioni ricevute. Nel primo capitolo vengono presentati i risultati principali su cui si basa la teoria della computabilità, definendo le macchine a registri illimitati (MRI), il loro funzionamento e come mediante esse sia possibile esprimere il concetto di funzione computabile e le sue implicazioni. Nel secondo capitolo viene definita e analizzata la categoria "Rec" delle funzioni ricorsive tra sottoinsiemi di numeri naturali, fornendo una caratterizzazione delle differenti strutture categoriali fondamentali. Vengono presentati i monomorfismi, i prodotti, gli esponenziali deboli e altre costruzioni rilevanti.