William Thomas Tutte (14 de mayo de 1917 - 2 de mayo de 2002) fue un descifrador de códigos y matemático inglés y canadiense. Durante la Segunda Guerra Mundial, hizo un avance brillante y fundamental en el criptoanálisis del cifrado de Lorenz, un importante sistema de encriptación de la Alemania nazi que se utilizó para comunicaciones de alto secreto dentro del Alto Mando de la Wehrmacht. La naturaleza estratégica de la información de alto nivel obtenida a partir del avance crucial de Tutte, específicamente en el descifrado masivo de los mensajes codificados con el sistema de Lorenz, contribuyó en gran medida, y quizás incluso de manera decisiva, a la derrota de la Alemania nazi.[1][2] También obtuvo resultados matemáticos significativos, incluido el trabajo de base en los campos de la teoría de grafos y la de matroides.[3][4]
W. T. Tutte | ||
---|---|---|
Información personal | ||
Nombre en inglés | William Thomas Tutte | |
Nacimiento |
14 de mayo de 1917 Newmarket (Reino Unido) | |
Fallecimiento |
2 de mayo de 2002 Waterloo (Canadá) | (84 años)|
Sepultura | West Montrose United Church Cemetery | |
Nacionalidad | Británica y canadiense | |
Educación | ||
Educado en |
| |
Supervisor doctoral | Shaun Wylie | |
Información profesional | ||
Ocupación | Matemático, profesor universitario y criptólogo | |
Área | Combinatoria, teoría de grafos, criptografía y Fish | |
Empleador |
| |
Obras notables | ||
Conflictos | Segunda Guerra Mundial | |
Miembro de | ||
Distinciones |
| |
La investigación de Tutte en el campo de la teoría de grafos demostró ser de notable importancia. En un momento en que esta disciplina era todavía un tema incipiente, comenzó el estudio de los matroides y los convirtió en una teoría ampliando el trabajo que Hassler Whitney había desarrollado por primera vez a mediados de la década de 1930.[5] Aunque las contribuciones de Tutte han influido en la teoría de grafos moderna y muchos de sus teoremas se han utilizado para seguir avanzando en el campo, la mayor parte de su terminología no estaba de acuerdo con su uso convencional y, por lo tanto, no es utilizada por los teóricos de grafos en la actualidad.[6] "Tutte hizo avanzar la teoría de grafos a partir de un tema contenido en un único texto (el de D. Kőnig) hacia su estado actual trabajando de forma extremadamente activa".[6]
Tutte nació en Newmarket, en Suffolk. Era el último hijo de William John Tutte (1873-1944), jardinero, y de la ama de llaves Annie Newell (1881-1956). Ambos padres trabajaban en la propiedad de los establos de Fitzroy House, donde Tutte nació.[4] La familia pasó algún tiempo en Buckinghamshire, el Condado de Durham y Yorkshire antes de regresar a Newmarket, donde asistió en la localidad de Cheveley a una escuela primaria regida por la Iglesia de Inglaterra.[3] En 1927, con diez años de edad, obtuvo una beca para asistir a la Escuela secundaria para niños de Cambridge y su Condado, donde ingresó en 1928.
En 1935 ganó una beca para estudiar ciencias naturales en el Trinity College de Cambridge, donde se especializó en química y se graduó con honores de primera clase en 1938.[3] Continuó con la química física como estudiante graduado, pero se decidió por el estudio de las matemáticas a finales de 1940.[3] Como estudiante, junto con tres de sus amigos, se convirtió en uno de los primeros en resolver el problema de la cuadratura del cuadrado y el primero en resolver el problema sin un subrectángulo cuadrado. Juntos, los cuatro crearon el seudónimo de Blanche Descartes, bajo el que Tutte publicó ocasionalmente algunos de sus trabajos durante años.[7]
Número de rueda | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
Nombre de la rueda en Bletchley Park[8] | 37 | 61 | ||||||||||
Número de levas (pasadores) | 43 | 47 | 51 | 53 | 59 | 37 | 61 | 41 | 31 | 29 | 26 | 23 |
Poco después del estallido de la Segunda Guerra Mundial, el tutor de Tutte, Patrick Duff, lo recomendó para trabajar durante la guerra en Escuela de Códigos y Cifrados del Gobierno en Bletchley Park (BP). Fue entrevistado y enviado a un curso de capacitación en Londres antes de ir a Bletchley Park, donde se unió a la Sección de Investigación. Al principio, trabajó en el cifrado Hagelin, que estaba siendo utilizado por la Marina italiana. Esta era una máquina de cifrado de rotores que estaba disponible comercialmente, por lo que se conocía la mecánica del cifrado, y para descifrar los mensajes solo requería averiguar cómo estaba configurada la máquina.[9]
En el verano de 1941 fue transferido para trabajar en un proyecto llamado Fish. La información de inteligencia había revelado que los alemanes llamaron a los sistemas de transmisión mediante teleimpresoras inalámbricas "Sägefisch" (pez sierra). Esto llevó a los británicos a denominar Fish al sistema de cifrado alemán. El apodo Tunny (atún) se usó para el primer sistema de enlace que no empleaba el código Morse, y posteriormente se usó para las máquinas Lorenz SZ y para las comunicaciones que cifraban.[10]
Las comunicaciones telegráficas utilizaban el Alfabeto Telegráfico Internacional n.º 2 (ITA2) de 5 bits. No se sabía nada sobre el mecanismo de cifrado, aparte de que los mensajes estaban precedidos por un indicador de 12 letras, lo que implicaba una máquina de cifrado de rotor de 12 ruedas. El primer paso, por lo tanto, tenía que ser diagnosticar la máquina estableciendo la estructura lógica y por lo tanto su funcionamiento. Tutte desempeñó un papel fundamental en este logro, y no fue hasta poco antes de la victoria aliada en Europa en 1945 cuando Bletchley Park pudo disponer de una máquina de cifrado Tunny Lorenz.[11] Los avances de Tutte llevaron finalmente al descifrado masivo de mensajes cifrados con el sistema Tunny entre el Alto Mando Alemán (OKW) en Berlín y sus mandos militares en toda la Europa ocupada y contribuyeron, quizás de manera decisiva, a la derrota de Alemania.[1][2]
El 31 de agosto de 1941 se enviaron dos versiones del mismo mensaje utilizando claves idénticas, lo que constituía una situación de vulnerabilidad denominada en criptografía "profundidad". Esto permitió a John Tiltman, el veterano y notablemente talentoso criptoanalista de Bletchley Park, deducir que se trataba de un cifrado de Vernam, que usa la función disyunción exclusiva (XOR) (simbolizada por "⊕"), y extraer los dos mensajes y, por lo tanto, obtener la clave de oscurecimiento. Después de un período infructuoso durante el cual los criptoanalistas de la Sección de Investigación intentaron averiguar cómo funcionaba la máquina Tunny, esta y algunas otras claves fueron entregadas a Tutte, a quien se le pidió que "viera qué podía hacer con ellas".[12]
En su curso de capacitación, a Tutte se le había enseñado la técnica del examen de Kasiski, consistente en escribir una clave en papel cuadriculado, comenzando una nueva fila después de un número definido de caracteres que se sospechaba que era la frecuencia de repetición de la clave.[13] Si este número era correcto, las columnas de la matriz mostrarían más repeticiones de secuencias de caracteres que el azar por sí solo. Tutte sabía que los indicadores de la máquina Tunny usaban 25 letras (excluyendo la J) para 11 de las posiciones, pero solo 23 letras para la otra. Por lo tanto, probó la técnica de Kasiski en el primer impulso de los caracteres clave, utilizando una repetición de 25 × 23 = 575. No observó un gran número de repeticiones de columna con este período, pero sí observó el fenómeno en diagonal. Por lo tanto, volvió a intentarlo con 574, que mostró repeticiones en las columnas. Reconociendo que los factores primos de este número son 2, 7 y 41, lo intentó de nuevo con un período de 41 y "obtuvo un rectángulo de puntos y cruces que estaba repleto de repeticiones".[14]
Estaba claro, sin embargo, que el primer impulso de la tecla era más complicado que el producido por una sola rueda de 41 impulsos de tecla. Tutte llamó a este componente de la clave (chi1). Supuso que había otro componente, que aplicaba una disyunción exclusiva, que no siempre cambiaba con cada nuevo carácter, y que este era el producto de una rueda que llamó (psi1). Lo mismo se aplicó para cada uno de los cinco impulsos ( and ). Entonces, para un solo carácter, la clave K completa constaba de dos componentes: En Bletchley Park, los impulsos de marca se representaban con x y los impulsos de espacio con • .[nota 1] Por ejemplo, la letra "H" se codificaría como ••x•x.[15] La deducción de Tutte de los componentes chi y psi fue posible por el hecho de que era más probable que los puntos fueran seguidos por puntos, y que las cruces tenían más probabilidades de ser seguidas por cruces. Esto fue producto de una debilidad en la configuración de clave alemana, que luego eliminaron. Una vez que Tutte hizo este avance, el resto de la Sección de Investigación se unió para estudiar los otros impulsos, y se estableció que las cinco ruedas chi avanzaban con cada nuevo carácter y que las cinco ruedas psi se movían juntas bajo el control de dos ruedas mu o "motor". Durante los siguientes dos meses, Tutte y otros miembros de la Sección de Investigación trabajaron en la estructura lógica completa de la máquina, con su conjunto de ruedas con levas que podrían estar en una posición (elevada) que agregaba una x al flujo de caracteres del teclado, o en la posición alternativa que se agregaba en •.[16]
Deducir el funcionamiento de la máquina Tunny de esta manera fue un logro criptoanalítico verdaderamente notable que, en la mención del nombramiento de Tutte como Oficial de la Orden de Canadá, se describió como "una de las mayores hazañas intelectuales de la Segunda Guerra Mundial".[4]
Para descifrar un mensaje de Tunny se requería conocimiento no solo del funcionamiento lógico de la máquina, sino también de las posiciones de inicio de cada rotor para el mensaje en particular. Se estaba buscando un proceso que manipulara el texto cifrado o la clave para producir una distribución de frecuencia de caracteres que se apartara de la uniformidad que el proceso de cifrado pretendía lograr. Mientras estaba adscrito a la Sección de Investigación en julio de 1942, Alan Turing descubrió que la combinación XOR de los valores de caracteres sucesivos en un flujo de texto cifrado y clave enfatizaba cualquier desviación de una distribución uniforme. La corriente resultante (simbolizada por la letra griega "delta" Δ) se denominó diferencia porque XOR es lo mismo que la resta de módulo 2.
La razón por la que esto proporcionó una forma de acceder a Tunny fue que, aunque la distribución de frecuencia de los caracteres en el texto cifrado no podía distinguirse de un flujo aleatorio, no ocurría lo mismo con una versión del texto cifrado a partir de la cual se había extraído el elemento chi de la clave. Este fue el caso porque donde el texto sin formato contenía un carácter repetido y las ruedas psi no se habían movido, el carácter psi diferenciado ( ) sería el carácter nulo (' / ' en Bletchley Park). Cuando se usa XOR con cualquier carácter, este carácter no tiene efecto. Los caracteres repetidos en el texto sin formato eran más frecuentes debido a las características del alemán (los pares de letras repetidas EE, TT, LL y SS son relativamente comunes),[17] y porque los telegrafistas repetían con frecuencia los caracteres de cambio de cifras y letras,[18] dado que su pérdida en un mensaje telegráfico ordinario podría dar lugar a un galimatías.[19]
Citando el Informe General sobre Tunny:
Turing introdujo el principio de que la clave diferenciada en uno, ahora llamada ΔΚ, podría generar información que no se puede obtener de la clave ordinaria. Este principio Δ iba a ser la base fundamental de casi todos los métodos estadísticos de desvelado y ajuste de ruedas.[8]
Tutte aprovechó esta amplificación de la falta de uniformidad en los valores diferenciados [nota 2] y en noviembre de 1942 había hallado una forma de descubrir los puntos de partida de las ruedas de la máquina Tunny que se conoció como el "Método estadístico".[20] La esencia de este método era encontrar la configuración inicial del componente chi de la clave probando exhaustivamente todas las posiciones de su combinación con el texto cifrado y buscando evidencia de la falta de uniformidad que reflejaba las características del texto original sin formato.[21][22] Debido a que cualquier carácter repetido en el texto sin formato siempre generaría •, y de manera similar generaría • cada vez que las ruedas psi no se movieran, y aproximadamente la mitad de las veces cuando lo hicieran, lo que suponía alrededor del 70% en general.
Además de aplicar la diferenciación a los caracteres completos de 5 bits del código ITA2, Tutte la aplicó a los impulsos individuales (bits).[nota 3] Es necesario establecer la configuración actual de la leva de la rueda chi para permitir que se genere la secuencia relevante de caracteres de las ruedas chi. Era totalmente impracticable generar los 22 millones de caracteres de las cinco ruedas chi, por lo que inicialmente se limitó a 41 × 31 = 1271 de las dos primeras. Después de explicar sus hallazgos a Max Newman, este último recibió el trabajo de desarrollar un enfoque automatizado para comparar el texto cifrado y la clave con el fin de buscar desviaciones de la aleatoriedad. La primera máquina se denominó Heath Robinson, pero la computadora Colossus, mucho más rápida, desarrollada por Tommy Flowers y usando algoritmos escritos por Tutte y sus colegas, pronto se hizo cargo de descifrar los códigos.[23][24][25]
A finales de 1945, Tutte reanudó sus estudios en Cambridge, ahora como estudiante graduado en matemáticas. Publicó algunos trabajos que había comenzado mucho antes, uno ahora famoso que caracteriza qué grafos tienen una coincidencia perfecta y otro que construye un grafo no hamiltoniano.
Completó su doctorado en matemáticas por la Universidad de Cambridge en 1948 bajo la supervisión de Shaun Wylie, quien también había trabajado en Bletchley Park en la máquina Tunny. Su tesis An Algebraic Theory of Graphs se consideró innovadora y trataba sobre el tema conocido más tarde como teoría de matroides.[26]
El mismo año, invitado por Harold Scott MacDonald Coxeter, aceptó un puesto en la Universidad de Toronto. En 1962, se trasladó a la Universidad de Waterloo en Waterloo, Ontario, donde permaneció el resto de su carrera académica. Se retiró oficialmente en 1985, pero permaneció activo como profesor emérito. Tutte fue fundamental para ayudar a fundar el Departamento de Combinatoria y Optimización en la Universidad de Waterloo.
Su carrera matemática se concentró en la combinatoria, especialmente la teoría de grafos, campo en el que se le atribuye haber ayudado a crear su forma moderna, y la teoría de matroides, a la que hizo profundas contribuciones. Un colega lo describió como "el matemático líder en combinatoria durante tres décadas". Fue editor en jefe del Journal of Combinatorial Theory hasta que se retiró de Waterloo en 1985.[26] También formó parte de los consejos editoriales de varias otras revistas de investigación matemática.
El trabajo de Tutte en teoría de grafos incluye la estructura de espacios de ciclos y de corte, el tamaño de las coincidencias máximas y la existencia de k-factores en grafos, y grafos hamiltonianos y no hamiltonianos.[26] Refutó la conjetura de Tait, sobre la hamiltonicidad de los grafos poliédricos, utilizando la construcción conocida como fragmento de Tutte. La prueba final del teorema de los cuatro colores hizo uso de su trabajo anterior. El polinomio gráfico que llamó "dicromato" se ha vuelto famoso e influyente con el nombre de polinomio de Tutte y sirve como prototipo de invariantes combinatorios que son universales para todos los invariantes que satisfacen una ley de reducción específica.
Realizó los primeros avances importantes en la teoría de matroides en su tesis doctoral de Cambridge de 1948, que formó la base de una importante secuencia de artículos publicados durante las siguientes dos décadas. El trabajo de Tutte en teoría de grafos y teoría de matroides ha tenido una profunda influencia en el desarrollo tanto del contenido como de la dirección de estos dos campos.[6] En la teoría de matroides, descubrió el altamente sofisticado teorema de la homotopía y fundó los estudios de grupos de cadenas y matroides regulares, sobre los que demostró profundos resultados.
Además, desarrolló un algoritmo para determinar si un matroide binario determinado es un matroide gráfico. El algoritmo hace uso del hecho de que un grafo plano es simplemente un grafo cuyo circuito-matroide, el dual de su enlace-matroide, es gráfico.[27]
Tutte escribió un artículo titulado Cómo dibujar un grafo en el que demostró que cualquier cara en un grafo de 3 conexiones está encerrada por un ciclo periférico. Usando este hecho, desarrolló una prueba alternativa para mostrar que cada gráfico de Kuratowski no es plano al demostrar que K5 y K3,3 tienen cada uno tres ciclos periféricos distintos con una arista común. Además de usar ciclos periféricos para demostrar que los gráficos de Kuratowski no son planos, también demostró que cada grafo simple de 3 conexiones se puede dibujar con todas sus caras convexas e ideó un algoritmo que construye el dibujo del plano resolviendo un sistema lineal. El dibujo resultante se conoce como embebido de Tutte. El algoritmo de Tutte hace uso de las asignaciones baricéntricas de los circuitos periféricos de un grafo simple de 3 conexiones.[28]
Los hallazgos publicados en este documento han demostrado ser de gran importancia porque los algoritmos que desarrolló Tutte se han convertido en métodos populares de dibujo de gráficos planos. Una de las razones por las que el embebido de Tutte es popular es que los cálculos necesarios que realizan sus algoritmos son simples y garantizan una correspondencia uno a uno de un grafo y su embebido en el plano euclídeo, lo que es importante al parametrizar una malla tridimensional al plano en el modelado geométrico. "El teorema de Tutte es la base para las soluciones de otros problemas de grafos por computadora, como las secuencias de imágenes".[29]
Fue el principal responsable de desarrollar la teoría de la enumeración de grafos planos, que tiene estrechos vínculos con los polinomios cromáticos y dicromáticos. Este trabajo involucró algunas técnicas altamente innovadoras de su propia invención, que requerían una destreza de manipulación considerable en el manejo de series de potencias (cuyos coeficientes cuentan tipos de grafos apropiados) y las funciones que surgen como sus sumas, así como destreza geométrica para extraer estas series de potencias de la situación teórica de los grafos.[30]
Tutte resumió su trabajo en Selected Papers of WT Tutte, 1979, y en Graph Theory as I have know it, 1998.[26]
El trabajo de Tutte en la Segunda Guerra Mundial y posteriormente en combinatoria le valió varios puestos, honores y premios:
También desempeñó el cargo de bibliotecario de la Real Sociedad Astronómica de Canadá en 1959-1960. El asteroide 14989 Tutte (1997 UB7) recibió su nombre.[35]
Debido al trabajo de Tutte en Bletchley Park, el Establecimiento de Seguridad de las Comunicaciones de Canadá nombró una organización interna destinada a promover la investigación en criptología, el Instituto Tutte de Matemáticas y Computación (TIMC), en su honor en 2011.[36]
En septiembre de 2014 recibió un homenaje en su ciudad natal de Newmarket, Inglaterra, con la inauguración de una escultura, después de que un periódico local iniciara una campaña para honrar su memoria.[37]
Bletchley Park en Milton Keynes celebró el trabajo de Tutte con una exposición Bill Tutte: Mathematician + Codebreaker de mayo de 2017 a 2019, precedida el 14 de mayo de 2017 por conferencias sobre su vida y obra durante el Simposio del Centenario de Bill Tutte.[38][39]
Además de los beneficios profesionales de trabajar en la nueva Universidad de Waterloo, el entorno más rural del condado de Waterloo atrajo a Bill y su esposa Dorothea. Compraron una casa en el pueblo cercano de West Montrose, Ontario, donde disfrutaron de caminatas, pasaron tiempo en su jardín en el Grand River y permitieron que otros disfrutaran del hermoso paisaje de su propiedad.
También tenían un amplio conocimiento de todas las aves de su jardín. Dorothea, una activa alfarera, también era una gran excursionista y Bill organizaba excursiones de senderismo. Incluso cerca del final de su vida, todavía era un asiduo caminante.[6][40] Después de la muerte de su esposa en 1994, se mudó de nuevo a Newmarket (Suffolk), pero luego regresó a Waterloo en 2000, donde murió dos años después.[41] Está enterrado en el cementerio West Montrose United.[26]