A bomba era rápida, mas não o bastante para testar todas as ordens de rotores da Enigma naval. Em 1940, Turing inventou um método de lápis e papel para descartar a maioria delas antes de ligar as máquinas. Como as folhas usadas no método eram impressas na cidade de Banbury, os colegas o batizaram de banburismo.

O método é estatístico. E, para fazê-lo, Turing reinventou uma das ideias centrais da estatística moderna.

Letras que se repetem

Escreva duas mensagens em alemão, uma embaixo da outra, e conte as casas em que as duas têm a mesma letra. Como o alemão usa muito o E, o N, o R e o I, as coincidências são bem mais frequentes do que se as letras fossem sorteadas. Em texto alemão, a chance de duas letras alinhadas coincidirem fica em torno de $\frac1{17}$; com letras ao acaso, seria $\frac1{26}$.

A Enigma preserva essa propriedade de um jeito curioso: se duas mensagens foram cifradas com a mesma sequência de posições dos rotores, as coincidências do texto original continuam sendo coincidências no texto cifrado, porque letras iguais na mesma posição viram letras iguais. Se as posições forem diferentes, a taxa cai para $\frac1{26}$. Contar coincidências, portanto, dá um indício de que duas mensagens estão alinhadas, e isso revelava informação sobre as posições dos rotores.

Quanto vale uma coincidência

Turing perguntou: quanto uma única coincidência deve aumentar a minha confiança de que as mensagens estão alinhadas? A resposta é a razão de verossimilhança, quantas vezes mais provável é ver uma coincidência num caso do que no outro:

$$\frac{\text{chance da coincidência se alinhadas}}{\text{chance se não alinhadas}}=\frac{1/17}{1/26}=\frac{26}{17}\approx1{,}53.$$

Uma casa sem coincidência é um indício na direção contrária, bem mais fraco:

$$\frac{16/17}{25/26}=\frac{416}{425}\approx0{,}979.$$

Pelo teorema de Bayes, cada indício multiplica as chances (a razão entre a probabilidade de uma hipótese e a da outra) pela sua razão de verossimilhança. Com muitas casas, são muitas multiplicações, e multiplicar à mão é lento.

Somar em vez de multiplicar

Turing fez o que Napier tinha feito três séculos antes: passou aos logaritmos, para trocar multiplicações por somas. Chamou de ban o logaritmo decimal de uma razão de verossimilhança, e de deciban a décima parte dele:

$$\text{peso em decibans}=10\log_{10}(\text{razão de verossimilhança}).$$

Agora cada coincidência vale

$$10\log_{10}\frac{26}{17}\approx+1{,}8\ \text{deciban},$$

e cada casa sem coincidência vale

$$10\log_{10}\frac{416}{425}\approx-0{,}09\ \text{deciban}.$$

Os operadores do Barracão 8 só precisavam contar e somar. Um total de $+20$ decibans significa que os indícios tornaram a hipótese $10^2=100$ vezes mais provável, em termos de chances, do que era antes.

Exercício: some os indícios

Duas mensagens alinhadas em 200 casas têm 14 coincidências. Qual é o peso total em decibans? A hipótese do alinhamento ficou mais provável?

São 14 coincidências e 186 casas sem coincidência: $14\cdot1{,}8+186\cdot(-0{,}09)\approx25{,}2-16{,}7=8{,}5$ decibans. Positivo: as chances a favor do alinhamento foram multiplicadas por cerca de $10^{0{,}85}\approx7$. Com letras ao acaso, o esperado seriam $200/26\approx7{,}7$ coincidências; com alinhamento, $200/17\approx11{,}8$. Catorze é mais compatível com o alinhamento.

Exercício: quantas coincidências empatam?

Em 100 casas, quantas coincidências $k$ dão peso total zero?

$1{,}8k-0{,}09(100-k)=0$, ou seja, $1{,}89k=9$, e $k\approx4{,}8$. Com 5 coincidências ou mais em 100 casas, o indício já pende para o alinhamento. É um número entre o esperado ao acaso, $100/26\approx3{,}8$, e o esperado com alinhamento, $100/17\approx5{,}9$.

Fontes: I. J. Good, “Studies in the history of probability and statistics XXXVII: A. M. Turing’s statistical work in World War II”, Biometrika (1979) · Andrew Hodges, Alan Turing: The Enigma (1983) · Sharon Bertsch McGrayne, The Theory That Would Not Die (2011).

Todos os tópicos de Alan Turing · ← A Enigma: 159 quintilhões de chaves e um defeito · O jogo da imitação: uma máquina pode pensar? →

Créditos das imagens.