Python one-liners são Turing-complete

Quem programa em C há décadas normalmente não se dá conta de quão ilegíveis são as expressões mais comuns da linguagem. Quando eu era um garoto recém-saído do BASIC, eu lembro de ter me assustado com coisas básicas como for(i=0; i<10; i++). Mas isso é idiossincrasia do C, outras linguagens não sofrem disso, como o Python.

Python foi planejada para ser legível. Os programadores mais experientes citam o Zen of Python, que dita que "belo é melhor que feio", e "legibilidade conta". De fato, é até difícil escrever código ilegível em Python. Mas é claro que difícil não é impossível, e se o dr. Ian Malcolm fosse um programador, ele certamente diria que "obfuscation finds a way."

Aconteceu comigo semana passada: eu olhava alguns exercícios sobre listas para iniciantes, e notei que, embora eles fossem de fato muito simples, ficariam bem mais divertidos se eu tentasse resolvê-los usando apenas uma linha em cada. Abusando de programação funcional, eu consegui fazer os dez primeiros assim:

Soluções dos exercícios em uma linha de Python cada.

Depois de brincar algum tempo com one-liners, a pergunta que naturalmente se apresenta é: será que é possível fazer qualquer programa em uma linha de Python? A dificuldade vem do fato de que o Python diferencia statements de expressions, e você só pode ter um statement por linha. Em Python, statements incluem print, if, while, for e atribuições, ou seja, um one-liner só pode usar um único desses.

Então, colocando a pergunta de outra maneira: é possível demonstrar que um programa em Python com um único statement é Turing-complete? Existem dois caminhos pra demonstrar isso, o primeiro é construir um emulador para uma máquina de Turing universal em uma linha, o segundo é mostrar que é possível converter para uma linha de Python todos os programas possíveis de um sistema que seja Turing-complete, como o cálculo lambda, ou os tag-systems.

Eu resolvi abordar o problema com a filosofia Ricbit: se existem várias maneiras equivalentes de fazer alguma coisa, escolha a mais bizarra! Assim sendo, vou demonstrar que Python one-liners são Turing-complete através de redução ao Brainfuck (cuja universalidade já foi demonstrada várias vezes).

Vamos lá então: o estado de um programa em Brainfuck pode descrito em qualquer momento por uma quádrupla (mem, p, stdin, stdout), que são respectivamente a memória, o ponteiro, a entrada e saída. Vou implementar cada operação do Brainfuck como funções que recebem quádruplas e retornam quádruplas, descrevendo assim a transição de estado.

A operação mais simples é o ponto, que só adiciona o elemento apontado na saída:

dot = lambda mem, p, stdin, stdout: (mem, p, stdin, stdout+[mem[p]])

Para implementar a vírgula, eu preciso primeiro de alguma maneira de modificar um único elemento de uma lista. Se eu pudesse usar atribuições, bastaria algo do tipo mem[p]=value, mas como atribuições em Python são statements, preciso de uma função auxiliar. Além disso, eu preciso fazer o pop() do valor frontal da lista que guarda o stdin, o que me leva à outra auxiliar:

change = lambda mem, pos, value: [value if i==pos else a for i, a in enumerate(mem)]

get = lambda s: (s[0], s[1:]) if len(s) else (0,[])

comma = lambda mem, p, stdin, stdout: (lambda now, next: (change(mem, p, now), p, next, stdout))(*get(stdin))

Tendo a função change em mãos, fazer os comandos de mais e menos é simples:

plus = lambda mem, p, stdin, stdout: (change(mem, p, mem[p]+1), p, stdin, stdout)

minus = lambda mem, p, stdin, stdout: (change(mem, p, mem[p]-1), p, stdin, stdout)

Os comandos de esquerda e direita precisam tomar o cuidado de aumentar os limites da memória se necessário, a universalidade do Brainfuck requer uma fita infinita para os dois lados:

left = lambda mem, p, stdin, stdout: ([0]+mem if not p else mem, 0 if not p else p-1, stdin, stdout)

