AFAIK, turing números computables son números cuyo i-ésimo índice puede ser devuelto por una máquina de Turing. Entonces, un número no computable sería algo así como un número cuyos decimales se deciden si otro programa se detiene en alguna otra entrada, etc. Pero, de nuevo, PI es un número real, que no puede ser enumerado por un T.M. y por lo tanto, no puede ser computado? Entonces, ¿qué escuela de pensamiento es la correcta?¿Es PI un número computable?
Sí, π es computable. Hay unas pocas definiciones equivalentes de computable, pero la más útil aquí es la que usted ha dado arriba: un número real r es computable si existe un algoritmo para encontrar su n dígito. Here es un algoritmo de este tipo.
Su último argumento no es correcto; ha confundido la definición "puede encontrar el n º dígito" con "puede enumerar todos los dígitos". Esta última no es una definición útil: ¡descarta todas las irracionales y muchas racionales también!
Un hecho interesante es que los números computables son de hecho contables, ya que podemos obtener el número Godel de las máquinas Turing que los producen. Por lo tanto, casi ningún real es computable.
Creo que quiere decir que casi todos los números reales * no * son computables, ya que el conjunto de máquinas de Turing es contable. –
@larsmans: sí, por supuesto =) – katrielalex
¡Gracias por aclarar eso! ¡Aclamaciones! –
No estoy muy seguro de lo que quiere decir con "PI es un número real, que no puede ser enumerado por un T.M.". Sí, los números reales no son enumerables, pero no veo cómo esto afecta si PI es computable. '4' también es un número real, pero eso no significa que no sea computable. – sepp2k
Um, lo que quise decir fue, pensé que tomaría una Máquina de Turing infinitamente larga calcular PI, ya que PI es infinitamente largo. –
@Gaurav: con ese argumento, ¿llevaría una máquina de Turing infinitamente larga calcular '1/3', ya que' 1/3 = 0.333333 ... 'es infinitamente largo? – katrielalex