¿Puede cualquier dígito finito de la función no computable ser siempre un computable?

Question

¿Puede cualquier dígito finito de la función no computable ser siempre computable? Si es así, ¿se crea una contradicción?

Dejemos que $\left\{a_n\right\}$ sea una secuencia binaria no computable y $f:\mathbb{N^+}\longrightarrow \left\{0,1\right\}$ ser un $n'$ dígito de la secuencia $a_n$ o $f(n):=\left\{a_n\right\}_{n\in\mathbb{N^+}}$ . Por supuesto, no tenemos $n'$ fórmula de los dígitos para $f(n)$ . ¿Implica esto que cualquier dígito finito de la secuencia binaria no computable tampoco es computable? En caso contrario, para cualquier $n\in\mathbb N^+$ , si $f(n)$ es computable, esto implica que $f(n)$ es computable lo que da una contradicción. ¿Cuáles son los puntos que me faltan?

Answer 1

Si entiendo correctamente su pregunta, cada dígito individual de su secuencia $f$ es 0 o 1. El 0 es computable, en concreto por el programa "print 0" (que ignora su entrada). Del mismo modo, el 1 es computable. Así que cada dígito individual en su secuencia es computable. Ninguno de estos hechos triviales tiene relación con el hecho de que toda la función $f$ es computable.

Answer 2

Una pista: Una función $\ g:\mathbb{N}^+\rightarrow\{0,1\}\ $ es computable si existe una máquina de Turing o equivalente que eventualmente devolverá el valor de $\ g(n)\ $ cuando se le da el valor de $\ n\ $ como entrada. Supongamos que $\ h:\mathbb{N}^+\rightarrow\{0,1\}\ $ no es computable y $\ g:\mathbb{N}^+\rightarrow\{0,1\}\ $ es computable. Definir $$ a_n=f(n)=\cases{g(n)& if $ n\in\mathbb{N}^+\\\N $ is odd,\\ h\left(\frac{n}{2}\right)& if $ n\in\mathbb{N}^+\\\N $ is even.} $$ Es $\ \left\{a_n\right\}\ $ ¿computable o no computable?