Visualizza wikitesto di Predicato T di Kleene

In [[Teoria della calcolabilità|teoria della computabilità]], il '''predicato T''', studiato per la prima volta dal matematico [[Stephen Kleene|Stephen Cole Kleene]], è una particolare [[relazione ternaria]] sui [[Numero naturale|numeri naturali]], che viene utilizzata per rappresentare [[Funzione calcolabile|funzioni calcolabili]] all'interno delle [[Teoria formale|teorie formali]] dell'[[aritmetica]]. Intuitivamente, il predicato ''T'' dice se un particolare [[Programma (informatica)|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 m n|teorema s<sub>mn</sub>]], la notazione originale usata da Kleene è diventata una terminologia standard per il concetto.<ref>Il predicato qui descritto è stato presentato in (Kleene 1943) e (Kleene 1952), ed è ciò che di solito viene chiamato "predicato ''T'' di Kleene". (Kleene 1967) utilizza la lettera ''T'' per descrivere un predicato diverso relativo a funzioni calcolabili, ma che non può essere utilizzato per ottenere il teorema della forma normale di Kleene.</ref>

== Definizione ==
[[File:KleeneT_collatz5.gif|thumb|upright=4.1| Esempio di chiamata di ''T''<sub>1</sub>. Il primo argomento fornisce il codice sorgente (in [[C (linguaggio)|C]] anziché come [[numero di Gödel]] ''e'') di una funzione calcolabile, la [[Congettura di Collatz|funzione di Collatz]] ''f''. Il secondo argomento fornisce il numero naturale ''i'' a cui deve essere applicata ''f''. Il terzo argomento fornisce una sequenza ''x'' di passi di computazione che simulano la valutazione di ''f'' su ''i'' (come una catena di equazioni piuttosto che un numero di sequenza di Gödel). La chiamata al predicato restituisce ''true'' poiché ''x'' è in realtà la sequenza di calcolo corretta per la chiamata ''f''(5) e termina con un'espressione che non coinvolge più ''f''. La funzione ''U'', applicata alla sequenza ''x'', restituirà la sua espressione finale, ovvero 1.]]
La definizione dipende da un'opportuna [[Numero di Gödel|numerazione di Gödel]] che assegni numeri naturali a [[Funzione calcolabile|funzioni calcolabili]] (date come [[Macchina di Turing|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 <math>T</math> si ottiene formalizzando questa simulazione.

La relazione ternaria <math>T_1(e,i,x)</math> prende tre numeri naturali come argomenti. <math>T_1(e,i,x)</math> è vero se <math>x</math> codifica una sequenza di passi di computazione della funzione calcolabile con indice <math>e</math> eseguita sull'input <math>i</math>, e il programma si interrompe all'ultimo passo di questa sequenza. Ovvero:

* <math>T_1</math> prima chiede se <math>x</math> è il [[Numero di Gödel per sequenze|numero di Gödel]] di una sequenza finita <math>\langle x_{j} \rangle</math> di configurazioni complete della macchina di Turing con indice <math>e</math>, che esegue un calcolo sull'input <math>i</math>.
* Se ciò è vero, <math>T_1</math> 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, <math>T_1</math> chiede infine se la sequenza <math>\langle x_{j} \rangle</math> si conclude con la macchina in stato di terminazione.

Se tutte e tre le domande hanno una risposta affermativa, allora <math>T_1(e,i,x)</math> è vero, altrimenti è falso.

Il predicato <math>T_1</math> è [[Funzione ricorsiva primitiva|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 <math>U</math> tale che, se <math>T_1(e,i,x)</math> è vero, allora <math>U(x)</math> restituisce l'output della funzione con indice <math>e</math> calcolata sull'input <math>i</math>.

Poiché il formalismo di Kleene assegna un numero di input a ciascuna funzione, il predicato <math>T_1</math> può essere utilizzato solo per funzioni unarie. Esistono predicati aggiuntivi per funzioni con più input; la relazione

: <math>T_k(e, i_1, \dots, i_k, x)</math>

è vera se <math>x</math> codifica una computazione terminante della funzione con indice <math>e</math> sugli ingressi <math>i_1, \dots, i_k</math>.

Come <math>T_1</math>, tutti i predicati <math>T_k</math> sono primitivi ricorsivi. Per questo motivo, qualsiasi teoria dell'aritmetica che sia in grado di rappresentare ogni funzione ricorsiva primitiva è in grado di rappresentare <math>T</math> e <math>U</math>. Esempi di tali teorie aritmetiche includono l'[[aritmetica di Robinson]] e teorie più forti come l'[[Assiomi di Peano|aritmetica di Peano]].

== Teorema della forma normale ==
I predicati <math>T_k</math> possono essere usati per ottenere il '''teorema della forma normale di Kleene''' per funzioni calcolabili (Soare 1987, p.&nbsp;15; Kleene 1943, pp.&nbsp;52&#x2014;53). Ciò afferma che esiste una [[funzione ricorsiva primitiva]] fissa <math>U</math> tale per cui una funzione <math>f:\mathbb{N}^{k}\rightarrow\mathbb{N}</math> è calcolabile se e solo se esiste un numero <math>e</math> tale che per ogni <math>n_1,\ldots,n_k</math> si ha

: <math>f(n_1,\ldots,n_k) \simeq U( \mu x\, T_k(e,n_1,\ldots,n_k,x))</math>

dove ''&#x3BC;'' è l'[[Minimalizzazione|operatore di minimizzazione]] (<math>\mu x\, \phi(x)</math> è il più piccolo numero naturale per il quale <math>\phi(x)</math> è vero) e <math>\simeq</math> è vero se entrambi i membri sono indefiniti o se sono entrambi uguali. Per il teorema, la definizione di ogni [[Funzione ricorsiva|funzione ricorsiva generale]] <math>f</math> può essere riscritta in una forma normale tale che l'operatore ''&#x3BC;'' sia usato una sola volta, come argomento dell'occorrenza più esterna di <math>U</math>, che è indipendente dalla funzione calcolabile <math>f</math>.

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

: <math> K = \{e \mid \exists x T_1(e,0,x) \}</math>

che è dello stesso [[grado di Turing]] del [[Problema della terminazione|problema dell'arresto]], è una relazione unaria <math>\Sigma^0_1</math>-completa (Soare 1987, pp.&nbsp;28, 41). Più in generale, il set

: <math>K_{n+1} = \{ \langle e, a_1, \ldots, a_n\rangle \mid \exists x T_n(e, a_1, \ldots, a_n, x)\}</math>

è un predicato (''n''+1)-ario <math>\Sigma^0_1</math>-completo. Così, una volta ottenuta una rappresentazione del predicato ''T''<sub>''n''</sub> in una teoria dell'aritmetica, una rappresentazione di un predicato <math>\Sigma^0_1</math>-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.&nbsp;397). Ad esempio, se un insieme <math>A \subseteq \mathbb{N}^{k+1}</math> è <math>\Sigma^0_{n}</math>-completo, allora l'insieme

: <math>\{ \langle a_1, \ldots, a_k\rangle \mid \forall x ( \langle a_1, \ldots, a_k, x) \in A)\}</math>

è <math>\Pi^0_{n+1}</math>-completo.

== Note ==
<references />

== Bibliografia ==

* Peter Hinman, 2005, ''Fundamentals of Mathematical Logic'', A K Peters. {{ISBN|978-1-56881-262-5}} 
* {{Cita pubblicazione|doi=10.1090/S0002-9947-1943-0007371-8 | url=https://www.ams.org/journals/tran/1943-053-01/S0002-9947-1943-0007371-8/S0002-9947-1943-0007371-8.pdf |autore=Stephen Cole Kleene |titolo=Recursive predicates and quantifiers |rivista=Transactions of the American Mathematical Society | volume=53 | numero=1 |pp=41-73 |data=Jan 1943 }} Ristampato in ''The Undecidable'', Martin Davis, ed., 1965, pp.&nbsp;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|matematica|informatica}}

[[Categoria:Teoria della calcolabilità]]
[[Categoria:Teoria della computazione]]
[[Categoria:Teoria della complessità computazionale]]
[[Categoria:Logica]]
[[Categoria:Logica matematica]]
[[Categoria:Logica nell'informatica]]
[[Categoria:Matematica]]
[[Categoria:Matematica applicata]]
[[Categoria:Matematica discreta]]