Conjunto de índices (computabilidad)

Clases de funciones recursivas parciales.

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

Definición

Sea una enumeración computable de todas las funciones computables parciales y 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 de índices de . En general, es un conjunto de índices si para cada uno con (es decir, indexan la misma función), tenemos . Intuitivamente, estos son los conjuntos de números naturales que describimos sólo con referencia a las funciones que indexan. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle A=\{x\,:\,\varphi _{x}\in {\mathcal {A}}\}}$ ${\displaystyle A}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle A}$ ${\displaystyle x,y\in \mathbb {N} }$ ${\displaystyle \varphi _{x}\simeq \varphi _{y}}$ ${\displaystyle x\in A\leftrightarrow y\in A}$

Conjuntos de índices y teorema de Rice

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 sólo si está vacío o es todo de . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle \mathbb {N} }$

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

Completitud en la jerarquía aritmética.

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 reducción m de a . -La integridad se define de manera similar. A continuación se muestran algunos ejemplos: ^[2] ${\displaystyle \Sigma _{n}}$ ${\displaystyle A}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle \Pi _{n}}$

• ${\displaystyle \mathrm {Emp} =\{e\,:\,W_{e}=\varnothing \}}$Esta completo. ${\displaystyle \Pi _{1}}$
• ${\displaystyle \mathrm {Fin} =\{e\,:\,W_{e}{\text{ is finite}}\}}$Esta completo. ${\displaystyle \Sigma _{2}}$
• ${\displaystyle \mathrm {Inf} =\{e\,:\,W_{e}{\text{ is infinite}}\}}$Esta completo. ${\displaystyle \Pi _{2}}$
• ${\displaystyle \mathrm {Tot} =\{e\,:\,\varphi _{e}{\text{ is total}}\}=\{e:W_{e}=\mathbb {N} \}}$Esta completo. ${\displaystyle \Pi _{2}}$
• ${\displaystyle \mathrm {Con} =\{e\,:\,\varphi _{e}{\text{ is total and constant}}\}}$Esta completo. ${\displaystyle \Pi _{2}}$
• ${\displaystyle \mathrm {Cof} =\{e\,:\,W_{e}{\text{ is cofinite}}\}}$Esta completo. ${\displaystyle \Sigma _{3}}$
• ${\displaystyle \mathrm {Rec} =\{e\,:\,W_{e}{\text{ is computable}}\}}$Esta completo. ${\displaystyle \Sigma _{3}}$
• ${\displaystyle \mathrm {Ext} =\{e\,:\,\varphi _{e}{\text{ is extendible to a total computable function}}\}}$Esta completo. ${\displaystyle \Sigma _{3}}$
• ${\displaystyle \mathrm {Cpl} =\{e\,:\,W_{e}\equiv _{\mathrm {T} }\mathrm {HP} \}}$está completo, ¿dónde 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. ], normalmente podemos demostrar que está completo [resp. -completo]. ${\displaystyle A}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle \Pi _{n}}$ ${\displaystyle A}$ ${\displaystyle \Sigma _{n}}$ ${\displaystyle \Pi _{n}}$

Notas

1. Odifreddi, PG Teoría clásica de la recursión, volumen 1 .; página 151
2. Soare, Robert I. (2016), "Reducibilidad de Turing", Computabilidad de Turing , teoría y aplicaciones de la computabilidad, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 51–78, doi :10.1007/978-3-642-31933- 4_3, ISBN 978-3-642-31932-7, recuperado 2021-04-21

Referencias

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