¿Es tan difícil predecir (en el límite) secuencias computables como el problema de detención?

Pregunta : ¿Es tan difícil predecir (como se define a continuación) las secuencias computables como el problema de detención?

Elaboración : "Predecir" significa predecir con éxito, lo que significa cometer solo un número finito de errores en la tarea de intentar predecir el enésimo bit de la secuencia con acceso a los bits n-1 anteriores (comenzando desde el primer bit y pasando por el secuencia computable infinita entera).

Existe un argumento de diagonalización simple (debido a Legg 2006) que para cualquier predictor de máquina de Turing p, hay una secuencia computable en la que comete infinitos errores. (Construya una secuencia que tenga como enésimo término el opuesto de lo que p predice dados los términos n-1 anteriores en la secuencia). Por lo tanto, no hay un predictor computable que prediga cada secuencia computable. Un oráculo de detención permitiría la construcción de tal predictor. Pero, ¿puedes demostrar que tener ese predictor te permite resolver el problema de detención?

Más elaboracion

Definición (Legg)
Un predictor p es una máquina de Turing que intenta predecir el enésimo bit de una secuencia S con acceso a los n-1 bits anteriores. Si la predicción no coincide con el enésimo bit de la secuencia, llamamos a esto un error . Diremos que p predice S si p solo comete muchos errores finitos en S. En otras palabras, p predice S si hay algún número M en la secuencia st para cada m> M, p predice correctamente el m-ésimo bit de S dado acceso a los primeros m-1 bits.

Formalmente, podríamos definir una máquina de predicción con tres cintas. La secuencia se ingresa como entrada bit a bit en una cinta, las predicciones para el siguiente bit se realizan en una segunda cinta (la máquina solo puede moverse a través de esta cinta), y luego hay una cinta de trabajo en la cual la máquina Puede moverse en ambas direcciones.

Resultados simples
Según la definición anterior, hay un predictor que predice todos los números racionales. (Use la enumeración estándar en zig-zag de los racionales. Comience prediciendo el 1er racional en la lista, si hay un error, pase al siguiente racional). Por un argumento similar, hay un predictor que da acceso a N, es capaz de predecir todas las secuencias de complejidad de Kolomogorov menores o iguales a N. (Ejecute todas las máquinas de N bits en paralelo y tome la predicción de la máquina que se detiene primero Solo puedes cometer muchos errores).

Cita Shane Legg 2006 http://www.vetta.org/documents/IDSIA-12-06-1.pdf (no es el autor de esta publicación)

En realidad, esto es más fácil que resolver el problema de detención.

$f:\mathbb N\rightarrow\mathbb N$$g:\mathbb N\rightarrow\mathbb N$$n$$g(n)\le f(n)$

$\varphi_e$$e\in\mathbb N$$\mathbb N$$\{0,1\}$

$f$$p$

$p(a_0,\ldots,a_{k-1})$$a_{k}\in \{0,1\}$$a_0,\ldots,a_k$$\varphi_t(0),\ldots,\varphi_t(k)$$t\le k$$f(k)$$f(k)$$t$$a_{k}$$=0$

$q$$\varphi_q$$k$$t=q$$a_{k}$$f$$\varphi_q$$s(n)=$$\varphi_q(n)$