right = lambda mem, p, stdin, stdout: (mem+[0] if p==len(mem)-1 else mem, p+1, stdin, stdout)

Agora chegamos na parte complicada, que é o operador de loop. Como for e while são statements, e lambdas recursivos precisam de uma atribuição (fat = lambda x: 1 if x<=1 else x*fat(x-1)), então a única saída é apelar pra lazy evaluation, que no Python é implementada no módulo itertools. (Incluir o módulo itertools poderia tornar o programa um two-liner, mas felizmente é possível importar um módulo usando uma expression ao invés de um statement: a função __import__).

A solução para o operador de loop é criar uma lista infinita contendo [x, f(x), f(f(x)), f(f(f(x))), ...], onde cada f é uma aplicação do conteúdo do loop. Depois, para executar o loop, basta iterar nesta lista infinita, procurando o primeiro elemento onde o elemento apontado pelo ponteiro seja nulo. Precisamos então de uma função que calcule f^n e uma que gere a lista infinita:

composite = lambda f, n: lambda x: reduce(lambda a, b: b(*a), [f]*n, x)

infinite = lambda f, x: itertools.imap(lambda n: composite(f, n)(x), itertools.count(0))

Depois, basta criar um predicado que avalie quando o loop deve parar, e pegar o primeiro elemento da lista onde o predicado é verdadeiro:

predicate = lambda mem, p, stdin, stdout: mem[p] != 0

getfirst = lambda it: [i for i in itertools.islice(it, 1)][0]

loop = lambda f: lambda *x: getfirst(itertools.dropwhile(lambda x: predicate(*x), infinite(f,x)))

Tendo todos os comandos, só precisamos de uma função extra para encadeá-los, e depois, só para o programa não ficar grande demais, um shortcut que executa strings diretamente em Brainfuck:

chain = lambda f: lambda *x: reduce(lambda y, g: g(*y), f, x)

bf = {'+':plus, '-':minus, '.':dot, ',':comma, '<':left, '>':right}

run = lambda f: chain([bf[i] for i in f])

Feito! Agora é só fazer um script para parsear o Brainfuck original e gerar o one-liner. A título de ilustração, esse é o Hello World gerado pelo script:

print ''.join(chr(i) for i in ( (lambda itertools: (lambda change, get, chain, composite: (lambda comma, dot, plus, minus, left, right, infinite, predicate, getfirst: (lambda bf, loop: (lambda run: (chain ([run ("++++++++++"), loop (run ("<+++++++<" "++++++++++<" "+++<+>>>>-")), run ("<++.<" "+.+++++++..+++." "<++.>>" "+++++++++++++++" ".<.+++." "------.--------" ".<+.<.")])) ([0],0,[],[]) )( (lambda f: chain([bf[i] for i in f])) ) )( ({'+':plus, '-':minus, '.':dot, ',':comma, '<':left, '>':right}), (lambda f: lambda *x: getfirst(itertools.dropwhile(lambda x: predicate(*x), infinite(f,x)))) ) )( (lambda mem,p,stdin,stdout: (lambda now,next: (change(mem,p,now),p,next,stdout))(*get(stdin))), (lambda mem,p,stdin,stdout: (mem,p,stdin,stdout+[mem[p]])), (lambda mem,p,stdin,stdout: (change(mem,p,mem[p]+1),p,stdin,stdout)), (lambda mem,p,stdin,stdout: (change(mem,p,mem[p]-1),p,stdin,stdout)), (lambda mem,p,stdin,stdout: ([0]+mem if not p else mem, 0 if not p else p-1, stdin, stdout)), (lambda mem,p,stdin,stdout: (mem+[0] if p==len(mem)-1 else mem, p+1, stdin, stdout)), (lambda f,x: itertools.imap(lambda n: composite(f,n)(x), itertools.count(0))), (lambda mem,p,stdin,stdout: mem[p] != 0), (lambda it: [i for i in itertools.islice(it, 1)][0]) ) )( (lambda mem,pos,value: [value if i==pos else a for i,a in enumerate(mem)]), (lambda s: (s[0],s[1:]) if len(s) else (0,[])), (lambda f: lambda *x: reduce(lambda y,g: g(*y), f, x)), (lambda f,n: lambda x: reduce(lambda a,b:b(*a),[f]*n,x)) ) )(__import__("itertools")) )[3])

