Alan Turing Brasil 2012

Exposição Palestras Concurso de Vídeo Quebrando o Código Cultural

O conceito de máquina de Turing é semelhante ao de uma fórmula ou equação. Assim, há uma infinidade de possíveis máquinas de Turing, cada uma correspondendo a um método definido ou algoritmo. Turing propôs que cada algoritmo, formalizado como um conjunto finito de instruções bem definidas, pudesse ser interpretado e executado por um processo mecânico.
Formalmente a máquina de Turing pode ser definida como uma máquina que contém:

Um conjunto finito de estados Q com um estado inicial distinto,
Um conjunto finito de símbolos ?.

A interpretação e execução dos algoritmos são realizadas por estados e uma função de transição determina o novo conteúdo da fita. Desde modo, por restrição imposta ao algoritmo, pode-se alterar o conteúdo de apenas um quadrado por vez ou movimentar a cabeça, no máximo uma célula em qualquer direção. É permitida também a utilização de qualquer conjunto finito de símbolos para o alfabeto ?, mesmo que a definição original tenha insistido em ? = {0,1}. Esta mudança não tem impacto sobre a definição do conjunto de funções computáveis pela máquina.
O que torna uma máquina de Turing capaz de executar uma tarefa é a tabela de regras de transição que compõem o programa da máquina e um determinado estado inicial. O conjunto de instruções conhecidas e processadas pelo módulo de controle finito é relacionado abaixo:

IMPRIMA 0 NO QUADRADO QUE PASSA PELA CABEÇA
IMPRIMA 1 NO QUADRADO QUE PASSA PELA CABEÇA
VÁ UM QUADRADO PARA A ESQUERDA
VÁ UM QUADRADO PARA A DIREITA
VÁ PARA O PASSO i SE O QUADRADO QUE PASSA PELA CABEÇA CONTÉM 0
VÁ PARA O PASSO j SE O QUADRADO QUE PASSA PELA CABEÇA CONTÉM 1
PARE

Por exemplo: uma computação pode ser representada por três estados, nomeados s0, s1, s2 e com algumas instruções formalizadas no Algoritmo 1:

1 ( s0 , 1, s0 , »)

2 ( s0 , 0, s1 , 1)

3 ( s1 , 1, s1 , «)

4 ( s1 , 0, s2 , »)

Algoritmo 1: Exemplo de instruções entre três estados s0, s1 e s2.

As duas primeiras instruções (linhas 1 e 2) descrevem o que acontecerá no estado s0. Há duas possibilidades: na primeira, a máquina faz a leitura de um dígito '1', movimentará a cabeça para a direita e permanecerá no estado s0. Na segunda, se for lido um dígito '0' a máquina deixará o estado s0, entrará no estado s1 e escreverá o dígito '1' nessa transição. As instruções descritas nas linhas 3 e 4 mostram o que acontecerá no estado s1, ou seja, se for lido o dígito '1', a máquina movimentará a cabeça para a esquerda e permanecerá no estado s1. Se for lido o dígito '0', a cabeça será movimentada para a direita e a máquina passará para o estado s2. Como não há instruções definidas pelo algoritmo no estado s2, a máquina pára a sua execução (condição de parada) ao atingir este estado. Quando estamos interessados em examinar o comportamento de uma máquina de Turing, é eficiente representarmos a máquina usando um diagrama de estados. A Figura 2 representada o conjunto de instruções neste formato visual. Figura 2: Um diagrama de estados representativo ao Algoritmo 1. Nesta figura, os estados são representados por círculos, com um círculo duplo identificando o estado inicial. Uma transição é representada por uma aresta ou arco proveniente de um estado para outro ou para o mesmo estado. As arestas são rotuladas por pares (símbolo, ação), constituído primeiro pelo símbolo que deverá ser lido e depois, pela ação que deverá ser executada com a transição. Os símbolos pertencem ao alfabeto ? e a ação será o símbolo a ser escrito, ou ainda « ou », indicando um movimento para a esquerda ou direita...

Baixe este texto na íntegra! Baixe uma cópia do artigo de Alan Turing sobre números computáveis!

Endereço:

País: Brasil: Cidade: Porto Alegre; Instituto de Informática; Campus do Vale; Caixa Postal 15064; Fone +55 (51) 3308 6168; Fax +55 (51) 3308 7308; Email:info@ufrgs.br