¿Es el conjunto de todos los programas C++ válidos infinito numerable?

Question

He oído que el conjunto de programas válidos en un determinado lenguaje de programación es infinito numerable. Por ejemplo, el conjunto de todos los programas C++ válidos es infinito numerable.

No entiendo por qué sin embargo. Un lenguaje de programación tiene llaves abiertas y el correspondiente cierre unos. ¿Uno no necesita una pila para rastrear las llaves? Por lo tanto, ¿cómo puede un diseño un DFA que acepta programas de C++ válidos?

Answer 1

Así la validez de un programa de C++ (o en realidad cualquier programa de C++) será simplemente una secuencia finita compone de un conjunto finito de caracteres y un par de otras cosas (sangría, espacios, etc.). Es un resultado general que el conjunto de todas las secuencias finitas de entradas a partir de un alfabeto finito será countably infinito. Para mostrar que hay countably infinitamente muchos válido programas de C++, usted sólo necesita demostrar que no hay finito límite superior de la longitud de los programas de C++.

Anexo: Otro enfoque (una alternativa de mostrar que no hay ningún límite superior finito de longitud) es definir explícitamente (en un sentido teórico) countably infinitamente muchos válido programas de C++. Por ejemplo, para un determinado número entero positivo, el programa que simplemente imprime dijo entero, entonces termina (como ya he mencionado en los comentarios de abajo).

La siguiente plantilla de programa debe hacer el truco:

 #include<iostream>
 using namespace std;

 int main ()
 {
 cout << "___________";
 return 0;
 }

Que "____" es el lugar donde debes escribir en cualquier entero positivo que quería que el programa para imprimir-ya sea $1$, o $23234$, o $1763598730987307865$, o lo que sea, en lugar de los caracteres de subrayado.

Ahora, obviamente, no importa lo rápido que se puede, existen enteros lo suficientemente grande que no podía terminar de escribir en su vida, por lo que en la práctica, hay programas de este tipo que nunca iba a terminar. Incluso si un programa se entregaron a usted, que sin duda va a ejecutar en problemas de memoria lo suficientemente grande para enteros (dependiendo del equipo), pero todavía deben ser válidos los programas. Podemos decir que este tipo de programas todos los que existen en una "teórica" de sentido. Es decir, dada la suficiente memoria y el poder para almacenar y ejecutar--necesariamente finita (aunque quizás excesivamente grande) cantidad-y dado el tiempo suficiente para programar y ejecutar--necesariamente finita (aunque quizás excesivamente largo) cantidad-en este programa se hace lo que se supone que debe hacer.

Por favor, no me dan ninguna pena acerca de la muerte de calor del universo, o algo como eso. ;)

Answer 2

Countably infinito no significa regular. El C++ gramática no es regular. De hecho, no es ni siquiera de contexto libre. Sin embargo, el conjunto de todos válidos los programas de C++ es countably infinito. Para ver por qué, primer aviso de que es infinita. No importa lo $n \in \mathbb{N}$ que usted escoja, usted siempre puede escribir un programa de C++ que es más de $n$. A continuación, vamos a $S_n$ ser el conjunto de todos los programas de C++ de longitud $n$. Cada $S_n$ es finito. El conjunto de todos los programas de C++ (de todas las longitudes posibles) es un contable de la unión de los conjuntos de $S_n$:

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

Desde el contable de la unión de contables (o finito) conjuntos es en la mayoría de los contables, llegamos a la conclusión de que el conjunto de todos válidos los programas de C++ es contable.

Answer 3

Un programa de C++ es una secuencia finita de caracteres en un alfabeto finito especificado. El conjunto de todas las secuencias finitas de caracteres de ese alfabeto es infinito numerable. El conjunto de todos los programas C++ válidos es un subconjunto del conjunto de todas las secuencias finitas de caracteres de ese alfabeto. Un subconjunto infinito de un conjunto infinito numerable es infinito numerable.

(Es infinito porque no hay ningún límite superior finito en las longitudes de los programas de C++).

Answer 4

Propongo la siguiente:

1. Cada número natural es un programa (un archivo no es nada pero un número muy grande).

2. Algunos de estos programas son válidos los programas de C++.

Si se demuestra ahora, que por cada válido programa de C++ n, existe un programa de n + m que es válido de un programa de C++ así, el número de programas de C++ es contable infinito.

1. Vamos a n_0 ser un clásico programa hola mundo.

2. para cada n, existe un m que añade un trivial de la línea n ( cout<<"Hola!";)

3. A prueba de niños.

Answer 5

Como varios carteles ya han señalado, el conjunto de programas de c ++ válidos es infinito numerable.

Preocupación de la OP tiene algún mérito aunque. En una computadora real , la memoria es finita, así que un programa válido no es sólo una determinada cadena finita , sino una cadena finita de longitud limitada , y así el conjunto de programas válidos, analizable en un equipo específico es finito (pero gran).