Macchine di Turing reversibili non deterministiche

The article presents an in-depth study of non-deterministic, deterministic, probabilistic and quantum Turing machines, using the formalisation proposed by Axelsen and Glock as a basis. The primary focus is on the formalisation of non-deterministic reversible Turing machines, which led to the reformulation of Axelsen and Glock's definition in relational terms, then extending the analysis to probabilistic and quantum Turing machines. Throughout the paper, all transition functions are systematically divided into move rules and symbol rules, to improve clarity and comparability between different machine models. Deterministic, non-deterministic, probabilistic and quantum Turing machines are considered in the analysis and a formal definition is provided for each type, functional modifications are proposed for the purposes of the investigation and current uses and examples are analysed.

L'articolo presenta uno studio approfondito delle macchine di Turing non deterministiche, deterministiche, probabilistiche e quantistiche, utilizzando come base la formalizzazione proposta da Axelsen e Glock. L'attenzione principale è rivolta alla formalizzazione delle macchine di Turing reversibili non deterministiche, che ha portato alla riformulazione della definizione di Axelsen e Glock in termini relazionali, estendendo poi l'analisi alle macchine di Turing probabilistiche e quantistiche. Nell'intero documento, tutte le funzioni di transizione sono sistematicamente suddivise in regole di movimento e regole di simbolo, per migliorare la chiarezza e il confronto tra i diversi modelli di macchina. L'analisi prende in considerazione macchine di Turing deterministiche, non deterministiche, probabilistiche e quantistiche e per ogni tipo viene fornita una definizione formale, vengono proposte modifiche funzionali ai fini dell'indagine e vengono analizzati usi ed esempi attuali.