Non determinismo e terminazione in programmazione: aspetti fondazionali

Il presente lavoro si concentra su un capitolo particolarmente importante della ricerca sulla semantica dei linguaggi di programmazione: la questione dell’interpretazione di programmi che possono generare infiniti risultati, in modo non deterministico. Nel primo capitolo, si vedrà che tale questione affonda le radici in problemi di implementabilità di programmi, specie nel problema detto del ”non determinismo unbounded”. Questo argomento è stato affrontato da E.W. Dijkstra in modo emblematico negli anni ’70 del secolo scorso. Il secondo capitolo presenterà un’alternativa alla semantica offerta da Dijkstra: la semantica denotazionale. Ciò verrà motivato dal fatto che la semantica presentata nel primo capitolo pone problemi nello stabilire quale sia il criterio da rispettarsi affinché una funzione possa essere considerata calcolabile. In questo capitolo, alla luce della teoria dei domini, verrà studiata più da vicino la proprietà di continuità, in alcune delle sue manifestazioni. Questa proprietà è spesso ritenuta necessaria per una caratterizzazione astratta della calcolabilità. Infine, nel terzo capitolo verrà presentato il problema dei supertask, programmi che restituirebbero un insieme infinito di risultati in un tempo finito: tale argomento rimanda ad altri campi, come la calcolabilità classica e persino la filosofia.