QED, em uma única linha, como prometido! (Eu não prometi que seria uma linha pequena :)

O script que converte de Brainfuck para Python one-liner está abaixo, para quem quiser brincar:

Conversor para Python one-liner.

Como nota final, vale lembrar que só porque você pode escrever qualquer coisa em uma linha, não significa que você deve fazer isso. Legibilidade conta :)

Potências ótimas

Olhando no Google Analytics, eu descobri que alguém chegou aqui no blog procurando por "como implementar em c++ potências". Se você é essa pessoa, a resposta está abaixo. Se você não é essa pessoa, puxe uma cadeira que o papo é divertido :)


Calcular potências aproximadas em ponto flutuante é trivial, basta incluir a biblioteca <cmath> e usar a função pow, que internamente é implementada como exp(y*log(x)). Mas existem várias aplicações onde você precisa do valor exato da potência, como, por exemplo, durante a criptografia RSA. Nesses casos, uma primeira abordagem pode ser como no código abaixo:

int natural(int x, int n) {
  int result = 1;
  for (int i = 1; i <= n; i++)
    result *= x;
  return result;
}


Esse código funciona, mas existem maneiras mais espertas. Nós, que temos dez dedos, não estamos acostumados a pensar em binário. Mas se fôssemos como os golfinhos, que tem um cérebro maior que o nosso e só duas barbatanas, poderíamos visualizar o expoente em binário e fazer um código assim:

int binary(int x, int n) {
  if (n == 0) return 1;
  if (n == 1) return x;

  int half = binary(x, n/2);
  if (n & 1)
    return half*half*x;
  else
    return half*half;
}

A versão original era O(n), essa é O(log n), uma melhoria significativa. Mas a melhor notícia sobre esse algoritmo é que você não precisa implementá-lo, ele já está pronto na biblioteca padrão do C++. Basta incluir <ext/numeric> e usar a função power. A função da STL ainda recebe como argumento opcional um functor de multiplicação, então você pode implementar com ela exponenciação modular, ou até mesmo potências de matrizes (ela funciona mesmo que sua multiplicação não seja comutativa).

Por outro lado, esse algoritmo é prático, mas não é ótimo. Em alguns casos, existem maneiras mais rápidas de calcular a potência, o primeiro caso onde isso acontece é para n¹⁵. O algoritmo binário precisa de seis multiplicações para resolver o problema, mas existem soluções com apenas cinco:



A melhor maneira de descrever as multiplicações necessárias para calcular uma potência é através de uma addition chain. Uma addition chain é uma espécie de generalização da seqüência de Fibonacci: enquanto no Fibonacci o próximo elemento é a soma dos dois imediatamente precedentes, numa addition chain o próximo elemento é a soma de dois anteriores quaisquer, ou até mesmo a soma de um elemento anterior com ele mesmo (com a restrição de que a seqüência precisa ser estritamente crescente).

Pela regra de formação dá pra perceber que, ao contrário da seqüência de Fibonacci, existem inúmeras addition chains. E melhor ainda, você pode associar uma addition chain com a seqüência de expoentes gerados no cálculo de uma potência. Para o exemplo de n=15 acima, as duas addition chains correspondentes são [1 2 3 6 7 14 15] e [1 2 4 5 10 15].

Achar uma seqüência ótima para calcular potências, então, é equivalente a achar uma addition chain de tamanho mínimo terminada no número que queremos. Infelizmente, eu tenho duas más notícias: o Erdös mostrou que a addition chain ótima não cresce mais lentamente que O(log n), então assintoticamente ela não é melhor que o método binário; e pior, o cálculo da addition chain ótima é NP-Completo. Abaixo eu implementei a addition chain ótima em C++ (usando brute force, então está bem lento):

