Hay un subconjunto de enteros positivos que ningún programa de computadora puede imprimir

Question

Se dice que un programa de ordenador "imprime" un conjunto A ($A \subconjunto \mathbb N$, enteros positivos.) si se imprime cada uno de los elementos en orden ascendente (Incluso si a es infinito.). Por ejemplo, el programa puede "imprimir":

1. Todos los números primos.
2. Toda la cantidad de $5$ para $100$.
3. Números, incluyendo el "$7$" en ellos.

Demostrar que hay un conjunto de que ningún programa de ordenador, puede imprimir.

Supongo que tiene algo que ver con un algoritmo destinado a manipular o confundir al programa, o para crear una paradoja, pero no puedo encontrar un ejemplo para demostrar esto. Alguna ayuda?

Chicos, esto me fue dado por mi profesor de Teoría de conjuntos, es decir, esta pregunta no se refiere equipo, pero lo considera un algoritmo que no puede agotar P(N). Todo lo que usted dice acerca de la computadora o el número de programas que realmente no me ayuda con esto... La prueba que ha de contener el Conjunto de la Teoría de las reclamaciones, y que probablemente tiene que encontrar un conjunto de términos que hacen que sea imposible para el programa de impresión. Yo no estoy diciendo que las pruebas incluidos los informáticos no son buenos, por el contrario, supongo que son maravillosos, pero yo realmente no lo entiendo, ni me necesitan para su uso, se trata de conjuntos.

Answer 1

No es realmente una elegante prueba de esto, que prácticamente no requiere de experiencia en las matemáticas.

Todos los programas de ordenador son una secuencia finita de bytes, que es sólo un número en base 256. Para cada programa de ordenador puede ser representado como un número natural único. Esta declaración se explica en detalle a continuación de la brecha.

• Si un programa de ordenador imprime su propio número, luego de que el programa es de color azul y su número es de color azul.
• Si un programa no imprime su propio número, luego de que el programa es rojo y su número es rojo.

El conjunto de rojo los números es un subconjunto de los números naturales. Ahora escribir un programa que imprime este conjunto. Es que el programa rojo o el azul?

• Supongamos que el programa es rojo. A continuación, debe imprimir su propio número como parte del conjunto, pero esto hace que sea un azul programa.
• Supongamos que el programa es de color azul. A continuación, debe imprimir su propio número de azul programa, pero esto hace que su salida no esté en el conjunto de rojo los números.

Este programa es imposible! Por lo tanto, debe existir al menos un conjunto de programas que puede que no se imprima.

Así es como me enteré de que el conjunto de Cantor/subconjunto de la desigualdad. No podía encontrar un mejor enlace, pero lo tengo de Martin Gardner libro.

---

Anexo

Vamos a entrar en la declaración de

cada programa de ordenador puede ser representado como un número natural único

Esto implicará algunos de matemáticas, en particular cuando se trabaja en binario. Vamos a crear una numeración de Gödel para los programas de ordenador.

Suponga que cada programa puede ser representado como un número finito de cadena de 0's y 1's. Esto describe con precisión el mundo real de los programas y la entrada a una Máquina de Turing Universal.

Por lo que cualquier programa dado X es x₁x₂...x_N , donde x_i es 0 o 1 para cada i.

Definamos Num(X) como el número binario 1 x₁x₂...x_N. Num(X) del programa X = '0110' sería '10110' en binario, que es de 22.

Num(X) le da a cada programa un número natural único, porque...

• Si dos programas tienen diferente longitud, a continuación, el programa más largo tiene un mayor Num() de la menor.
• Si dos programas tienen la misma longitud, pero difieren en algunos trozos, a continuación, la representación binaria es diferente para que poco, por lo Num() serán diferentes entre los programas.
• En cualquier otro caso, los dos programas tienen la misma longitud y con idéntica bits, lo que significa que son idénticos a los programas.

Ahora podemos conseguir que en el conjunto de la teoría parte de la prueba.

La prueba supone binario, pero en la medida en que su programa es finitely describible en cualquier idioma que utiliza un número finito de caracteres (como el inglés!) del mismo modo se puede asignar a un único número natural. Esto es interesante porque se extiende la prueba de los programas a cualquier descriptible concepto (como el genio de los deseos!).

Answer 2

Hay numerable muchos programas pero el número de subconjuntos de $\mathbb{N}$ es incontable.

Answer 3

Cualquier modelo de la informática, y por lo tanto, cualquier equipo nos puede hacer, es equivalente a una máquina de Turing. Dado que el número de posibles entradas y los estados de una máquina de Turing es finito, hay, como la Yihad dijo, countably muchos programas disponibles. Ya que hay una cantidad no numerable de subconjuntos de los números naturales, debe haber algunos subconjuntos de que el equipo no puede imprimir.

Si usted quiere encontrar algo específico, usted debe buscar para uncomputable funciones, o indecidible problemas.

Por ejemplo, usted podría intentar imprimir A060843, el Busy Beaver números. El Busy Beaver función determina el número máximo de pasos que una $n$-estado de la máquina de Turing se puede tomar antes de parar. Básicamente, se indica la duración de un equipo puede ejecutar sin quedarse atascado en un bucle infinito. Crece muy rápidamente: sólo los primeros $4$ elementos de esta secuencia se conoce exactamente, la quinta es conocido por ser más de $47 millones de dólares, y el sexto es de más de $8$ billones.

Encontrar un general-caso algoritmo para esta función sería equivalente a la resolución de la suspensión problema, que es indecidible. Esto significa que mientras que la secuencia está bien definido, no es computable.

O, teniendo en cuenta algunas de codificación de instrucciones lógicas con números naturales, se podría tener la impresión de que el conjunto de todos los $$ n cuando la declaración representado por $n$ es cierto. Esto es de Hilbert Decisión del Problema, o Entscheidungsproblem, y es muy similar (posiblemente equivalente, no estoy seguro) a WillO la respuesta acerca de los Números de Gödel.

Usted también podría romper a través de la auto-referencia, así como la Marca de Bennet sugiere.

Answer 4

Respuesta de Jihad demuestra que existe algunos tales $A$. Un ejemplo explícito, sea $A$ el conjunto de números Godel de declaraciones verdaderas sobre aritmética (después de fijar tu codificación preferida).

Answer 5

Una solución explícita en su sistema podría ser :

1. Considere la posibilidad de una enumeración de sus programas ($P_0$ es el primer programa, $P_1$ el segundo, y así sucesivamente)
2. Vamos a denotar por $P_{\! n}(m)$ m$^\mbox{th}$ número impreso por el programa de $P_{\!n}$ (si es que existe)
3. Considerar los enteros $i_n$ definida por $$i_n=n+1+\max_{j,k\le n}\{P_j(k)\}$$ (si el subconjunto es vacía, sólo recuerde que el máximo de un subconjunto vacío es de $0$).
4. Por lo tanto $i_{n+1}>i_n$
5. El conjunto $\{i_n\}_{n\in\mathbb N}$ no puede ser impreso como usted quiera, porque si se puede imprimir en orden ascendente por algún programa, entonces hay un costo de $s$ que $P_s(n)=i_n$, pero entonces $$P_s(s)=i_s\ge s+1+P_s(s)>P_s(s)$$ Esta es una contradicción !