Conjunto de índices (computabilidad)

En la teoría de la computabilidad , los conjuntos de índices describen clases de funciones computables ; específicamente, proporcionan todos los índices de las funciones en una clase determinada, según una numeración de Gödel fija de funciones computables parciales.

Dejar${\displaystyle \varphi _{e}}$sea ​​una enumeración computable de todas las funciones computables parciales, y${\displaystyle W_{e}}$sea ​​una enumeración computable de todos los conjuntos ce .

Dejar${\displaystyle {\mathcal {A}}}$ser una clase de funciones parcialmente computables. Si${\displaystyle A=\{x\,:\,\varphi _{x}\in {\mathcal {A}}\}}$entonces${\displaystyle A}$es el conjunto de índices de${\displaystyle {\mathcal {A}}}$. En general${\displaystyle A}$es un conjunto de índices si para cada${\displaystyle x,y\in \mathbb {N} }$con${\displaystyle \varphi _{x}\simeq \varphi _{y}}$(es decir, indexan la misma función), tenemos${\displaystyle x\in A\leftrightarrow y\in A}$Intuitivamente, estos son los conjuntos de números naturales que describimos únicamente en referencia a las funciones que indexan.

La mayoría de los conjuntos de índices no son computables, salvo dos excepciones triviales. Esto se afirma en el teorema de Rice :

Dejar${\displaystyle {\mathcal {C}}}$sea ​​una clase de funciones parcialmente computables con su conjunto de índices${\displaystyle C}$. Entonces${\displaystyle C}$es computable si y solo si${\displaystyle C}$está vacío, o${\displaystyle C}$es todo de${\displaystyle \mathbb {N} }$.

El teorema de Rice afirma que "cualquier propiedad no trivial de las funciones parcialmente computables es indecidible". ^{[ 1 ]}

Los conjuntos de índices proporcionan muchos ejemplos de conjuntos que son completos en algún nivel de la jerarquía aritmética . Aquí decimos que un conjunto de índices es completo en algún nivel de la jerarquía aritmética.${\displaystyle \Sigma _{n}}$colocar${\displaystyle A}$es${\displaystyle \Sigma _{n}}$-completar si, para cada${\displaystyle \Sigma _{n}}$colocar${\displaystyle B}$, hay una reducción m de${\displaystyle B}$a${\displaystyle A}$.${\displaystyle \Pi _{n}}$La completitud se define de manera similar. Aquí hay algunos ejemplos: ^{[ 2 ]}

• ${\displaystyle \mathrm {Emp} =\{e\,:\,W_{e}=\varnothing \}}$es${\displaystyle \Pi _{1}}$-completo.
• ${\displaystyle \mathrm {Fin} =\{e\,:\,W_{e}{\text{ es finito}}\}}$es${\displaystyle \Sigma _{2}}$-completo.
• ${\displaystyle \mathrm {Inf} =\{e\,:\,W_{e}{\text{ es infinito}}\}}$es${\displaystyle \Pi _{2}}$-completo.
• ${\displaystyle \mathrm {Tot} =\{e\,:\,\varphi _{e}{\text{ es total}}\}=\{e:W_{e}=\mathbb {N} \}}$es${\displaystyle \Pi _{2}}$-completo.
• ${\displaystyle \mathrm {Con} =\{e\,:\,\varphi _{e}{\text{ es total y constante}}\}}$es${\displaystyle \Pi _{2}}$-completo.
• ${\displaystyle \mathrm {Cof} =\{e\,:\,W_{e}{\text{ es cofinito}}\}}$es${\displaystyle \Sigma _{3}}$-completo.
• ${\displaystyle \mathrm {Rec} =\{e\,:\,W_{e}{\text{ es computable}}\}}$es${\displaystyle \Sigma _{3}}$-completo.
• ${\displaystyle \mathrm {Ext} =\{e\,:\,\varphi _{e}{\text{ es extendible a una función computable total}}\}}$es${\displaystyle \Sigma _{3}}$-completo.
• ${\displaystyle \mathrm {Cpl} =\{e\,:\,W_{e}\equiv _{\mathrm {T} }\mathrm {HP} \}}$es${\displaystyle \Sigma _{4}}$-completo, donde${\displaystyle \mathrm {HP} }$es el problema de la parada .

Empíricamente, si la definición "más obvia" de un conjunto${\displaystyle A}$es${\displaystyle \Sigma _{n}}$[resp.${\displaystyle \Pi _{n}}$], normalmente podemos demostrar que${\displaystyle A}$es${\displaystyle \Sigma _{n}}$-completo [resp.${\displaystyle \Pi _{n}}$-completo].

• Odifreddi, PG (1992). Teoría clásica de la recursión, Volumen 1. Elsevier. pág.  668. ISBN 0-444-89483-7.
• Rogers Jr., Hartley (1987). Teoría de las funciones recursivas y la computabilidad efectiva . MIT Press. pág.  482. ISBN 0-262-68052-1.