AVALIAÇÃO 5 Mentes e Máquinas

Prévia do material em texto

AVALIAÇÃO 5 Mentes e Máquinas - Inteligência Artificial Profissional sem Segredos
O modelo original de Alan Turing foi expandido ao longo do tempo com diversas variações, como o não determinismo e o uso de múltiplas fitas. Embora essas modificações tenham sido propostas com o objetivo de aumentar o poder computacional, nenhuma delas foi capaz de estender o conjunto de linguagens aceitas pela máquina original. Tais variações são fundamentais para dar robustez à Hipótese de Church, que postula que qualquer função computável pode ser processada por uma máquina de Turing.
Sobre a equivalência entre os diferentes modelos de Máquinas de Turing, avalie as asserções abaixo e a relação proposta entre elas:
I. Uma Máquina de Turing com múltiplas fitas possui o mesmo poder computacional de uma Máquina de Turing de fita única, sendo capaz de reconhecer exatamente a mesma classe de linguagens.
PORQUE
II. É possível simular o comportamento de uma máquina com múltiplas fitas em uma máquina de fita única através do uso de símbolos auxiliares (como o #) para delimitar o conteúdo e marcar a posição das cabeças de leitura.
A respeito dessas asserções, assinale a opção correta:
Selecione a resposta:
· A A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
· B A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
· C As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
· D As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
· E As asserções I e II são proposições falsas.
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:
​​​​​​​​​​​​​​Com base no conteúdo da fita e no estado corrente da máquina, qual será o próximo estado alcançado? O que será escrito na posição para onde a cabeça da máquina está apontando?
Selecione a resposta:
· 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.
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.​​​​​​​
Selecione a resposta:
· A Uma máquina de Turing é capaz de reconhecer qualquer linguagem que se enquadre na taxonomia de Chomsky.
· 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.
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’?
​​​​​​
Selecione a resposta:
· 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.
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)?
Selecione a resposta:
· A Apenas I.
· B Apenas II.
· C I e II.
· D I e III.
· E I, II e III.
image1.jpeg
image2.jpeg