Aula 10 Máquina de Turing

Prévia do material em texto

Aula 10 – Máquina de Turing 
1. Uma das funções de uma máquina de Turing consiste em reconhecer linguagens. 
Isso quer dizer que ela é capaz de classificar palavras como pertencentes ou não a 
determinada linguagem. 
Considere a máquina de Turing definida a seguir: 
 
Qual das seguintes cadeias é rejeitada pela máquina acima? 
A. aabbbaaaaa 
B. abaa 
C. aaaabaaaaa 
D. aabbaa 
E. abbbbaaaaa 
 
2. A função de transição de uma máquina de Turing é uma função parcial que mapeia 
um estado e um símbolo lido na posição atual da cabeça da fita em uma tripla que 
consiste no próximo estado, no símbolo que será escrito na fita e na direção em que a 
cabeça da fita se moverá. 
Considere a máquina de Turing dada a seguir: 
 
A. Próximo estado: indefinido. A entrada será rejeitada. 
B. Próximo estado: q4. Será escrito ’2’ na fita 
C. Próximo estado: q1. Será escrito ’1’ na fita. 
D. Próximo estado: q4. Será escrito ’b’ na fita. 
E. Próximo estado q7. Será escrito ’2’ na fita. 
 
3. O estudo do que pode (ou não) ser computado é o cerne da ciência da computação. 
Apesar de ser bastante antigo, ele se desenvolveu principalmente na primeira metade 
do século XX e foi revolucionado quando Alan Turing propôs um formalismo genérico de 
computação capaz de representar qualquer problema computável. 
Avalie as seguintes afirmações sobre a máquina de Turing e assinale a alternativa correta. 
 
A. Uma máquina de Turing é capaz de reconhecer qualquer linguagem que se enquadre 
na taxonomia de Chomsk 
B. Em uma máquina de Turing, sempre é possível saber se um programa termina sua 
execução, aceitando ou rejeitando a entrada. 
C. Um processador Intel Core i9 reconhece linguagens que não são possíveis de se 
reconhecer por meio de uma máquina de Turing. 
 
D. Toda linguagem que pode ser reconhecida por uma máquina de Turing também pode 
ser reconhecida por um autômato de uma pilha. 
E. Uma máquina de Turing com três fitas, não determinística e com fita multidimensional 
consegue processar linguagens que uma máquina de Turing tradicional não conseguiria. 
 
4. Diversas modificações para as máquinas de Turing determinística foram propostas ao 
longo dos anos com o objetivo de aumentar seu poder computacional. Até hoje, todos 
os modelos conseguiram no máximo igualar o poder de processamento da máquina 
determinística, sem superá-lo. 
Dado o gráfico de transições de uma máquina de Turing a seguir, qual é uma sequência 
possível de estados percorridos para que essa máquina aceite a palavra de entrada 
‘aabccb’? 
 
 
A. q0 — q0 — q0 — q0 — q3 — q4. 
B. q1 — q1 — q1 — q1 — q1 — q4. 
C. q0 — q0 — q2 — q2 — q2 — q4. 
D. q0 — q2 — q2 — q2 — q2 — q4. 
E. q0 — q0 — q0 — q3 — q3 — q4. 
 
5. Uma máquina de Turing é composta de uma fita de tamanho infinito com sua cabeça 
de leitura e escrita que servem de memória e como dispositivo de entrada e saída. 
Também existe uma função de transição, que corresponde ao programa executado pela 
máquina. 
Sobre a máquina de Turing, analise as seguintes afirmações: 
I. Uma máquina de Turing com múltiplas fitas pode reconhecer qualquer linguagem 
recursivamente enumerável. 
II. Para refutar a hipótese de Church, basta apresentar uma modificação da máquina de 
Turing que comprovadamente tenha mais poder computacional que uma máquina de 
Turing determinística. 
III. Por padrão, uma máquina de Turing determinística pode alterar diversos pontos da 
fita em cada transição e é capaz de transferir sua atenção para mais de uma posição da 
fita em cada argumento da função de transição. 
Qual(is) dessas afirmações está(ão) correta(s)? 
 
A. Apenas I. 
B. Apenas II. 
C. I e II. 
D. I e III. 
E. I, II e III.