Si. Existe un teorema llamado teorema de dominación de Martin que establece que para cualquier grado de Turing por encima de los conjuntos decidibles, existe una función de ese grado que domina todas las funciones computables.
Además, sabemos que hay grados de Turing entre los conjuntos decidibles y su salto de Turing (los problemas que podemos resolver con el problema de detención como un oráculo).
Dado que la función Busy Beaver es equivalente a Turing al problema de Halting, se deduce que existe una función no controlable que domina cada función computable pero que, según su definición, crece asintóticamente más lentamente que la función Beaver (porque de lo contrario, podría usarse para resolver el problema de Halting) , contradiciendo la suposición sobre su grado de Turing).
No puedo darle ningún ejemplo natural de tal función porque no se conoce ninguno. La existencia se demuestra utilizando un procedimiento muy técnico que puede encontrar aquí: Asintótico vinculado a todas las funciones computables inferiores a la función Busy Beaver
- ¿Cuál es un ejemplo de un problema cuya respuesta no es obvia, pero si los datos se visualizan de una manera nueva, se vuelven más fáciles de resolver?
- ¿Por qué la suma, pero no la resta, es asociativa?
- ¿Cuál es el problema P versus NP en informática?
- ¿Cuántas matemáticas hay que saber para PNL?
- ¿Cómo se pueden representar los números negativos en 0 y 1 binarios para que la computadora pueda leer con precisión?
Mientras escribía esta respuesta, sabía que existen grados de Turing que están estrictamente entre los conjuntos computables y su salto de Turing y pensé que este hecho podría usarse para construir fácilmente alguna función usando la diagonalización, pero no pude encontrar ninguna, así que busqué funciones de rápido crecimiento asociadas con los grados de Turing en Google y encontré el teorema de dominación de Martin. Nunca había leído sobre este teorema en ningún libro de Teoría de la Computación hasta ahora, pero definitivamente vale la pena saberlo porque establece que cada grado de Turing indecidible tiene sus propias funciones de rápido crecimiento y que, por lo tanto, existe una estrecha conexión entre el crecimiento rápido funciones y computabilidad oráculo.
