Conjunto de índices (computabilidad)

En la teoría de computabilidad , los conjuntos de índices describen clases de funciones computables ; específicamente, dan todos los índices de funciones en una cierta clase, de acuerdo con una numeración de Gödel fija de funciones computables parciales.

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

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

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

Sea una clase de funciones computables parciales con su conjunto de índices . Entonces es computable si y solo si está vacío, o es todo .${\displaystyle {\mathcal {C}}}$${\estilo de visualización C}$${\estilo de visualización C}$${\estilo de visualización C}$${\estilo de visualización C}$${\displaystyle \mathbb {N}}$

El teorema de Rice dice que "cualquier propiedad no trivial de funciones computables parciales es indecidible". ^[1]

Los conjuntos de índices proporcionan muchos ejemplos de conjuntos que están completos en algún nivel de la jerarquía aritmética . Aquí, decimos que un conjunto es -completo si, para cada conjunto , hay una m-reducción de a . La -completitud se define de manera similar. A continuación se ofrecen algunos ejemplos: ^[2]${\displaystyle \Sigma__{n}}$${\estilo de visualización A}$${\displaystyle \Sigma__{n}}$${\displaystyle \Sigma__{n}}$${\estilo de visualización B}$${\estilo de visualización B}$${\estilo de visualización A}$$Estilo de visualización: Pi__{n}$

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

Empíricamente, si la definición "más obvia" de un conjunto es [resp. ], generalmente podemos demostrar que es -completo [resp. -completo]. ${\estilo de visualización A}$${\displaystyle \Sigma__{n}}$$Estilo de visualización: Pi__{n}$${\estilo de visualización A}$${\displaystyle \Sigma__{n}}$$Estilo de visualización: Pi__{n}$

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