MÁQUINAS DE
TURING
Acadêmicos:
Karen Juliani Tosta Tomaz RA – 47566
Clauan Castro
RA – 47857
Mayara Oliveira dos Santos RA – 48891
Andressa Rautenberg
RA – 48909
Carlos Alexandre Fontana RA – 47664
Bruna Ritieli
RA – 47650
MÁQUINAS DE TURING
• Proposto por Alan Turing em 1936, a máquina de
Turing é semelhante a um autômato finito, mas
com uma memória ilimitada e irrestrita, uma
máquina de Turing é um modelo muito mais
acurado de um computador de propósito geral.
Uma máquina de Turing pode fazer tudo que um
computador real pode fazer, entretanto, uma
máquina de Turing não pode resolver certos
problemas.
MÁQUINAS DE TURING
• O modelo da máquina de Turing usa uma fita infinita como sua
memória ilimitada. Possui uma cabeça de fita que pode ler e
escrever símbolos e mover-se sobre a fita. Inicialmente, a fita
contém apenas a cadeia de entrada e está em branco em todo
o restante. Se a máquina precisa armazenar informação, ela
pode escrevê-la sobre a fita. Para ler a informação que ela
escreveu, a máquina pode mover sua cabeça de volta para a
posição onde a informação foi escrita. A máquina continua a
computar até que ela decida produzir uma saída. As saídas:
aceite e rejeite são obtidas entrando em estados designados
de aceitação e de rejeição. Se não entrar em um estado de
aceitação ou de rejeição, ela continuará para sempre, nunca
parando.
MÁQUINAS DE TURING
• A parte mais importante da definição de uma máquina
de Turing é a função de transição , pois ela informa
como a máquina vai de um passo para o próximo. Para
uma máquina de Turing,  toma a forma: Q    Q  
 {E, D}. Ou seja, quando a máquina está em certo estado
q e a cabeça está sobre uma célula da fita contendo um
símbolo a e se  (q, a) = (r, b, E), a máquina escreve o
símbolo b substituindo o a e vai para o estado r. O
terceiro componente é o E ou D e indica se a cabeça
move para a esquerda ou direita após escrever.
MÁQUINAS DE TURING
• Uma máquina de Turing é uma 7-upla, (Q, Ʃ, , , q0, qaceita,
qrejeita), onde Q, Ʃ,  são todos conjuntos finitos e;
• Q é o conjunto de estados.
• Ʃ é o alfabeto de entrada não contendo o símbolo em branco
|_|.
•  é o alfabeto de fita, onde |_|   e Ʃ  .
• : Q    Q    {E, D} é a função de transição.
• q0  Q é o estado inicial.
• qaceita  Q é o estado de aceitação.
• qrejeita  Q é o estado de rejeição, onde qrejeita  q aceita.
MÁQUINAS DE TURING
• Uma máquina de Turing é uma 7-upla, (Q, Ʃ, , , q0, qaceita,
qrejeita), onde Q, Ʃ,  são todos conjuntos finitos e;
• Q é o conjunto de estados.
• Ʃ é o alfabeto de entrada não contendo o símbolo em branco
|_|.
•  é o alfabeto de fita, onde |_|   e Ʃ  .
• : Q    Q    {E, D} é a função de transição.
• q0  Q é o estado inicial.
• qaceita  Q é o estado de aceitação.
• qrejeita  Q é o estado de rejeição, onde qrejeita  q aceita.
MÁQUINAS DE TURING
Exemplo 1:
• O esquema da máquina de Turing é bastante simples,
conforme a Figura01: uma fita que pode se mover de passo
em passo para a direita ou para a esquerda.
• Cada passo (também chamado de célula) pode estar cheio
(representado por *) ou vazio. No exemplo da figura, em a
existe um passo vazio e em b, dois passos vazios adjacentes.
• Para simplificar, supõe-se que uma célula cheia só pode ter
um único símbolo (*), mas pode ter vários símbolos
diferentes.
MÁQUINAS DE TURING
• O cabeçote C pode ler o conteúdo do passo e nele escrever,
deixando-o cheio ou vazio. Por exemplo, na posição do cabeçote da
figura e dependendo da instrução, o cabeçote poderá deixar a
marca * ou removê-la, tornando vazia a posição.
• Numa construção prática, não seria viável uma do tipo fita
perfurada, pois seria muito complicado recompor um local furado,
mas seria perfeitamente possível o uso de fita magnética como em
alguns equipamentos atuais.
MÁQUINAS DE TURING
• O próximo componente é um conjunto de instruções
específico para cada função a resolver, conforme exemplo a
seguir, que é simples, apenas para demonstração. Existem
muitos outros que podem ser apresentados, inclusive
programas de computador que simulam a máquina de Turing.
• Na descrição anterior foi comentado que a fita se move e o
cabeçote é fixo, similar a um gravador atual. Entretanto, para
facilitar a representação em tabela, considera-se agora que o
cabeçote se move e a fita é fixa, o que é apenas uma questão
de referência.
MÁQUINAS DE TURING
• O exemplo considerado é uma operação matemática elementar: Somar dois
números inteiros. Supõe-se que se deseja somar os números 3 e 4.
• A entrada dos dados seria uma fita com a disposição: *** ****, ou seja,
representando os números 3 e 4.
• A saída dos dados seria a seguinte informação na fita: *******, ou seja
representando o número 7 (3 + 4).
Tabela 01
Estado
0
1
2
Ação se a célula estiver
Ação se a célula estiver
cheia (*)
vazia
Mover para direita,
Escrever *, mover para
continuar no estado 0
direita, ir para estado 1
Mover para direita,
Mover para esquerda, ir
continuar no estado 1
para estado 2
Apagar, parar
MÁQUINAS DE TURING
• A tabela anterior, também denominada tabela de ações, instrui a máquina
para adicionar dois números consecutivos e apresentar o resultado conforme
estabelecido.
• Abaixo a operação passo a passo da máquina (a posição do cabeçote é
indicada pelo fundo cinza).
MÁQUINAS DE TURING
• Os estados que a máquina pode assumir podem ser vistos
como variáveis auxiliares para a tomada de decisões. Tudo isso
lembra um pouco o software das máquinas de hoje.
• O procedimento poderia somar qualquer par de números
inteiros, independente dos valores. Entretanto, o número de
células necessárias deve acompanhar. Assim, por exemplo,
para somar 40000 com 60000 seriam, no mínimo, 100000
células. Na realidade, uma máquina de Turing universal, isto é,
capaz de efetuar qualquer operação matemática e com
quaisquer valores, deveria ter uma fita de comprimento
infinito.
MÁQUINAS DE TURING
• Exemplo 2:
• • Seja a linguagem L1= { anbn | n ≥ 0}.
• • A Máquina de Turing M = ({a, b}, {q0, q1, q2, q3, q4}, δ1, q0,
{q4}, {A, B}, β), onde δ1 é como na tabela a seguir é tal que:
• (1) ACEITA(M) = L1, (2) REJEITA(M) = Σ* - L1 e (3) LOOP(M)
=∅
MÁQUINAS DE TURING
MÁQUINAS DE TURING