Comencemos con el brillante informático y matemático, Alan Turing. Entre los legos, es conocido sobre todo por ser decisivo para descifrar el código del dispositivo de cifrado de Alemania, llamado Enigma Machine. Esta fue una hazaña asombrosa, y muchos historiadores piensan que acortó la Segunda Guerra Mundial en dos o tres años.
Entre los científicos informáticos, Turing es más conocido por preguntar y luego responder a esta pregunta crítica en la década de 1930:
¿Qué puede ser calculado por una máquina?
- ¿Sería posible construir una máquina que pueda 'mirar' al pasado?
- ¿Cuáles son los conceptos más complicados en informática?
- ¿Cómo es tomar CS 124 (Sistemas operativos) en Caltech?
- ¿Qué es una hoja de ruta UX? ¿Cuándo y por qué se crea?
- ¿Las grandes empresas comerciales (como Glencore) están interesadas en el aprendizaje automático / IA?
Para responder a esto, Turing pensó en cómo las personas calculaban las cosas. Por ejemplo, piense en cómo multiplica dos números naturales.
(Por supuesto, la mayoría de ustedes no tienen idea de cómo multiplicar números porque simplemente sacan una aplicación de calculadora en su teléfono inteligente. Así que por ahora, solo pretendan que recordaron cómo multiplicar).
Sacarías un trozo de papel y comenzarías a hacer cosas. Cuando Turing pensó en resolver tales problemas, se dio cuenta de lo siguiente:
- Cuando resolvemos un problema en una hoja de papel, lo hacemos paso a paso.
- Cuando resolvemos un problema, tiene que tomar solo un número finito de pasos. (De lo contrario, nunca terminaríamos).
- Cuando resolvemos un problema, solo podemos usar un número finito de trozos de papel. (De lo contrario, nos quedaríamos sin árboles para hacer papel).
Luego, Turing formalizó esta idea con lo que ahora llamamos una ‘máquina de Turing’. Este es un modelo matemático sobre cómo podemos resolver cualquier problema que tenga solución. Mostró cómo crear una máquina de Turing, en una hoja de papel, que podría multiplicarse, ordenar una lista o determinar si un número es primo.
Tenga en cuenta que hizo esto antes de que hubiera computadoras de uso general.
Y luego Turing continuó y preguntó: “¿Hay algún problema matemático que no se pueda resolver?” Hoy, podríamos decir: “¿Hay algún problema matemático que no se pueda calcular?”
Turing respondió eso también. Él demostró que hay bastantes problemas matemáticos que son indiscutibles. ¿Como que?
Veamos algunas proposiciones matemáticas: declaraciones matemáticas que son verdaderas o falsas.
Primero, recuerde que un número natural (que es mayor que 1) es primo si solo es divisible por 1 y por sí mismo.
“Hay un número infinito de números primos”. (Esta es una proposición verdadera).
“Dos más dos son siete”. (Según mi calculadora, esto es falso).
Aquí hay uno más que necesitará un poco de historia para entender. Dos números primos se denominan ‘pares primos’ si son dos números primos impares consecutivos. Por ejemplo, 17 y 19 son un par primo. Así son 41 y 43. Ahora considere esta proposición:
“Hay un número infinito de pares primos”.
Y esta propuesta es: no lo sabemos. Los matemáticos piensan que es cierto, pero aún no hay pruebas.
Aquí está el punto interesante. ¿Por qué no construir una computadora, o simplemente escribir un programa de computadora, al que podamos dar cualquier proposición matemática y que nos diga si la proposición es verdadera o falsa?
Buena idea. Excepto que Turing mostró que es imposible escribir dicho programa. En la terminología moderna, diríamos que determinar si una proposición dada es verdadera o falsa es indiscutible.
Este triste resultado es malo para la humanidad, pero mantiene a los matemáticos en el trabajo.
Hay muchos problemas tan importantes que son indiscutibles, un resultado muy interesante de las reflexiones de Turing.
Y ahora, para responder directamente a su pregunta sobre la teoría de los autómatas, la pregunta más importante que responde es lo que preguntó Turing. “¿Qué se puede calcular?”
Y una pregunta más de Automata Theory es esta. “Si algo se puede calcular, ¿qué tan rápido se puede calcular?”
La teoría de los autómatas tiene muchos términos geniales como “autómatas finitos no deterministas” y “autómatas” y “lenguajes recursivamente enumerables”.
Pero tendrás que tomar el curso (de mí, por supuesto) para descubrir lo que significan.
