Turing riduzione

In teoria della computabilità, una Turing-riduzione da un problema decisionale ${\displaystyle A}$ ad un problema decisionale ${\displaystyle B}$ è una macchina oracolo che decide il problema ${\displaystyle A}$ dato un oracolo per ${\displaystyle B}$ (Rogers 1967, Soare 1987). Può essere inteso come un algoritmo che potrebbe essere utilizzato per risolvere ${\displaystyle A}$ se avesse a sua disposizione una subroutine per la risoluzione di ${\displaystyle B}$. Il concetto può essere applicato in modo analogo ai problemi di funzione.

Se esiste una Turing-riduzione da ${\displaystyle A}$ a ${\displaystyle B}$, allora ogni algoritmo per ${\displaystyle B}$^[1] può essere utilizzato per produrre un algoritmo per ${\displaystyle A}$, inserendo l'algoritmo per ${\displaystyle B}$ in ogni punto in cui la macchina oracolo che computa ${\displaystyle A}$ interroga l'oracolo per ${\displaystyle B}$. Tuttavia, poiché la macchina oracolo può interrogare l'oracolo un numero elevato di volte, l'algoritmo risultante potrebbe asintoticamente richiedere più tempo rispetto all'algoritmo per ${\displaystyle B}$ o alla macchina oracolo che computa ${\displaystyle A}$. Una Turing-riduzione in cui la macchina oracolo computa in un tempo polinomiale è nota come riduzione di Cook.

La prima definizione formale di computabilità relativa, poi chiamata riducibilità relativa, fu data da Alan Turing nel 1939 in termini di macchine oracoli. Successivamente, nel 1943 e nel 1952 Stephen Kleene definì un concetto equivalente in termini di funzioni ricorsive. Nel 1944 Emil Post usò il termine "riducibilità di Turing" per riferirsi al concetto.

Dati due insiemi ${\displaystyle A,B\subseteq \mathbb {N} }$ di numeri naturali, diciamo che ${\displaystyle A}$ è Turing-riducibile a ${\displaystyle B}$ e scriviamo

${\displaystyle A\leq _{T}B}$

se e solo se esiste una macchina oracolo che calcola la funzione caratteristica di ${\displaystyle A}$ usando un oracolo per ${\displaystyle B}$. In questo caso, diciamo anche che ${\displaystyle A}$ è B-ricorsivo, o B-computabile.

Se esiste una macchina oracolo che, usando un oracolo per ${\displaystyle B}$, calcola una funzione parziale che ha per dominio ${\displaystyle A}$, allora ${\displaystyle A}$ è detto B-ricorsivamente enumerabile, o B-computabilmente enumerabile.

Diciamo che ${\displaystyle A}$ è Turing-equivalente a ${\displaystyle B}$ e scriviamo ${\displaystyle A\equiv _{T}B}$ se valgono ${\displaystyle A\leq _{T}B}$ e ${\displaystyle B\leq _{T}A}$. Le classi di equivalenza degli insiemi Turing-equivalenti sono chiamate gradi di Turing. Il grado di Turing di un insieme ${\displaystyle X}$ è indicato con ${\displaystyle {\textbf {deg}}(X)}$.

Dato un insieme ${\displaystyle {\mathcal {X}}\subseteq 2^{\mathbb {N} }}$, un insieme ${\displaystyle A\subseteq \mathbb {N} }$ è detto Turing-difficile per ${\displaystyle {\mathcal {X}}}$ se ${\displaystyle X\leq _{T}A}$ per ogni ${\displaystyle X\in {\mathcal {X}}}$. Se inoltre ${\displaystyle A\in {\mathcal {X}}}$, allora ${\displaystyle A}$ è detto Turing-completo per ${\displaystyle {\mathcal {X}}}$.

