Votación impar: aceleramos autómatas cambiando la regla ✛ ✎

Al tribunal entra una palabra: una cadena de letras. Doce jurados, cada uno de ellos un camino computacional, recorren las letras y deciden: «aceptar» o «rechazar». En un autómata no determinista habitual, le basta a la palabra con un solo voto a favor. Pero existe un tribunal extraño donde el veredicto depende del número total de votos: si un número impar de jurados votó «a favor», la palabra se considera aceptada. Esta regla cambió todo el funcionamiento.

¿Por qué acelera esto los cálculos? Un autómata normal usa la lógica «o»: o hay un camino o no lo hay. Aquí funciona la aritmética de residuos: cada camino es 0 o 1, y el resultado global es su suma módulo 2, es decir, una simple O exclusiva (suma sin acarreo). Esta aritmética permite aplicar métodos algebraicos rápidos y en lugar de seguir todos los caminos, solo vigilar cuántos hay en cada estado. Para autómatas donde una palabra tiene a lo sumo k caminos, se ha desarrollado un ingenioso método para procesar cada símbolo en un número de pasos proporcional a k y al tamaño del autómata.

Lo más sorprendente: se puede convertir un autómata normal en un conjunto de varios no convencionales. Usando coeficientes aleatorios y la aritmética de residuos, se crea un ensamble, y si el autómata original aceptaba la palabra, al menos uno de los nuevos producirá un resultado impar con probabilidad mayor que la mitad. Recuerda a un juego de adivinanzas: en lugar de un juez fiable, se toma un equipo de excéntricos, pero juntos no se equivocan.

En definitiva, la propia estructura del autómata sugiere cómo acelerar los cálculos. La ambigüedad aleatoria de los caminos, que antes molestaba, se convierte en una aliada. Y si los científicos demuestran que no se puede hacer aún más rápido, tendrán que refutar otra hipótesis, no demostrada. El tribunal de votos impares no es un mero pasatiempo: es la clave de la frontera entre los cálculos rápidos y los ultrarrápidos.