Teorema de base (computabilidad)

En la teoría de la computabilidad , hay varios teoremas básicos . Estos teoremas muestran que tipos particulares de conjuntos siempre deben tener algunos miembros que, en términos de grado de Turing , no sean demasiado complicados. Una familia de teoremas básicos se refiere a conjuntos efectivamente cerrados no vacíos (es decir, conjuntos no vacíos en la jerarquía aritmética ); estos teoremas se estudian como parte de la teoría clásica de la computabilidad. Otra familia de teoremas básicos concierne a conjuntos analíticos no vacíos (es decir, en la jerarquía analítica ); estos teoremas se estudian como parte de la teoría hiperaritmética . ${\ Displaystyle \ Pi _ {1} ^ {0}}$ ${\ Displaystyle \ Sigma _ {1} ^ {1}}$

Los conjuntos efectivamente cerrados son un tema de estudio en la teoría clásica de la computabilidad. Un conjunto efectivamente cerrado es el conjunto de todas las rutas a través de algún subárbol computable del árbol binario . Estos conjuntos son cerrados, en el sentido topológico , como subconjuntos del espacio de Cantor , y el complemento de un conjunto cerrado efectivo es un conjunto abierto efectivo en el sentido de espacios polacos efectivos . Kleene demostró en 1952 que existe un conjunto no vacío, efectivamente cerrado, sin punto computable (Cooper 1999, p. 134). Los teoremas básicos muestran que debe haber puntos que no estén "demasiado lejos" de ser computables, en un sentido informal. ${\ Displaystyle 2 ^ {<\ omega}}$ ${\ Displaystyle 2 ^ {\ omega}}$

Una clase es una base para conjuntos efectivamente cerrados si cada conjunto efectivamente cerrado no vacío incluye un miembro de (Cooper 2003, p. 329). Los teoremas básicos muestran que clases particulares son bases en este sentido. Estos teoremas incluyen (Cooper 1999, p. 134): ${\ Displaystyle {\ mathcal {C}} \ subseteq 2 ^ {\ omega}}$ ${\ Displaystyle {\ mathcal {C}}}$

Aquí, un conjunto es bajo si su salto de Turing , el grado del problema de detención . tiene un grado libre de hiperinmunidad si cada función computable total está dominada por una función computable total (es decir, para todas ). ${\ Displaystyle X \ subseteq \ mathbb {N}}$ ${\ Displaystyle X '= \ varnothing'}$ ${\ Displaystyle X}$ ${\ Displaystyle X}$ ${\ Displaystyle f \ colon \ mathbb {N} \ to \ mathbb {N}}$ ${\ Displaystyle g}$ ${\ Displaystyle f (n) \ leq g (n)}$ ${\ Displaystyle n}$

También existen teoremas básicos para conjuntos de caras claras. Estos teoremas básicos se estudian como parte de la teoría hiperaritmética . Un teorema es el teorema de la base de Gandy, que es análogo al teorema de la base baja. El teorema de la base de Gandy muestra que cada uno no está vacío . El conjunto tiene un elemento que es hiperaritméticamente bajo, es decir, que tiene el mismo hipergrado que el conjunto de Kleene . ${\ Displaystyle \ Sigma _ {1} ^ {1}}$ ${\ Displaystyle \ Sigma _ {1} ^ {1}}$ ${\ Displaystyle {\ mathcal {O}}}$