Boris Trakhtenbrot, 1921-2016

[Joao Marcos]

Não são todos que podem se gabar de ter um teorema que leva o seu nome
(https://en.wikipedia.org/wiki/Trakhtenbrot%27s_theorem).
Infelizmente, o resultado sobre a indecidibilidade do problema de
validade sobre a classe de todos os modelos finitos está na literatura
há 66 anos, mas ainda não é tão bem conhecido como deveria, nem é
lugar-comum nos livros-texto de Lógica Matemática / Computacional.
(Eu próprio soube dele, no início do meu doutorado, apenas por meio da
minha co-autora Sandra de Amo, uma especialista em bancos de dados.)

Boaz Trakhtenbrot também é bem conhecido na comunidade de complexidade
computacional, por outros resultados igualmente importantes, tais
como:
https://en.wikipedia.org/wiki/Gap_theorem

RIP
http://cacm.acm.org/news/207650-in-memoriam-boris-trakhtenbrot-1921-2016/fulltext

Joao Marcos


PS: Há dois anos, ao passar uma temporada na Universidade de Tel-Aviv,
presentearam-me com um gabinete de trabalho cuja porta tinha uma
plaquinha com o nome de Trakhtenbrot: "ele está muito velhinho e só
vem aqui muito de vez em quando", me disseram. Qual não foi minha
surpresa quando um dia cheguei para trabalhar e o encontrei por lá!
https://dl.dropboxusercontent.com/u/9291912/pics/BTrakhtenbrot.JPG