Implementação da addition chain ótima em C++

É interessante também dar uma olhada nos casos onde o binário perde. No gráfico abaixo, a linha vermelha é o método binário, a linha azul é a addition chain ótima, e a linha verde é log₂n:


Olhando o gráfico, um golfinho certamente perceberia que o desvio do método binário é proporcional à quantidade de dígitos 1 na representação binária do expoente (os picos são em 63, 127, 255, e assim por diante). A demonstração disso é bem simples e está no Seminumerical Algorithms, junto com várias heurísticas para aproximar a addition chain ótima.

Ao Infinito e Além

O que há de comum entre Cantor, Gödel e Turing? Pelo menos duas coisas, e a primeira delas é que os três tentaram expandir os limites da matemática.

Cantor, por exemplo, queria contar até infinito. Essa é uma tarefa bem difícil: todos os que tentaram, cansaram antes de concluir! Mas o que o Cantor percebeu foi que, embora seja difícil contar diretamente, você pode contar até infinito indiretamente, desde que você saiba qual o significado real de "contar" alguma coisa.

O que significa, por exemplo, que você tem quatro maçãs? Na interpretação de Cantor, isso significa que você pode criar uma bijeção do seu conjunto de maçãs com um subconjunto dos números naturais, como na figura abaixo:

Se você criou uma bijeção do seu conjunto com o conjunto dos quatro primeiros naturais, então você efetivamente contou seu conjunto e concluiu que ele tem quatro elementos. O truque do Cantor foi perceber que você podia estender esse conceito, e criar bijeções com todos os naturais, ao invés de só algum subconjunto. E isso leva a resultados que são bem pouco intuitivos!

Por exemplo, o conjunto dos números pares. A intuição do iniciante é que esse conjunto tem a metade dos elementos dos naturais. Mas não é verdade, porque você pode construir uma bijeção entre os dois:


Para cada natural você tem um par correspondente, para cada par você tem um natural. Pelo raciocínio do Cantor, então esses dois conjuntos tem o mesmo número de elementos, o que também mostra que, pelo menos quando você está lidando com o infinito, a parte pode ser igual ao todo.

Indo além, o Cantor também mostrou que os Números Racionais também são do mesmo tamanho dos Naturais. Quem quiser repetir a demonstração original dele, pode tentar fazer o problema CANTON do spoj, que pede para você criar a bijeção. Uma maneira alternativa é utilizar uma construção inventada pelo Gödel: a cada racional p/q, você associa o natural 2^p3^q, e pra transformar o natural de volta numa racional, você usa a fatoração única que o Teorema Fundamental da Aritmética te garante.

Quando um conjunto tem o mesmo tamanho dos naturais, diz-se que ele tem cardinalidade aleph-zero, ou ainda, que é um conjunto contável. Mas todos os conjuntos infinitos são contáveis? Não! O Cantor também mostrou que o conjunto dos Números Reais é maior que qualquer conjunto contável dado, utilizando um método chamado argumento diagonal. Ou seja, os números reais são um tipo de infinito maior que o infinito dos naturais!

Agora, se os racionais são contáveis, e os reais não são, fica claro que os culpados por existir um infinito maior que o outro são os irracionais. Mas quais irracionais? Existem vários tipos deles também. Por exemplo, alguns irracionais podem ser construídos como raízes de polinômios de coeficientes inteiros (diz-se que esses são irracionais algébricos). Um exemplo é a razão áurea, que é a maior raiz do polinômio x²-x-1.

Porém, os irracionais algébricos são contáveis também. Basta utilizar novamente o mesmo truque do Gödel, dessa vez você associa cada coeficiente do polinômio a um expoente de um número primo. Um polinômio como x²+2x+1, por exemplo, escreveria-se como 2¹*3²*5¹.

