Cardinalidad del conjunto de algoritmos.

Alguien en una discusión mencionó que (él cree) que puede haber al menos un número continuo de estrategias para abordar un problema específico. El problema específico eran las estrategias comerciales (no los algoritmos sino las estrategias), pero creo que eso no viene al caso en mi pregunta.

Esto me hizo pensar en la cardinalidad del conjunto de algoritmos. He estado buscando un poco pero no he encontrado nada. He estado pensando que, dado que las máquinas de Turing funcionan con un conjunto finito de alfabeto y la cinta debe ser indexable, por lo tanto, contable, es imposible tener un número incontable de algoritmos. Es cierto que mi teoría de conjuntos está oxidada, así que no estoy seguro de que mi razonamiento sea válido y probablemente no podría probarlo, pero es un pensamiento interesante.

¿Cuál es la cardinalidad del conjunto de algoritmos?

Un algoritmo se describe informalmente como una secuencia finita de instrucciones escritas para realizar alguna tarea. Más formalmente, se identifican como máquinas de Turing, aunque también podría describirlas como programas de computadora.

El formalismo preciso que usa no importa mucho, pero el punto fundamental es que cada algoritmo puede escribirse como una secuencia finita de caracteres, donde los caracteres se eligen de un conjunto finito, por ejemplo, letras romanas, ASCII o ceros y unos. Por simplicidad, supongamos ceros y unos. Cualquier secuencia de ceros y unos es solo un número natural escrito en binario. Eso significa que hay como máximo una infinidad de algoritmos contables, ya que cada algoritmo puede representarse como un número natural.

Para obtener el crédito completo, debe preocuparse de que algunos números naturales no codifiquen programas válidos, por lo que puede haber menos algoritmos que los números naturales. (Para crédito de bonificación, es posible que también se pregunte si es posible que dos números naturales diferentes representan el mismo algoritmo.) Sin embargo, print 1, print 2, print 3y así sucesivamente son todos los algoritmos y todos diferentes, por lo que hay al menos infinitamente contables algoritmos.

Entonces concluimos que el conjunto de algoritmos es infinitamente contable.

El conjunto de algoritmos es infinitamente contable. Esto se debe a que cada algoritmo tiene una descripción finita, por ejemplo, como una máquina de Turing.

El hecho de que un algoritmo tenga una descripción finita nos permite ingresar un algoritmo en otro, y esta es la base de la teoría de la computabilidad. Nos permite formular el problema de detención, por ejemplo.

al menos un número continuo de estrategias para abordar un problema específico

Se supone que "continuo" significa los números reales ... usar "al menos" junto con esa palabra es absurdamente exagerado. Para ser un poco irónico: incontablemente infinito es bastante grande, pero incontablemente infinito es ... más grande que grande. Enormemente más. Insondable.

Así que vamos a tirar eso por la ventana. Para ver qué tipo de infinito estamos tratando es muy simple (e intuitivo, incluso si su amigo nunca ha oído hablar de ninguna ciencia teórica de la informática):

• Cualquier algoritmo puede implementarse con cualquier lenguaje completo de turing; elige tu veneno favorito de los lenguajes del mundo real (Java, C, ...) para desmitificar esto un poco. Todos estos son equivalentes con el conjunto teórico de algoritmos que cualquiera podría inventar. Tenga en cuenta que cada algoritmo es en sí mismo finito, es decir, no hay algoritmos que tomarían infinitos símbolos para anotar.
• No pienses en máquinas de Turing complicadas. Su idioma de elección utiliza archivos simples para almacenar su código fuente. Cada archivo es una colección de pequeños números (también conocidos como bytes). Lo importante es que estos números son definitivamente enteros, no continuos. (Si usted es un purista y quiere permanecer en el régimen teórico, reemplace la palabra "byte" con "símbolo", no cambia nada). Si tiene miedo de los programas grandes que se distribuyen en varios archivos (y bibliotecas , y otras cosas), luego simplemente mételos en un solo archivo comprimido (es decir, un solo archivo).
• Ahora, puede asignar un solo número entero a cada archivo, biyetivamente. Simplemente escribimos todo el lío de bits / bytes del archivo uno tras otro, y terminamos con un gran número expresado en binario. En el pasado distante, la gente realmente hacía eso: imprimían programas binarios compilados como largas listas de números hexadecimales en revistas; los escribiría, pero nunca los verá como algo más que números (a menudo agrupados convenientemente en conjuntos de 8 o 16 dígitos para facilitar la escritura).
• Entonces: cada programa puede ser representado por un número entero, aunque sea arbitrariamente grande. A la inversa, también funciona: cada número entero puede transferirse inmediata y trivialmente a un archivo y arrojarse a un compilador (obviamente, solo una pequeña parte de esos serán programas válidos, pero eso no nos importa ahora).
• Al final, los programas, y por lo tanto los algoritmos, son un subconjunto de los enteros; por lo tanto, solo contablemente pueden existir muchos.
• NB, el hecho de que haya muchas implementaciones diferentes de un solo algoritmo está a nuestro favor, es decir, muchos de esos enteros se condensan en (diferentes representaciones de) el mismo algoritmo. Entonces, si el infinito contable ya no era el tipo más pequeño de infinito, tendríamos que preocuparnos de que el número de algoritmos sea aún más pequeño, pero ciertamente no más grande (es decir, incontable).

