Grosso modo, una Máquina de Turing no es más que una modelización de la computación manual. Esquemáticamente, consiste en una cinta dividida en celdas y una cabeza lectora/escritora que sólo puede realizar una acción en una sola celda por vez.
Pensemos en un algoritmo simple: dado un natural, calcular el siguiente. Operando en binario, todo se reduce a fijar una corta serie de normas sobre cambios entre ceros y unos en función de sus adyacentes, por lo que evidentemente el tiempo que tarde el algoritmo en resolver el problema dependerá de la longitud de la inscripción inicial. Si llamamos n a esa longitud, podemos definir T(n) como el tiempo que tarda en resolver el problema una Máquina de Turing arrancada con una inscripción de tamaño n. T(n) es una función discreta, que se puede intentar acotar mediante una O grande g real.
Si conseguimos acotar el tiempo del algoritmo mediante una O grande que sea a su vez un polinomio real, decimos que es de tiempo polinómico; en caso contrario decimos que el algoritmo es tiempo exponencial. Dándole la vuelta, decimos que un problema es de tiempo polinómico si existe un algoritmo de tiempo polinómico que lo resuelve.
Un problema se dice de decisión si sólo admite dos respuestas. Por ejemplo, la primalidad: un número entero sólo puede ser primo o compuesto. Parece evidente pues llamar P a los problemas de decisión para los que existe un algoritmo de tiempo polinómico que los resuelve. De hecho, desde 2002 sabemos que Primes is in P.
Existe otro tipo de problemas un poco más enrevesados. Consiste en aquellos problemas de decisión para los cuales, si la respuesta es afirmativa, existe un conjunto de valores iniciales y un algoritmo en tiempo polinómico que los resuelve. Nótese la ligera diferencia: si la respuesta es sí y me dan unos datos, lo resuelvo eficientemente. Desde mucho antes de 2002 se sabía que la primalidad es de este tipo… pero haciendo trampa y llamándolo problema de factorización de enteros: dado un número compuesto, si sé es compuesto y tengo unos determinados datos (por ejemplo trivial, un factor) existe un algoritmo de tiempo polinómico que resuelve el problema de factorizarlo (otra cosa es que sea computacionalmente eficiente con las velocidades de las máquinas actuales). Este tipo de problemas se llaman NP (Non-Deterministic Polynomial-time).
La gran pregunta es, por supuesto, ¿P=NP?
No se preocupen, esto es sólo un divertimento… y una cuenta atrás.
Hoy voy a darle un toque divulgativo al blog. Sigo poniendo bonita mi casa, y esta vez presento el plugin WP-LaTeX, un genial invento que me va a ayudar a escribir de vez en cuando sobre Matemáticas. Ahora no sólo torturaré a mis compañeros de trabajo con explicaciones extrañas, sino a todos vosotros. Toca aguantarse.
Para empezar, tengo reservado algo que muchos no creerán. Es algo tan sabido y masticado, tan común, que cuesta creer que es mentira. De pequeños, nos repiten en la escuela que un número es primo siempre y cuando sólo pueda ser dividido por él mismo o por uno. Esa definición no es correcta.
Empecemos por el principio. Cuando hablamos de primalidad, de números primos, de ser dividido, nos centramos en un pequeño conjunto de puntos, de números. Normalmente no se nos ocurre que 7 no sea primo porque 7=2x(3,5), porque ese 3,5 es extraño, decimal, no entero. De eso se trata, de números enteros. Hablamos de división entera, de primalidad de números enteros.
El conjunto de los números enteros se denota por la grafía 
, una zeta mayúscula con doble barra interna. Todos los conjuntos de números tienen su letrita equivalente, todas decoradas con su doble barrita. El caso es que ese es un conjunto, como esos diagramas de Venn que se hacían en mis tiempos, y además de ser un conjunto tiene unas propiedades. Lo normal, conocido: se suman enteros, se restan, se multiplican, se dividen cuando se puede, el 1 es especial y el 0 también. Esas propiedades hacen que el conjunto sea algo más que un conjunto. A los matemáticos les encanta ordenar y clasificar cosas, y clasifican conjuntos según las operaciones que se permitan a sus elementos sin salirse del conjunto. El caso es que cae dentro de la calificación de anillo. Básicamente, un anillo es cualquier conjunto de cosas entre las cuales defines dos operaciones, a modo de suma y producto, y que se comporta más o menos como sabemos que se comportan los enteros, . A grosso modo, toscamente y de manera muy poco precisa ni elegante, eso es un anillo.
¿Qué tiene esto que ver con que un número primo no sea el que sólo se puede dividir entre el uno y sí mismo? Bueno, los anillos funcionan parecido a los números enteros, pero no exactamente igual. Hay anillos relacionados con (extensiones y esas cosas) donde el número 7 sí tiene dos factores, es decir, puede ser dividido por algo que no es ni 7 ni 1 y da resto cero. Pero eso no es lo importante. Lo que cuenta es cómo se define qué es un elemento primo en un anillo, y ver qué ha pasado con los números enteros.
Cuando en un anillo un elemento sólo puede ser dividido por sí mismo o una unidad (el equivalente del 1 en ), ese elemento recibe un título, pero no el de primo. Ése es un elemento maximal. Es maximal porque si imaginas un árbol compuesto por las ramificaciones de todos sus múltiplos, ves siempre que la raíz es algo indivisible, que a su vez no es múltiplo de nada.
En un anillo un elemento primo es el que, si divide a un producto, divide siempre a algún factor. Por ejemplo pensemos en el número 42 y en el número 7. 42=2×3x7, luego podemos expresar 42 como 2×21, 3×14 y 7×6, porque el orden no influye. Lo que quiere decir la definición anterior es que 7 es primo si divide a algún factor en todas las descomposiciones posibles en productos. 7 divide a 21, 7 divide a 14 y 7 divide a 7. Como 42 no se puede expresar de otra manera multiplicando cosas enteras, deducimos que 7 cumple esa condición para el 42. El problema es que la definición habla de «si divide a un producto», a cualquier producto. Claro, la cosa no es ir haciendo la prueba para todos los enteros (son infinitos, eso otro día), pero tampoco nos quedamos de brazos cruzados. Tenemos dos grandes herramientas.
Primero, la descomposición en factores primos. Ir sacando los factores de un número partiendo dede el 2, luego el 3 y subiendo por una lista de primos conocida (al menos, te acordarás de los primos menores de 20, ¿no?). El problema es que este método no es general y a los matemáticos les asusta afirmar cosas sin haberlas comprobado antes. Y claro, hay números muy pero que muy grandes, tanto que los mejores ordenadores del planeta no pueden factorizarlos. Y eso está genial, pues permite, entre otras cosas, el correo electrónico (más sobre criptografía, otro día).
Y llegamos a la segunda herramienta. En abstracto no hay número grande que valga, y en abstracto a los matemáticos nadie les gana. El punto fuerte es que existe una demostración de que, en el conjunto de los números enteros, los elementos maximales y los elementos primos son los mismos. En otros anillos no, pero sí en . Es decir, existe una conexión entre los elementos que, si dividen un producto, dividen un factor, y los elementos que no pueden ser divididos salvo por sí mismos y el 1. Si piensas en los primos como ladrillos de números, es más sencillo. Son la base de los demás números (divide a un producto, luego divide a un factor, luego es parte componente de otros números) y a la vez es el mínimo posible, la base, la pieza menor e indivisible.
La definición real de elemento primo no es operativa, pero sí la de maximal. El cambio es natural, y empezar ahora a revisar terminologías para cambiar primo por maximal es absurdo, incluso para un cascarrabias puntilloso como yo. Sin embargo, no deja de ser curioso.
