Ano Turing

Neste ano, comemoramos o centenário do nascimento do grande cientista da computação Ala Turing. A vida e a obra de Turing são fascinantes. A frase de Harvey Dent no filme  Batman O Cavaleiro das Trevas Ressurge poderia ser aplicada a vida de Turing :  “ou você morre como um herói, ou vive o suficiente para se tornar um vilão”

Durante a segunda guerra, Alan Mathison Turing trabalhou em Bletchley Park, o centro de operações de criptanálise durante a guerra. O trabalho do jovem Turing sobre uma máquina Universal capaz de resolver um problema lógico foi seu passaporte para esta grande aventura de criptanálise. Turing era a pessoa certa no momento certo. Os alemães possuíam uma máquina eletro-mecânica de criptografia chamada Enigma utilizada para criptografar suas instruções militares. A máquina Enigma era supostamente indecifrável. Para quebrar o código Enigma, Turing e sua equipe construíram uma máquina que analisava o código enigma buscando regularidades, traços recorrentes que pudessem ajudar na quebra do código. Essa máquina tinha a capacidade para escanear 25000 caracteres por segundo. Depois da guerra, a homossexualidade de Turing foi vista como uma ameaça pelo governo britânico. Ele submeteu-se (ou foi submetido) a tratamento  hormonal controverso como uma alternativa à prisão. Turing morreu em 1954, duas semanas antes do seu aniversário de 42 anos, por envenamento. Em 2009, o primeiro ministro britânico fez um pedido oficial de desculpas pública, em nome do governo britânico,  devido à maneira pela qual Turing foi tratado após a guerra.

O nome de Turing está relacionado intimamente com diversas contribuições na área da Computação. Vamos conhecer algumas delas:

Máquina de Turing

Formalmente, uma máquina de Turing (com uma fita) é usualmente definida como uma Tupla , onde

•  é um conjunto finito de estados
•  é um alfabeto finito de símbolos
•  é o alfabeto da fita (conjunto finito de símbolos)
•  é o estado inicial
•  é o símbolo branco (o único símbolo que se permite ocorrer na fita infinitamente em qualquer passo durante a computação)
•  é o conjunto dos estados finais
•  ⇒  é uma função parcial chamada função de transição, onde  é o movimento para a esquerda e  é o movimento para a direita.

A máquina de Turing é um dispositivo teórico construído para capturar formalmente a noção de computabilidade ou procedimento efetivo ou mecânico (tudo que pode ser feito seguindo-se diretamente um algoritmo ou um conjunto de regras). Observe que Turing conseguiu propor uma formalização para um conceito totalmente abstrato de computabilidade.

Tese de Church-Turing

O mais interessante é que diversas extensões da Máquina de Turing não conseguiam ser mais poderosas que a Máquina de Turing simples. Turing estava andando no mesmo terreno que Cantor quando começou a descobrir os primeiros paradoxos da cardinalidade dos números infinitos.

Exemplos:
Máquina de Turing com múltiplas fitas.
Máquina de Turing com múltiplos cabeçotes.
Máquina de Turing com fita infinita para os dois lados.
Máquina de Turing não-determinísticas
Máquina de Turing Multidimensional


Church definiu um modelo de computabilidade diferente chamado lambda cálculo. Esse modelo de computabilidade também não conseguia ser mais poderoso que a computabilidade definida pela Máquina de Turing. A tese de Church-Turing estabelece que os limites da máquina de Turing também descreve os limites de todos os computadores.

Máquina de Turing Universal

A máquina de Turing Universal é uma máquina de Turing que pode simular uma Máquina de Turing arbitrária e uma  entrada arbitrária. A máquina de Turing Universal é a origem da dualidade programa/dado que é parte essencial da arquitetura dos computadores modernos. Observe que essa dualidade permite a ideia de um programa vírus. Um vírus é um dado/programa que explora um programa/dado para ser executado.


Turing-complete


Um sistema é dito Turing-Complete se ele pode simular uma máquina de Turing Universal ou um outro sistema Turing-Complete conhecido. Suponha que eu queira provar que a linguagem C é Turing-complete, basta eu fazer um programa que simule uma máquina de Turing Universal ou fazer um interpretador em C da linguagem brainfuck (linguagem Turing-complete conhecida).