La Turing-completezza, per come è definita sopra, corrisponde solo parzialmente alla Turing-equivalenza nel senso di universalità computazionale. Nello specifico, una macchina di Turing è una macchina di Turing universale se il suo problema della fermata (cioè l'insieme di input sui quali si ferma) è molti a uno-completo. Pertanto, una condizione necessaria ma non sufficiente affinché una macchina sia computazionalmente universale, è che il suo problema della fermata sia Turing-completo per la classe ${\displaystyle {\mathcal {X}}}$ degli insiemi ricorsivamente enumerabili. Insufficiente perché può accadere che il linguaggio accettato dalla macchina non sia di per sé ricorsivamente enumerabile.

Denotiamo con ${\displaystyle W_{e}}$ l'insieme dei valori di input per i quali la macchina di Turing con indice e si ferma. Allora, gli insiemi ${\displaystyle A=\{e\mid e\in W_{e}\}}$ e ${\displaystyle B=\{(e,n)\mid n\in W_{e}\}}$ sono Turing-equivalenti (qui ${\displaystyle (\_,\_)}$ denota una funzione di accoppiamento calcolabile). Una riduzione che prova ${\displaystyle A\leq _{T}B}$ può essere costruita utilizzando il fatto che ${\displaystyle e\in A\Leftrightarrow (e,e)\in B}$. Data una coppia ${\displaystyle (e,n)}$, può essere costruito un nuovo indice ${\displaystyle i(e,n)}$ usando il teorema s_mn, tale per cui il programma codificato da ${\displaystyle i(e,n)}$ ignora il suo input e simula semplicemente il calcolo della macchina con indice e sull'input n. In particolare, la macchina con indice ${\displaystyle i(e,n)}$ o si ferma su ogni input o non si ferma su alcun input. Perciò, ${\displaystyle i(e,n)\in A\Leftrightarrow (e,n)\in B}$ vale per tutti gli e ed n. Poiché la funzione i è calcolabile, questo dimostra ${\displaystyle B\leq _{T}A}$ . Le riduzioni qui presentate non sono solo Turing-riduzioni ma riduzioni molti a uno, discusse di seguito.

• Ogni insieme è Turing-equivalente al suo complemento.
• Ogni insieme calcolabile è Turing-riducibile a ogni altro insieme. Poiché qualsiasi insieme calcolabile può essere calcolato senza oracolo, può essere calcolato da una macchina oracolo che ignora l'oracolo dato.
• La relazione ${\displaystyle \leq _{T}}$ è transitiva: se ${\displaystyle A\leq _{T}B}$ e ${\displaystyle B\leq _{T}C}$, allora ${\displaystyle A\leq _{T}C}$. Inoltre, ${\displaystyle A\leq _{T}A}$ vale per ogni insieme ${\displaystyle A}$, e quindi la relazione ${\displaystyle \leq _{T}}$ è un preordine (non è un ordine parziale, poiché ${\displaystyle A\leq _{T}B}$ e ${\displaystyle B\leq _{T}A}$ non implica ${\displaystyle A=B}$).
• Ci sono coppie di insiemi ${\displaystyle (A,B)}$ tali che ${\displaystyle A}$ non è Turing-riducibile a ${\displaystyle B}$ e ${\displaystyle B}$ non è Turing-riducibile ad ${\displaystyle A}$, quindi ${\displaystyle \leq _{T}}$ non è un ordine totale.
• Ci sono sequenze decrescenti infinite di insiemi sotto ${\displaystyle \leq _{T}}$, quindi questa relazione non è ben fondata.
• Ogni insieme è Turing-riducibile al proprio salto di Turing, ma il salto di Turing di un insieme non è mai Turing-riducibile al medesimo insieme.

Poiché ogni riduzione da un insieme ${\displaystyle B}$ ad un insieme ${\displaystyle A}$ deve determinare se un singolo elemento è presente in ${\displaystyle A}$ in un numero finito di passaggi, può fare solo un numero finito di interrogazioni sull'appartenenza all'insieme ${\displaystyle B}$. Quando si parla della quantità di informazioni sull'insieme ${\displaystyle B}$ utilizzate per calcolare un singolo bit di ${\displaystyle A}$, ciò è resa precisa dalla funzione uso. Formalmente, l'uso di una riduzione è la funzione che assegna ad ogni numero naturale ${\displaystyle n}$ il più grande numero naturale ${\displaystyle m}$ la cui appartenenza all'insieme ${\displaystyle B}$ è stata domandata dalla riduzione per determinare l'appartenenza di ${\displaystyle n}$ ad ${\displaystyle A}$.

Esistono due modi comuni per produrre riduzioni più forti della Turing-riducibilità. Il primo modo è limitare il numero e il tipo di chiamate all'oracolo.

• L'insieme${\displaystyle A}$ è molti a uno-riducibile a ${\displaystyle B}$ se esiste una funzione totale calcolabile ${\displaystyle f}$ tale che ogni elemento ${\displaystyle n\in A}$ se e solo se ${\displaystyle f(n)\in B}$. Tale funzione può essere utilizzata per generare una Turing-riduzione (calcolando ${\displaystyle f(n)}$, interrogando l'oracolo e poi interpretando il risultato).
• Una truth table-reduction o una truth table-reduction debole deve presentare tutte le interrogazioni all'oracolo contemporaneamente. In una truth table-reduction, la riduzione fornisce anche una funzione booleana (una tavola di verità) che, una volta fornite le risposte alle interrogazioni, produrrà la risposta finale della riduzione. In una truth table-reduction debole, la riduzione utilizza le risposte dell'oracolo come base per ulteriori calcoli a seconda delle risposte fornite (ma senza usare l'oracolo). In modo equivalente, una truth table-reduction debole è tale per cui l'uso della riduzione è maggiorato da una funzione calcolabile. Per questo motivo, le truth table-reduction deboli sono talvolta chiamate Turing-riduzioni "limitate".

Il secondo modo per produrre una nozione di riducibilità più forte è limitare le risorse computazionali che il programma che implementa la Turing-riduzione può utilizzare. Questi limiti sulla complessità computazionale della riduzione sono importanti quando si studiano classi subricorsive come P. Un insieme ${\displaystyle A}$ è riducibile in tempo polinomiale a un insieme ${\displaystyle B}$ se c'è una Turing-riduzione da ${\displaystyle A}$ a ${\displaystyle B}$ che termina in tempo polinomiale. Il concetto di riduzione in spazio logaritmico è simile.

Queste riduzioni sono più forti, nel senso che forniscono una distinzione più fine in classi di equivalenza e soddisfano requisiti più restrittivi rispetto alle Turing-riduzioni. Di conseguenza, tali riduzioni sono più difficili da trovare. Potrebbe non esserci modo di costruire una riduzione molti a uno da un insieme ad un altro, anche qualora esista una Turing-riduzione per gli stessi insiemi.

Secondo la tesi di Church-Turing, un Turing-riduzione è la forma più generale di riduzione effettivamente calcolabile. Tuttavia, vengono prese in considerazione anche riduzioni più deboli. L'insieme ${\displaystyle A}$ è detto aritmetico in ${\displaystyle B}$ se ${\displaystyle A}$ è definibile con una formula dell'aritmetica di Peano che ha ${\displaystyle B}$ per parametro. L'insieme ${\displaystyle A}$ è iperaritmetico in ${\displaystyle B}$ se esiste un ordinale ricorsivo ${\displaystyle \alpha }$ tale per cui ${\displaystyle A}$ è calcolabile da ${\displaystyle B^{(\alpha )}}$, il salto di Turing α-iterato di ${\displaystyle B}$. La nozione di costruibilità relativa è un'importante nozione di riducibilità nella teoria degli insiemi.

• M. Davis, ed., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. ISBN 0-486-43228-9.
• S. C. Kleene, 1952. Introduction to Metamathematics. Amsterdam: North-Holland.
• S. C. Kleene and E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability". Annals of Mathematics v. 2 n. 59, 379–407.
• E. L. Post, Recursively enumerable sets of positive integers and their decision problems (PDF), in Bulletin of the American Mathematical Society, vol. 50, n. 5, 1944, pp. 284–316, DOI:10.1090/s0002-9904-1944-08111-1. URL consultato il 17 dicembre 2015.
• A. Turing, 1939. "Systems of logic based on ordinals." Proceedings of the London Mathematics Society, ser. 2 v. 45, pp. 161–228. Ristampato in "The Undecidable", M. Davis ed., 1965.
• H. Rogers, 1967. Theory of recursive functions and effective computability. McGraw-Hill.
• R. Soare, 1987. Recursively enumerable sets and degrees, Springer.
• Martin Davis, What is...Turing Reducibility? (PDF), in Notices of the American Mathematical Society, vol. 53, n. 10, novembre 2006, pp. 1218–1219. URL consultato il 16 gennaio 2008.

• Riduzione in tempo polinomiale

• NIST Dictionary of Algorithms and Data Structures: Turing reduction
• University of Cambridge, Andrew Pitts, Tobias Kohn: Computation Theory
• Prof. Jean Gallier’s Homepage

Portale Informatica

Portale Matematica