¿Cómo es contable el conjunto de todos los programas?

Question

Me cuesta ver cómo el número de programas no es incontable, ya que para cada número real se puede crear un programa que imprima ese número. ¿No establece eso inmediatamente un número incontable de programas?

Answer 1

No conozco su definición de "programa", pero estoy bastante seguro de que cualquier programa será una cadena de caracteres de longitud finita sobre un alfabeto finito. Para cualquier conjunto finito $X$ el conjunto $X^*$ de todas las cadenas de longitud finita sobre $X$ es contable (por el mismo tipo de argumento que utilizarías para demostrar que los racionales son contables).

Answer 2

Si estás programando en un lenguaje que tiene las siguientes restricciones:

1. Sólo hay un número finito de caracteres en el lenguaje.
2. Todos los programas son finitos.

Entonces el conjunto de todos los programas es contable, ya que es un subconjunto de todas las cadenas finitas del lenguaje que a su vez es contable.

Además, ¿qué significa "imprimir un número real"? Si tiene una expansión decimal infinita (por ejemplo un número irracional) entonces imprimirlo nunca se detiene, ¿es este un comportamiento legal para tu programa? Si no, entonces ciertamente no puedes escribir un programa que imprima cada número real.

Si se le permite imprimir una salida de longitud infinita, y su programa es finito, entonces usted tiene que calcular el número de alguna manera, pero sólo hay un número contable de números que usted puede calcular sus valores. Así que de nuevo, no puedes imprimir todos los números reales.

Answer 3

De mi respuesta aquí .

El conjunto de todos los programas es contablemente infinito. Para ver por qué, observe primero que cada programa debe tener una longitud finita. En segundo lugar, observe que el conjunto de todos los programas posibles es infinito, ya que no importa lo que $n \in \mathbb{N}$ que elija, siempre podrá escribir un programa más largo que $n$ . A continuación $S_n$ sea el conjunto de todos los programas de longitud $n$ . Cada $S_n$ es finito. El conjunto de todos los programas de todas las longitudes posibles es una unión contable de conjuntos $S_n$ :

$$ S = \bigcup_{n=0}^\infty S_n $$

Dado que la unión contable de conjuntos contables (o finitos) es a lo sumo contable, concluimos que el conjunto de todos los programas es contable.

Answer 4

En un lenguaje de programación que funciona traduciendo unidades de compilación enteras (como archivos fuente) cada vez, el conjunto de programas posibles es contable. Un flujo infinitamente largo no se considera un programa válido, porque el compilador nunca termina y, por tanto, nunca hay una forma ejecutable.

En un lenguaje de programación que puede interpretar (o compilar, sobre la marcha) un flujo de código indefinidamente largo (como el de una sesión interactiva) y producir comportamientos útiles antes de llegar al final del flujo, el conjunto de programas es incontable.

Así, por ejemplo, el conjunto de posibles sesiones interactivas Lisp (que son programas de facto) es incontable, mientras que el conjunto de posibles programas C es contable.

Cada programa finitamente largo corresponde a un número entero, por lo que puede haber una correspondencia de uno a uno entre programas y números enteros. Los programas infinitamente largos corresponden a los números reales.

Answer 5

Véase esta respuesta o cualquiera de las otras buenas respuestas a esa pregunta. (Ignora las malas respuestas.) No todos los números reales son computables, así que no puedes hacer lo que propones.