¿Podríamos diseñar una máquina de Turing que diera salida a cada bit de $\pi$ uno tras otro correctamente con una longitud de cinta limitada?

Question

¿Podríamos diseñar una máquina de Turing que diera salida a cada bit de $\pi$ uno tras otro correctamente?

Creo que la respuesta es sí porque tenemos programas informáticos que calculan el valor de $\pi$ día tras día para siempre, y así es viable.

Sin embargo, ¿podríamos hacerlo si la máquina de Turing tiene una longitud de cinta limitada?

Answer 1

Una máquina de Turing con una cinta de longitud limitada es básicamente un autómata de estado finito, ya que sólo hay un número finito de configuraciones posibles de datos en la cinta y sólo un número finito de estados en la propia máquina. Lo que esto significa es que cualquier secuencia de números producida por una máquina de este tipo va a ser finalmente periódica - en particular, ningún número irracional puede ser producido de esta manera.

Answer 2

Todos los programas de ordenador pueden modelarse como máquinas de Turing, ya que los ordenadores modernos son fundamentalmente máquinas giratorias.

Mientras no necesitemos guardar todos los dígitos a medida que los generamos, podríamos utilizar una serie para pi para obtener una precisión cada vez mayor y así dar salida a un flujo de dígitos.

ACTUALIZACIÓN: Esto no es correcto, pero creo que los comentarios son importantes, así que lo dejaré.