¿Qué matemática puede o no puede hacer una computadora?

Hay muchos problemas relativamente dentro del campo de la combinatoria y la teoría de juegos que actualmente solo pueden resolverse mediante una fuerza bruta intensa o búsquedas heurísticas del espacio de estado (árbol de juegos, etc.) para descubrir cuál es la respuesta exacta que está buscando, o la estrategia óptima, podría ser. No es que la computadora NO PUEDA hacerlo, es que a los seres humanos no les gustará esperar la respuesta. Aunque la velocidad de las computadoras sigue aumentando, su costo sigue disminuyendo, y las GPU y FPGA se utilizan cada vez más para acelerar los cálculos simples, muchas de estas respuestas aún están fuera del alcance, excepto a través de una intensa investigación y suficientes años de tiempo de ejecución de la computadora.

Por ejemplo, el esfuerzo de investigación bastante reciente para determinar el Número de Dios para las soluciones óptimas del Cubo de Rubik 3x3x3 (20 movimientos o menos) tomó 46 años de computación en Google más una gran optimización del código C y la teoría de grupos antes de que pudiera ser ejecutado. Luego, todo ese cálculo tuvo que hacerse de nuevo tomando la métrica del MIT para contar movimientos de cuarto de vuelta y no permitir medias vueltas (el número de Dios es 26 medido en esa métrica). Todo ese cálculo fue solo para encontrar el Número de Dios para cubos 3x3x3: la combinatoria explota cuando intentas encontrar propiedades similares de 4x4x4, 5x5x5 y cubos más grandes o cubos con diferentes geometrías (y grupos correspondientes) CADA rompecabezas de Rubik como cubo (permutación rompecabezas) tendrá complejidades similares, y el Número de Dios no es la única propiedad sobre estos acertijos que puede preguntar fácilmente, pero luego no obtendrá una respuesta oportuna. Ha mejorado con la velocidad de las computadoras aumentando rápidamente y la capacidad de ejecutar cuadrículas con viabilidad económica, pero aún así requirió meses de trabajo para que los investigadores optimizaran su código a mano para prepararse para esas búsquedas de fuerza bruta.

Dada una posición arbitraria de 3x3x3, una computadora puede encontrar el camino óptimo para la solución utilizando el “Algoritmo de Dios” en quizás noventa segundos de tiempo de búsqueda en un Intel i7, pero encontrar este valor para TODAS las posibles posiciones es lo que requiere ese tiempo de computación.

Esto se debe en parte a nuestro enfoque de diseño en programación secuencial y paradigmas de hardware. Nuestra elección de lenguajes de computación no necesariamente se paraleliza automáticamente muy bien sin que el programador explique cómo debe ocurrir la paralelización. Con lenguajes más orientados en paralelo que no dependen únicamente de subprocesos múltiples y semáforos, se pueden ver algoritmos paralelos más cooperativos.

Creo que la solución será crear lenguajes de programación que se compilen tan fácilmente en silicio (FPGA y otros) como compilar en uno o más procesadores secuenciales o GPU. Eso está muy lejos, pero creo hacia dónde debemos dirigirnos para reducir el procesamiento combinatorio en las próximas décadas.

ACTUALIZACIÓN: Recientemente he estado explorando el entorno de desarrollo CλaSH para el lenguaje funcional Haskell (ver clash-lang.org). Haskell se puede utilizar para expresar programas altamente matemáticos de manera concisa, con un modelo de ejecución interesante para procesadores secuenciales que se basa en una evaluación diferida, entre otras cosas. Lo que proporciona la biblioteca CλaSH es una forma de expresar los programas Haskell que se pueden compilar en silicio. Si bien este entorno no es perfecto, y lo que existe en este momento es algo así como un prototipo, puedo apreciar cómo se puede usar para acelerar el desarrollo de dispositivos FPGA.

Una computadora puede verificar “fácilmente” una prueba formal en cualquier sistema Hilbert de primer orden (es decir, matemática ordinaria), ya que el problema de decisión de k-probabilidad para tales sistemas está en NP (-completo). Si alguna vez se encuentra un algoritmo “rápido” para problemas NP-completos (esto está relacionado con un problema abierto conocido como “P versus NP”), entonces será “fácil” para una computadora encontrar una prueba, siempre que la prueba existe y se da / adivina un límite superior factible de su longitud (una prueba es una cadena finita).

Tenga en cuenta que una “prueba” no es solo como decir “prueba de la conjetura de Goldbach”, sino también una prueba de una declaración como esta:

existe un número real x tal que [matemática] x ^ 2 + 5x + 1 = 0 [/ matemática].

Una gran cantidad de declaraciones como las anteriores pueden ser probadas (o refutadas) por una computadora. Compruebe, por ejemplo, Wolfram | Alpha Pro: solucionador matemático paso a paso.

Observe también que una computadora moderna es una máquina universal de Turing y las máquinas de Turing son matemáticas. Por lo tanto, una computadora es matemática misma. La autorreferencia matemática siempre lleva las cosas al límite.

Las computadoras pueden hacer prácticamente todos los cálculos matemáticos. ¿Pero cómo?

El hardware de la computadora puede sumar, restar, multiplicar, dividir y varias operaciones lógicas básicas. Pero eso es todo.

Todo el resto de las matemáticas se puede lograr con algoritmos que utilizan esos cálculos básicos de hardware.

El análisis numérico es el estudio de cómo hacerlo.

Bueno, la mayor parte de las matemáticas de nivel superior implica probar cosas, y en su mayor parte, las computadoras no pueden probar cosas. Una computadora solo puede hacer cosas que en cierto sentido son sencillas y pueden describirse mediante una fórmula (o algo así como una fórmula). Probar teoremas requiere ingenio y rara vez es sencillo, por lo que es muy difícil enseñar a una computadora a crear pruebas. Sin embargo, más recientemente, han comenzado a enseñar a las computadoras a probar cosas en campos como la teoría de números donde las reglas pueden definirse más fácilmente. Sin embargo, las pruebas proporcionadas por las computadoras a menudo son innecesariamente largas y poco intuitivas.

Las computadoras no pueden calcular raíces cuadradas de números negativos. Sin embargo, lo que hacen es fingir que pueden calcular dichos valores mediante el uso de excepciones.

Existen algoritmos que usan las computadoras para calcular raíces cuadradas, como el Método Babilónico.

Si usa un número negativo como el operando del Método Babilónico, el programa se ejecutará para siempre.

Esto se debe a que el algoritmo es inútil con números negativos, lo que significa que siempre generará otro número negativo, y no hay una solución real para las raíces cuadradas de números negativos.

Aquí está el código de Python para el Método Babilónico:

x = flotante (input ())
k = 1
q = (x / 2 + 2 / (x / 2)) / 2
mientras q ** 2! = x y k <= 16:
d = x / q
q = (d + q) / 2
k + = 1
imprimir (q)

Si pensamos que las matemáticas son toneladas y toneladas de cálculos aburridos, las computadoras pueden hacer la mayor parte de eso. Al menos enseñamos a las computadoras a hacer eso. A veces aprendemos que las computadoras están cometiendo errores o más bien nos malinterpretan en lugares más o menos importantes y les enseñamos a calcular correctamente. Sin embargo, si pensamos que las matemáticas son esta increíble capacidad para ver patrones, verifique eso, invente un nuevo patrón y descríbalo, cree algo hermoso y juegue con eso … Me temo que las computadoras no son de gran ayuda en esto. zona.

Prueba el factorial de 100.