Predicato T di Kleene

In teoria della computabilità, il predicato T, studiato per la prima volta dal matematico Stephen Cole Kleene, è una particolare relazione ternaria sui numeri naturali, che viene utilizzata per rappresentare funzioni calcolabili all'interno delle teorie formali dell'aritmetica. Intuitivamente, il predicato T dice se un particolare programma per computer si fermerà se eseguito su un particolare input, e la corrispondente funzione U viene utilizzata per ottenere i risultati della computazione se il programma si ferma. Come per il teorema s_mn, la notazione originale usata da Kleene è diventata una terminologia standard per il concetto.^[1]

La definizione dipende da un'opportuna numerazione di Gödel che assegni numeri naturali a funzioni calcolabili (date come macchine di Turing). Questa numerazione deve essere tale per cui, dato un indice di una funzione calcolabile e un input per la funzione, sia possibile simulare effettivamente il calcolo della funzione su quell'input. Il predicato ${\displaystyle T}$ si ottiene formalizzando questa simulazione.

La relazione ternaria ${\displaystyle T_{1}(e,i,x)}$ prende tre numeri naturali come argomenti. ${\displaystyle T_{1}(e,i,x)}$ è vero se ${\displaystyle x}$ codifica una sequenza di passi di computazione della funzione calcolabile con indice ${\displaystyle e}$ eseguita sull'input ${\displaystyle i}$, e il programma si interrompe all'ultimo passo di questa sequenza. Ovvero:

• ${\displaystyle T_{1}}$ prima chiede se ${\displaystyle x}$ è il numero di Gödel di una sequenza finita ${\displaystyle \langle x_{j}\rangle }$ di configurazioni complete della macchina di Turing con indice ${\displaystyle e}$, che esegue un calcolo sull'input ${\displaystyle i}$.
• Se ciò è vero, ${\displaystyle T_{1}}$ chiede poi se questa sequenza inizia con la configurazione iniziale e se ogni successivo elemento della sequenza corrisponde a un singolo passo della macchina di Turing.
• Se ciò è vero, ${\displaystyle T_{1}}$ chiede infine se la sequenza ${\displaystyle \langle x_{j}\rangle }$ si conclude con la macchina in stato di terminazione.

Se tutte e tre le domande hanno una risposta affermativa, allora ${\displaystyle T_{1}(e,i,x)}$ è vero, altrimenti è falso.

Il predicato ${\displaystyle T_{1}}$ è ricorsivo primitivo nel senso che esiste una funzione ricorsiva primitiva che, dati gli input per il predicato, determina correttamente il valore di verità del predicato su quegli input.

Esiste una corrispondente funzione ricorsiva primitiva ${\displaystyle U}$ tale che, se ${\displaystyle T_{1}(e,i,x)}$ è vero, allora ${\displaystyle U(x)}$ restituisce l'output della funzione con indice ${\displaystyle e}$ calcolata sull'input ${\displaystyle i}$.

Poiché il formalismo di Kleene assegna un numero di input a ciascuna funzione, il predicato ${\displaystyle T_{1}}$ può essere utilizzato solo per funzioni unarie. Esistono predicati aggiuntivi per funzioni con più input; la relazione

${\displaystyle T_{k}(e,i_{1},\dots ,i_{k},x)}$

è vera se ${\displaystyle x}$ codifica una computazione terminante della funzione con indice ${\displaystyle e}$ sugli ingressi ${\displaystyle i_{1},\dots ,i_{k}}$.

Come ${\displaystyle T_{1}}$, tutti i predicati ${\displaystyle T_{k}}$ sono primitivi ricorsivi. Per questo motivo, qualsiasi teoria dell'aritmetica che sia in grado di rappresentare ogni funzione ricorsiva primitiva è in grado di rappresentare ${\displaystyle T}$ e ${\displaystyle U}$. Esempi di tali teorie aritmetiche includono l'aritmetica di Robinson e teorie più forti come l'aritmetica di Peano.

I predicati ${\displaystyle T_{k}}$ possono essere usati per ottenere il teorema della forma normale di Kleene per funzioni calcolabili (Soare 1987, p. 15; Kleene 1943, pp. 52—53). Ciò afferma che esiste una funzione ricorsiva primitiva fissa ${\displaystyle U}$ tale per cui una funzione ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$ è calcolabile se e solo se esiste un numero ${\displaystyle e}$ tale che per ogni ${\displaystyle n_{1},\ldots ,n_{k}}$ si ha

${\displaystyle f(n_{1},\ldots ,n_{k})\simeq U(\mu x\,T_{k}(e,n_{1},\ldots ,n_{k},x))}$

dove μ è l'operatore di minimizzazione (${\displaystyle \mu x\,\phi (x)}$ è il più piccolo numero naturale per il quale ${\displaystyle \phi (x)}$ è vero) e ${\displaystyle \simeq }$ è vero se entrambi i membri sono indefiniti o se sono entrambi uguali. Per il teorema, la definizione di ogni funzione ricorsiva generale ${\displaystyle f}$ può essere riscritta in una forma normale tale che l'operatore μ sia usato una sola volta, come argomento dell'occorrenza più esterna di ${\displaystyle U}$, che è indipendente dalla funzione calcolabile ${\displaystyle f}$.

Oltre a codificare la computabilità, il predicato T può essere utilizzato per generare insiemi Turing-completi nella gerarchia aritmetica. In particolare, l'insieme

${\displaystyle K=\{e\mid \exists xT_{1}(e,0,x)\}}$

che è dello stesso grado di Turing del problema dell'arresto, è una relazione unaria ${\displaystyle \Sigma _{1}^{0}}$-completa (Soare 1987, pp. 28, 41). Più in generale, il set

${\displaystyle K_{n+1}=\{\langle e,a_{1},\ldots ,a_{n}\rangle \mid \exists xT_{n}(e,a_{1},\ldots ,a_{n},x)\}}$

è un predicato (n+1)-ario ${\displaystyle \Sigma _{1}^{0}}$-completo. Così, una volta ottenuta una rappresentazione del predicato T_n in una teoria dell'aritmetica, una rappresentazione di un predicato ${\displaystyle \Sigma _{1}^{0}}$-completo può essere ottenuta da essa.

Questa costruzione può essere estesa più in alto nella gerarchia aritmetica, come nel teorema di Post (confronta Hinman 2005, p. 397). Ad esempio, se un insieme ${\displaystyle A\subseteq \mathbb {N} ^{k+1}}$ è ${\displaystyle \Sigma _{n}^{0}}$-completo, allora l'insieme

${\displaystyle \{\langle a_{1},\ldots ,a_{k}\rangle \mid \forall x(\langle a_{1},\ldots ,a_{k},x)\in A)\}}$

è ${\displaystyle \Pi _{n+1}^{0}}$-completo.

• Peter Hinman, 2005, Fundamentals of Mathematical Logic, A K Peters. ISBN 978-1-56881-262-5
• Stephen Cole Kleene, Recursive predicates and quantifiers (PDF), in Transactions of the American Mathematical Society, vol. 53, n. 1, Jan 1943, pp. 41–73, DOI:10.1090/S0002-9947-1943-0007371-8. Ristampato in The Undecidable, Martin Davis, ed., 1965, pp. 255–287.
• —, 1952, Introduction to Metamathematics, North-Holland. Ristampato da Ishi press, 2009, ISBN 0-923891-57-9.
• —, 1967. Mathematical Logic, John Wiley. Ristampato da Dover, 2001, ISBN 0-486-42533-9.
• Robert I. Soare, 1987, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer. ISBN 0-387-15299-7

Portale Informatica

Portale Matematica