El problema específico eran las estrategias comerciales (no algoritmos sino estrategias)

No sé qué quiere decir tu amigo con "estrategia"; Supongo que quiere decir algo que es algo así como un algoritmo, pero que no está formulado con suficiente detalle como para piratearlo en una computadora. ¿O que de alguna manera depende de la "intuición" humana durante la ejecución? Si es así, estos son solo detalles irrelevantes. La humanidad aún no ha encontrado ningún tipo de descripción de procesos que sea más poderosa o más grande que los "algoritmos" en el sentido que usamos en CS.

Ver numeración de Gödel , es un hecho básico en informática que los algoritmos son contables, como lo son, por extensión, conjuntos enumerables recursivamente.

Como los algoritmos son contables, es fácil mostrar que no existe un algoritmo para verificar cada conjunto en un sistema formal (asignar un valor de verdad a un problema). Esto sería equivalente a asignar un algoritmo a cada función que asigna el conjunto de problemas a valores booleanos. Sin embargo, el conjunto de estas funciones es incontable (trivialmente de la misma cardinalidad que el conjunto de poder del conjunto de problemas, por lo tanto incontable).

Espero que esto dé alguna intuición de por qué los algoritmos tienen que ser "menos poderosos" que cualquier función, por lo tanto contables (ignoremos la hipótesis del continuo aquí).

Si uno no comienza con el requisito de que una estrategia debe ser implementable con un algoritmo e ignora los efectos de discretización de la vida real, podría, por ejemplo, aceptar lo siguiente como una estrategia comercial parametrizada:

$a$$b$$a$$b$

$a$$b$ no es computable superior, entonces no podemos detectar que las condiciones son verdaderas.

Si concebimos los algoritmos como programas de computadora escritos en binario *, entonces el número de algoritmos es el número de números binarios (enteros). Así, la cardinalidad de los algoritmos es la cardinalidad de los enteros.

* Una prueba de que las máquinas de Turing pueden ejecutar todos los algoritmos, y que las computadoras pueden ejecutar cualquier programa de máquinas de Turing, haría que esta respuesta fuera innecesariamente larga. El primero puede depender de la definición de un algoritmo, pero no creo que esté utilizando estrategias comerciales inconfundibles.

Las otras respuestas ya explicaron que en el modelo estándar de computación (máquinas de Turing, cálculo lambda, etc.) el conjunto de algoritmos es infinitamente contable.

Sin embargo, hay otros modelos teóricos de computación en los que el conjunto de algoritmos es infinitamente infinito. Por ejemplo, las máquinas Blum – Shub – Smale tienen un conjunto de instrucciones infinitamente infinito ¹ , por lo que su conjunto de algoritmos también es infinitamente innumerable.

Dado que las máquinas de Turing funcionan con un conjunto finito de alfabeto y la cinta debe ser indexable, por lo tanto, contable

Dado un tamaño particular, hay muchas máquinas de Turing y hay muchos tamaños. Un conjunto contable de números, siempre que sean finitos, es contable. El tamaño del alfabeto es un factor en la cantidad de máquinas de Turing, pero el tamaño de la cinta no lo es. Si se permitiera que el alfabeto tuviera innumerables caracteres, entonces habría innumerables máquinas (cada número real podría codificarse como una secuencia de símbolos).

Si "algoritmo" simplemente quiere decir una correspondencia entre la entrada y la salida, y no una máquina de Turing o algo que es el sentido normal de "cálculo", entonces claramente si hay innumerables entradas diferentes, entonces hay innumerables algoritmos: Para cada número real, podríamos definir un "algoritmo" que toma un número natural como entrada y genera ese lugar decimal. Por ejemplo, dando la entrada "3" a la$\sqrt{.5}$algoritmo daría la salida de "7". (Tenga en cuenta que si bien es posible diseñar una máquina de Turing que proporcione el enésimo dígito de$\sqrt{.5}$, no es posible hacerlo para todos los números reales; solo contablemente muchos números reales son computables).