En la teoría de la computabilidad , los conjuntos de índices describen clases de funciones computables ; específicamente, dan todos los índices de funciones en una determinada clase, de acuerdo con una numeración fija de Gödel de funciones computables parciales.
Definición
Dejar ser una enumeración computable de todas las funciones computables parciales, y ser una enumeración computable de todos los conjuntos ce .
Dejar ser una clase de funciones computables parciales. Si luego es el conjunto de índices de. En general es un índice establecido 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.
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 :
Dejar ser una clase de funciones computables parciales con su conjunto de índices . Luego es computable si y solo si está vacío, o es todo de .
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 un colocar es -completa si, para cada colocar , hay una reducción m de a . -La completitud se define de manera similar. A continuación se muestran algunos ejemplos: [2]
- es -completo.
- es -completo.
- es -completo.
- es -completo.
- es -completo.
- es -completo.
- es -completo.
- es -completo.
- es -completo, donde es el problema de la detención .
Empíricamente, si la definición "más obvia" de un conjunto es [resp. ], normalmente podemos mostrar que es -completo [resp. -completo].
Notas
- ^ Odifreddi, PG Classical Recursion Theory, Volumen 1 .; página 151
- ^ Soare, Robert I. (2016), "Turing Reducibility" , Turing Computability , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 51–78, ISBN 978-3-642-31932-7, consultado el 21 de abril de 2021