Ora, se os irracionais algébricos são contáveis, então o que torna os reais maiores que os naturais são os irracionais não-algébricos (ou transcendentes). Mas mesmo entre esses existem vários tipos. O número Pi, por exemplo: você não consegue construí-lo como uma raiz de um polinômio, mas pode aproximá-lo com um algoritmo computacional, com tanta precisão quanto se queira. Dos números que podem ser aproximados por algoritmos, diz-se que são números computáveis.

Surpreendentemente, os irracionais computáveis são contáveis também. A maneira simples de visualizar isso é da seguinte maneira: se existe um algoritmo que aproxima o número, então esse algoritmo pode ser implementado numa linguagem qualquer (como nos garante a tese de Church-Turing). Agora, imagine que você criou um binário que implementou esse algoritmo, e esse binário tem X bytes. Se você fizer um hexdump do binario e imprimi-lo, você vai ter na sua frente um número hexa de 2X dígitos (que é um número natural grandinho, mas ainda assim um natural).

Mas se os irracionais computáveis são contáveis, quem são os não-contáveis? Existem números que não podem ser calculados por algoritmos? A resposta é sim, e um desses números é a constante de Chaitin. A construção da constante é curiosa. Nós vimos que, a cada algoritmo possível, existe um natural associado. Calcule então a seguinte somatória: para cada algoritmo existente (cujo natural associado é n), se o algoritmo pára, você soma 2^-n, senão não soma nada. Ora, essa somatória não pode ser calculada por um algoritmo, porque o Teorema de Turing garante que você não pode construir um algoritmo que detecta se outro algoritmo pára. A constante de Chaitin, então, é um número não-computável.

Mas os irracionais não-computáveis ainda não são o segredo do infinito real. Eu não consigo construir um algoritmo que aproxima a constante de Chaitin, mas no parágrafo acima eu consegui descrever exatamente do que a constante se trata. Os números que eu consigo descrever são números definíveis, e, (surpresa), eles são contáveis também. O argumento é ainda mais simples, se eu posso escrever um arquivo texto que contenha a descrição do número, o hexdump desse arquivo também vai associar a descrição a um número natural.

Então, os números que fazem o infinito dos reais ser maior que o infinito dos naturais são os números que não podemos construir, não podemos aproximar e não podemos descrever, ou seja, nem dá pra pensar sobre eles!

Se a essa altura sua cabeça deu tilt, então deixe-me concluir qual é a segunda coisa em comum entre Cantor, Gödel e Turing: os três ficaram doidos. De fato, Cantor achava que era um mensageiro de Deus, e terminou a vida num hospício. Gödel ficou paranóico com comida contaminada, e só comia o que a mulher preparava (quando a mulher ficou doente e internada num hospital, ele literalmente morreu de fome). E o Turing ficou tão deprimido que se matou, comendo uma maçã envenenada.

Há quem diga que existe relação causal entre estudar o infinito e ficar doido. Se você é desse tipo, hum, então era melhor não ter lido esse post :)

(Esse post é dedicado ao prof. Henrique, in memorian, líder do nosso grupo de doidos, que se reunia toda sexta na USP para estudar matemática, computação e ciências cognitivas. Três vivas aos que estudam o infinito, e além!)

All your game are belong to us

Quando eu ainda morava em São Paulo, todo ano eu ministrava uma das aulas da disciplina PSI-5015 da Poli, falando sobre a história dos videogames. Morando em Belo Horizonte, eu não tive como apresentar a palestra na Poli, mas eu usei o conteúdo para fazer uma Tech Talk no Google. Eu disponibilizei os slides abaixo, para quem não teve oportunidade de ver a palestra ao vivo:


É uma pena que em apenas uma hora não seja possível falar tanto quanto eu gostaria. Se tivesse mais tempo, eu ainda gostaria de citar o Time Traveler da Sega, por ser o primeiro a utilizar hologramas (na verdade, pseudo-hologramas), e também o Dance Dance Revolution e o GuitarFreaks da Konami, por iniciarem as manias de jogos de dança e jogos de guitarra, respectivamente.

