número computable
En matemáticas , los números computables son los números reales que se pueden calcular con cualquier precisión deseada mediante un algoritmo de terminación finito . También se les conoce como números recursivos , números efectivos [1] o reales computables o reales recursivos . [ cita requerida ]
Se pueden dar definiciones equivalentes utilizando funciones μ-recursivas , máquinas de Turing o cálculo λ como representación formal de algoritmos. Los números computables forman un campo cerrado real y se pueden usar en lugar de los números reales para muchos propósitos matemáticos, pero no para todos.
A continuación, Marvin Minsky define los números a calcular de manera similar a los definidos por Alan Turing en 1936; [2] es decir, como "secuencias de dígitos interpretadas como fracciones decimales" entre 0 y 1: [3]
Un número computable [es] aquel para el que existe una máquina de Turing que, dado n en su cinta inicial, termina con el enésimo dígito de ese número [codificado en su cinta].
Las nociones clave en la definición son (1) que algún n se especifica al principio, (2) para cualquier n , el cálculo solo toma un número finito de pasos, después de lo cual la máquina produce la salida deseada y termina.
Una forma alternativa de (2) – la máquina imprime sucesivamente todos los n de los dígitos en su cinta, deteniéndose después de imprimir el n – enfatiza la observación de Minsky: (3) que mediante el uso de una máquina de Turing, una definición finita – en la forma de la tabla de estado de la máquina – se utiliza para definir lo que es una cadena potencialmente infinita de dígitos decimales.
