¿Es este número computable?

Question

Mi pregunta se basa en esta respuesta:

https://math.stackexchange.com/a/458768/292477

Dejemos que $T$ sea la máquina de Turing que busca una prueba de una contradicción en ZFC. Si ZFC es consistente, entonces si $T$ se detiene será independiente de ZFC. (De hecho, si no es así, entonces esto contradice el teorema de incompletitud de Gödel). (Zhen Lin)

Dado ahora este programa que imprime un número (la impresión no incluye una nueva línea):

print "0."
for i = 0 to infinity:
    halted = execute_i_steps_of_the_given_turing_machine_and_return_true_if_it_halted()
    if halted:
        print "1"
    else:
        print "0"

Creo que debería ser computable, pero no estoy seguro de que la definición del número sea válida.

¿Quizás alguien pueda ayudarme en esto? ¿Es un número computable?

Gracias

Answer 1

Sí, este número es computable. Su definición es un algoritmo para calcular sus dígitos.

De forma más general, hay que tener en cuenta que no saber cuál es el valor de un número tiene poco que ver con que el número sea computable. Por ejemplo, defina un número $n$ de la siguiente manera. Si ZFC es consistente, $n=1$ . Si ZFC es inconsistente, $n=0$ . Este número es ciertamente computable: o bien el programa que acaba de salir $1$ lo computa, o el programa que sólo emite $0$ lo computa. No importa que no podamos determinar (en ZFC) que de estos programas es el correcto: en cualquier caso, existe un programa que funciona.

Answer 2

Por supuesto, este valor es $0$ o $2^{-n}$ para algunos $n$ y todos esos números son computables, así que este número es computable. (Suponiendo que el resultado se trate como binario).

Si la base $10$ entonces este valor es $0$ o $9^{-1}\cdot 10^{-n}$ para algunos $n$ y cualquier número racional es computable.