Paranóia x Matemática

No último post eu falei sobre Criptografia, então agora, pra balancear, o tópico é Criptanálise. Semana passada, a polícia prendeu uma gangue que estava instalando os mini-notebooks Eee PC dentro de caixas automáticos, para roubar senhas dos usuários. O vídeo com a matéria pode ser visto abaixo:

Eu tenho certeza que um monte de gente deve ter visto a matéria e pensado "omfg nunca mais vou usar caixas automáticos kthxbye", mas na verdade, mesmo com o notebook lá dentro, não é tão fácil conseguir roubar a senha!

Se o seu banco for como o meu, você não digita a sua senha diretamente, ao invés disso, a máquina associa dois dígitos para cada botão, e você aperta os botões correspondentes à sua senha. Assim, se algum xereta estiver atrás de você olhando, ele não vai conseguir descobrir sua senha, e isso vale também se tiver um notebook dentro da máquina registrando o que você digita.

Então esse sistema é à prova de sniffers? Não! Um jeito de quebrar esse sistema é fazendo várias observações. Se o xereta te olhar uma única vez, ele não consegue descobrir sua senha, mas reduz bastante as possibilidades. Se a senha tiver quatro dígitos, uma única observação reduz de dez mil possibilidades para apenas 16. Se ele olhar uma segunda vez, pode ser que consiga informação suficiente para reduzir ainda mais o espaço, e, eventualmente, repetindo o processo, ele pode conseguir deduzir a senha.

Para conseguir reconstruir computacionalmente a senha, tudo que ele precisa fazer é resolver uma matriz de exact cover (na verdade outros métodos podem ser usados, mas eu sou preguiçoso adepto da orientação à objeto e do reuso de código pronto). Assuma n observações: para cada um dos 4 dígitos da senha há dez possibilidades, então você tem 40 linhas. Além disso, para cada observação, você precisa garantir que os quatro dígitos são consistentes, o que dá 4n colunas, e ainda mais 4 colunas extras para garantir que um único número estará associado a cada dígito da senha. No total, a matriz terá 40x(4n+4) elementos.

E quantas observações ele precisa? Isso não dá pra saber a priori, depende de como os números foram sorteados. Se a máquina repetir sempre a mesma distribuição, ele nunca vai conseguir deduzir a senha (mas também nem precisaria, pois aí ele só precisa apertar os mesmos botões que você). Por outro lado, se você tiver azar, pode ser que só duas observações sejam suficientes, como no caso abaixo:

observação 1:
senha CADA, botões A=(6 2) B=(5 8) C=(4 3) D=(1 9) E=(7 0)
observação 2:
senha CAAC, botões A=(1 2) B=(8 4) C=(6 3) D=(5 0) E=(7 9)

Nesse exemplo, dá pra ver claramente que a única senha consistente com os dados é 3216. Se o ladrão for levemente mais esperto, ele pode até perceber que não precisa fazer observações suficientes para que a senha seja única, basta que ele reduza o espaço de possibilidades para 3 ou menos (já que ele pode chutar 3 senhas antes da máquina bloquear o cartão).

Embora não seja possível calcular a priori quantas observações são necessárias, é perfeitamente possível calcular qual é o valor esperado dessa distribuição. Como eu sou preguiçoso adepto das simulações computacionais, ao invés de calcular as probabilidades na unha, eu escrevi uma simulação de Monte Carlo para calcular esse valor. O resultado é que, para uma senha de 4 dígitos, um ladrão que queira achar a senha exata precisa de 2.3 observações, enquanto que o ladrão esperto, que se contenta em reduzir pra 3 ou menos possibilidades, precisa de apenas 2.1 observações.

Código do simulador de Monte Carlo

A lição prática dessa análise é que, se você estiver desconfiado que o caixa tem um sniffer, não precisa ficar preocupado, desde que digite sua senha uma única vez. Se você precisar fazer uma outra operação, é melhor fazer em outra máquina.