Reducció de Turing

En teoria de la computabilitat, una reducció de Turing a partir d'un problema de decisió $A$ a un problema de decisió $B$ és una màquina oracle que decideix el problema $A$ donat un oracle per $B$ (Rogers 1967, Soare 1987). Es pot entendre com un algorisme que es podria utilitzar per resoldre $A$ si tingués a la seva disposició una subrutina per resoldre $B$. El concepte es pot aplicar de manera anàloga a problemes de funció.

Si una reducció de Turing de $A$ a $B$ existeix, llavors cada algorisme per $B$ es pot utilitzar per produir un algorisme per a $A$, inserint l'algorisme per $B$ a cada lloc on la màquina oracle informàtica $A$ consulta l'oracle per $B$. Tanmateix, com que la màquina oracle pot consultar l'oracle un gran nombre de vegades, l'algoritme resultant pot requerir més temps de manera asimptòtica que l'algorisme per a $B$ o la màquina informàtica oracle $A$. Una reducció de Turing en què la màquina oracle funciona en temps polinomial es coneix com a reducció de Cook.

La primera definició formal de computabilitat relativa, aleshores anomenada reductibilitat relativa, va ser donada per Alan Turing el 1939 en termes de màquines oracle. Més tard, el 1943 i el 1952, Stephen Kleene va definir un concepte equivalent en termes de funcions recursives. L'any 1944 Emil Post va utilitzar el terme "reductibilitat de Turing" per referir-se al concepte.

Definició

Donats dos conjunts $A,B\subseteq \mathbb {N}$ dels nombres naturals, diem $A$ és Turing reductible a $B$ i escriure

$A\leq _{T}B$

si i només si hi ha una màquina oracle que calcula la funció característica d' A quan s'executa amb l'oracle B. En aquest cas, també diem que A és B- recursiu i B-computable.

Si hi ha una màquina oracle que, quan s'executa amb l'oracle B, calcula una funció parcial amb el domini A, llavors es diu que A és B-enumerable recursivament i B-enumerable computablement.

Donat un conjunt ${\mathcal {X}}\subseteq {\mathcal {P}}(\mathbb {N} )$, un conjunt $A\subseteq \mathbb {N}$ es diu Turing dur per ${\mathcal {X}}$ si $X\leq _{T}A$ per a tots $X\in {\mathcal {X}}$. Si a més $A\in {\mathcal {X}}$ aleshores $A$ s'anomena Turing complet per ${\mathcal {X}}$.

Relació de la integritat de Turing amb la universalitat computacional

La completitud de Turing, com acabem de definir anteriorment, correspon només parcialment a la completitud de Turing en el sentit d'universalitat computacional. Concretament, una màquina de Turing és una màquina de Turing universal si el seu problema d'aturada (és a dir, el conjunt d'entrades per a les quals finalment s'atura) és completa per al conjunt. ${\mathcal {X}}$ de conjunts enumerables recursivament. Per tant, una condició necessària però insuficient perquè una màquina sigui computacionalment universal, és que el problema d'aturada de la màquina sigui complet de Turing per a ${\mathcal {X}}$. Insuficient perquè encara pot ser que el llenguatge acceptat per la màquina no sigui enumerable recursivament.

Exemple

SI $W_{e}$ denoten el conjunt de valors d'entrada per als quals s'atura la màquina de Turing amb l'índex e. Després els conjunts $A=\{e\mid e\in W_{e}\}$ i $B=\{(e,n)\mid n\in W_{e}\}$ són equivalents a Turing (aquí $(-,-)$ denota una funció d'aparellament eficaç). Es mostra una reducció $A\leq _{T}B$ es pot construir utilitzant el fet que $e\in A\Leftrightarrow (e,e)\in B$. Donat un parell $(e,n)$, un nou índex $i(e,n)$ es pot construir utilitzant el teorema s_mn de manera que el programa codificat per $i(e,n)$ ignora la seva entrada i només simula el càlcul de la màquina amb l'índex e a l'entrada n. En particular, la màquina amb índex $i(e,n)$ o s'atura en cada entrada o s'atura en cap entrada. Així $i(e,n)\in A\Leftrightarrow (e,n)\in B$ val per a totes les e i n. Com que la funció i és computable, això es mostra $B\leq _{T}A$. Les reduccions que es presenten aquí no són només reduccions de Turing, sinó moltes reduccions, que es comenten a continuació.

Propietats

• Cada conjunt és Turing equivalent al seu complement.
• Cada conjunt computable és Turing reductible a qualsevol altre conjunt. Com que qualsevol conjunt computable es pot calcular sense oracle, pot ser calculat per una màquina oracle que ignora l'oracle donat.
• La relació $\leq _{T}$ és transitiu: si $A\leq _{T}B$ i $B\leq _{T}C$ aleshores $A\leq _{T}C$. A més, $A\leq _{T}A$ s'aplica per a cada conjunt A, i per tant la relació $\leq _{T}$ és una comanda prèvia (no és una comanda parcial perquè $A\leq _{T}B$ i $B\leq _{T}A$ no implica necessàriament $A=B$ ).
• Hi ha parells de conjunts $(A,B)$ tal que A no és Turing reductible a B i B no és Turing reductible a A. Així $\leq _{T}$ no és una comanda total.
• Hi ha infinites seqüències decreixents de conjunts sota $\leq _{T}$. Per tant, aquesta relació no està ben fundada.
• Cada conjunt és reduïble de Turing al seu propi salt de Turing, però el salt de Turing d'un conjunt mai és reduïble de Turing al conjunt original.

L'ús d'una reducció

Ja que cada reducció d'un conjunt $A$ a un conjunt $B$ ha de determinar si hi ha un sol element $A$ en només un nombre finit de passos, només pot fer moltes consultes de pertinença al conjunt $B$. Quan la quantitat d'informació sobre el conjunt $B$ utilitzat per calcular un sol bit de $A$ es comenta, això es concreta amb la funció d'ús. Formalment, l' ús d'una reducció és la funció que envia cada nombre natural $n$ al nombre natural més gran $m$ la pertinença del qual al conjunt $B$ va ser consultat per la reducció mentre es determinava la pertinença de $n$ en $A$.