Para falarmos da máquina de Turing, precisamos conhecer seu criador: Alan Mathison Turing (1912-1954), conhecido também como Alan Turing. Ele foi um matemático britânico nascido em 23 de junho de 1912 na cidade de Paddington, na Inglaterra. Estudou na tradicional Escola Sherbourne tendo-se graduado em 1931 em Matemática pela Universidade de Cambridge.
Depois de formado, e após muito estudo, criou uma máquina automatizada que calcula qualquer algoritmo e processa as instruções mecanicamente na própria máquina. Essa é a tão famosa Máquina de Turing que serviu como protótipo para os computadores atuais e permitiu o desenvolvimento do “Enigma” que foi capaz de decifrar os códigos nazistas na Segunda Guerra Mundial.
Máquina de Turing
Uma Máquina de Turing pode ser descrita como sendo constituída por uma cabeça de leitura/escrita e uma fita unidimensional potencialmente infinita em ambas as direções. A fita e dividida em células, cada uma das quais com capacidade de conter um único símbolo. Em cada instante de tempo a máquina se encontra em um determinado estado, e com a cabeça lendo uma célula especifica da fita, a qual ela considerada como sendo a posição atual da maquina. A configuração atual da maquina consiste na junção do estado atual e do símbolo que esta sendo lido na posição atual.
O comportamento da máquina é determinado por um conjunto de instruções, as quais indicam a operação a se realizar dependendo da configuração atual. As únicas operações que a maquina pode realizar são: escrever um novo símbolo na posição atual (substituindo o símbolo anterior) ou realizar um movimento da cabeça a esquerda ou direita, passando a uma célula subsequente da atual. Os estados, os símbolos de leitura/escrita e as instruções são conjuntos finitos.
Uma Máquina de Turing M é uma estrutura matemática <Q,E,M,I> onde:
- Q = {q1, q2, . . . , qn} (com Q ≠ ∅) é um conjunto finito de estados da maquina;
- E = {s1, s2, . . . , sm} (com ( E − {s1} ≠ ∅)) é um conjunto finito de símbolos de entrada/saída (ou alfabeto de entrada/saída). Por convenção s1 representa o símbolo vazio;
- M = {R,L} é o conjunto de movimentos da maquina, onde R indica movimento a direita e L indica movimento a esquerda;
- I = {i1, i2, . . . , ik} (com I ≠ 0) é um conjunto finito de instruções.
Cada ij é uma quádrupla de alguma das formas: qisjskql (I), qisjRql (II) e qisjLql (III), onde I, II e III são tipos de instruções numa Máquina de Turing:
I – Quando a maquina estiver no estado qi, lendo o símbolo sj, vai escrever o símbolo sk e passará ao estado ql;
II – Quando a maquina estiver no estado qi, lendo o símbolo sj, vai se deslocar uma célula à direita e vai passar ao estado ql;
III – Similar ao (II), com a diferença que o movimento se da à esquerda.
Com essa base computacional, outras máquinas de turing se desenvolveram como iremos abordar no nosso oitavo capítulo da serie: Lógica Paraconsistente: Máquina de Turing Paraconsistente.
Fonte Complementar:
Biografia – Alan Turing