Máquinas de Turing Determinísticas e Não Determinísticas

Prévia do material em texto

12/06/2024, 09:20Atividade 4: Linguagens Formais e Autômatos
Página 1 de 10https://famonline.instructure.com/courses/35817/quizzes/177213?headless=1
Atividade 4
Entrega 26 mai em 23:59
Pontos 1
Perguntas 5
Disponível 12 fev em 0:00 - 26 mai em 23:59
Limite de tempo Nenhum
Tentativas permitidas 2
Instruções
Este teste foi travado 26 mai em 23:59.
Histórico de tentativas
Tentativa Tempo Pontuação
MAIS RECENTE Tentativa 1 6 minutos 0,6 de 1
Pontuação desta tentativa: 0,6 de 1
Enviado 23 abr em 14:27
Esta tentativa levou 6 minutos.
 
Pergunta 1
0,2 / 0,2 pts
Importante:
Caso você esteja realizando a atividade através do aplicativo "Canvas Student", é necessário que
você clique em "FAZER O QUESTIONÁRIO", no final da página.
Leia o trecho abaixo:
Definição - O que significa Máquina de Turing Não Determinística (NTM)?
Uma máquina de Turing não determinística é um tipo teórico de computador no qual comandos
específicos podem permitir uma gama de ações, em vez de um comando específico que leva a
apenas uma ação permitida no modelo determinístico de computação.
Onde a programação determinística é uma condição simples de 'entrada X leva à ação Y', uma
configuração de máquina de Turing não determinística teoricamente permitiria que a entrada X
levasse a uma variedade de ações Y (matriz) [...].
As máquinas de Turing não determinísticas podem realmente fornecer uma direção para o futuro
A+
A
A-
https://famonline.instructure.com/courses/35817/quizzes/177213/history?version=1
12/06/2024, 09:20Atividade 4: Linguagens Formais e Autômatos
Página 2 de 10https://famonline.instructure.com/courses/35817/quizzes/177213?headless=1
Correto!
da computação inteligente ou artificialmente inteligente. Ao desvincular o trabalho computacional
do paradigma determinístico, os computadores poderiam aprender a resolver problemas mais
complicados e 'pensar' mais como humanos.
Um tipo de máquina de Turing não determinística é a máquina de Turing probabilística. Aqui, a
matriz de ações (Y) mencionada acima é determinada por meio de alguma distribuição de
probabilidade. Outra maneira de dizer isso é que quando a máquina tem mais de uma escolha,
ela vai para um modelo probabilístico, analisa esse modelo e faz uma escolha de acordo.
Existem muitas outras maneiras de solicitar uma máquina de Turing não determinística, mas o
princípio é que o computador deve escolher a partir de um conjunto de opções disponíveis.
Alguns modelos de Turing não determinísticos em uma configuração de aprendizado de máquina
podem consistir em o computador seguir caminhos lógicos até um fim aceito ou rejeitado e, em
seguida, voltar e escolher uma ação de acordo.
Como os especialistas apontam, as máquinas de Turing não determinísticas são diferentes dos
modelos de computação quântica. Na computação quântica, a confluência de bits binários em
qubits amplia o paradigma e torna os processos de computação mais elaborados e sofisticados.
Na máquina de Turing não determinística, conforme explicado, é a disponibilidade de escolhas de
acordo com as entradas que afasta o modelo de computação do determinismo puro.
Fonte: ASHLAN. Máquina de Turing não determinística (ntm). Definirtec, [s. d]. Disponível em:
https://definirtec.com/maquina-de-turing-nao-deterministica-ntm/. Acesso em: 10 fev. 2023.
Considerando as informações apresentadas sobre as máquinas de Turing determinísticas e não
determinísticas, avalie as afirmações abaixo:
I. Do ponto de vista da computabilidade, uma máquina de Turing probabilística é equivalente
a uma máquina de Turing não determinística.
II. Uma máquina de Turing não determinística é uma máquina de Turing modificada para
executar uma computação aleatória.
III. A diferença entre uma máquina de Turing determinística e uma máquina de Turing não
determinística é a mesma entre um AFD e um AFN.
IV. Uma máquina de Turing não determinística é uma variante da máquina de Turing
simples.
É correto o que se afirma em:
12/06/2024, 09:20Atividade 4: Linguagens Formais e Autômatos
Página 3 de 10https://famonline.instructure.com/courses/35817/quizzes/177213?headless=1
 III e IV, apenas.
 I e IV, apenas.
 II e III, apenas.
 II, III e IV, apenas.
 I, II e III, apenas.
A alternativa está correta. É correto o que se afirma em III e IV, apenas.
A afirmação I está incorreta, pois do ponto de vista da computabilidade, uma máquina de Turing
probabilística é equivalente a uma máquina de Turing. Em outros aspectos, entretanto, o
comportamento de uma máquina de Turing probabilística é profundamente diferente da
computação determinística de uma máquina de Turing. Resultados falsos, por exemplo, só podem
ser excluídos estatisticamente em uma máquina de Turing probabilística.
A afirmação II está incorreta, pois uma Máquina de Turing Probabilística (MTP) é uma Máquina de
Turing (MT) modificada para executar uma computação aleatória. Além disso, algumas aplicações
da ciência da computação podem ser melhor modeladas por uma máquina de Turing
probabilística do que por uma máquina de Turing clássica.
A afirmação III está correta, pois a diferença entre uma Máquina de Turing Determinística e uma
Máquina de Turing não Determinística é a mesma entre um AFD e um AFN. Uma Máquina de
Turing Multifita é usada para construir uma Máquina de Turing não Determinística. Além disso,
todas as sequências de transição possíveis de uma máquina de Turing não Determinística em
uma determinada string de entrada podem ser representadas por uma árvore chamada árvore de
computação.
A afirmação IV está correta, pois uma Máquina de Turing não Determinística é uma variante da
máquina de Turing simples. Para cada entrada em um estado, pode haver vários caminhos/ações
executados pela máquina de Turing, o que significa que as transições não são determinísticas.
 
Pergunta 2
0,2 / 0,2 pts
Leia o trecho abaixo:
[...] A máquina de Turing seria equipada com uma fita perfurada de comprimento infinito,
preenchida em intervalos regulares com símbolos de um conjunto finito e um ponteiro que
marcaria a posição real em que a máquina se encontrava, dentro de um conjunto limitado de
"estados internos" possíveis.
12/06/2024, 09:20Atividade 4: Linguagens Formais e Autômatos
Página 4 de 10https://famonline.instructure.com/courses/35817/quizzes/177213?headless=1
Entretanto, em cada operação a máquina leria o símbolo inscrito na posição correspondente na
fita, e para cada combinação de posição e símbolo lido um programa especificaria um novo
símbolo para inscrever na mesma fita ou um movimento a ser efetuado pelo ponteiro, que poderia
deslocar-se para a esquerda, para a direita, ou parar.
Com esta máquina abstrata, Turing pretendia conseguir definições matematicamente precisas
para algoritmos, ou procedimentos mecânicos.
Ainda muito utilizada na abordagem a teorias como a da computação ou da complexidade, a
máquina de Turing compreenderia então, e mais precisamente, quatro elementos:
- Uma fita dividida em células contíguas, cada qual contendo um símbolo de um alfabeto finito,
que por sua vez contém, entre outros, um símbolo nulo especial. Esta fita seria infinitamente
extensível para a esquerda e para a direita, e assumir-se-ia que as células que não tivessem sido
preenchidas com um símbolo contivessem o carácter especial nulo.
- Um dispositivo de leitura e gravação que se movimentasse para a esquerda e para a direita
nessa fita, e conseguisse interpretar e escrever os símbolos.
- Um outro dispositivo que registasse cada estado da máquina de Turing, sendo que o número de
estados diferentes seria sempre finito e compreenderia um estado inicial de arranque, que
iniciaria o dispositivo de registro.
- Uma tabela de ações que comandaria os movimentos da máquina, dizendo-lhe que símbolo
escrever, para onde mover o dispositivo de leitura e gravação, e decidiria qual o seu novo estado,
em função do símbolo acabado de ler e do estado em que a máquina se encontrasse no
momento. Se porventura não existisse qualquer entrada na tabela de ações para uma dada
combinação de símboloe estado, então a máquina consideraria o programa concluído e pararia.
Fonte: MÁQUINA DE TURING. In: INFOPÉDIA. Porto: Porto Editora, 2022. Disponível em:
https://www.infopedia.pt/apoio/artigos/$maquina-de-turing. Acesso em: 05 ago. 2023.
Considerando o texto sobre o funcionamento da máquina de Turing, avalie as afirmações abaixo:
I. Uma máquina de Turing consiste em uma fita infinitamente longa, que foi dividida em
células.
II. A direção em que o ponteiro se move depende de um conjunto de instruções fornecidas à
máquina.
III. O ponteiro é incapaz de apagar símbolos e escrever novos símbolos nas células.
IV. O ponteiro pode se mover para a esquerda ou para a direita e pode ler os símbolos
escritos nas células.
É correto o que se afirma em:
12/06/2024, 09:20Atividade 4: Linguagens Formais e Autômatos
Página 5 de 10https://famonline.instructure.com/courses/35817/quizzes/177213?headless=1
 III e IV, apenas.
Correto!
 I, II e IV, apenas.
 I, III e IV, apenas.
 I e II, apenas.
 II e III, apenas.
A alternativa está correta. É correto o que se afirma em I, II e IV, apenas.
A afirmação I está correta, pois uma máquina de Turing consiste em uma fita infinitamente longa,
que foi dividida em células. Cada célula pode conter um 1, um 0 ou um espaço vazio. Além disso,
Alan Turing provou que qualquer problema computável pode ser calculado por uma máquina de
Turing usando seu sistema simples.
A afirmação II está correta, pois a direção em que o ponteiro se move, quais valores ele apaga e
quais valores ele insere dependem de um conjunto de instruções fornecidas à máquina. As
instruções para uma máquina de Turing simples apresentam apenas um estado, mas máquinas
de Turing mais complexas podem ser construídas usando vários estados.
A afirmação III está incorreta, pois o ponteiro também é capaz de apagar símbolos e escrever
novos símbolos nas células. Isso é o que chamamos de movimentos entre estados da máquina.
A afirmação IV está correta, pois o ponteiro pode se mover para a esquerda ou para a direita e
pode ler os símbolos escritos nas células. Para colocar uma máquina de Turing para funcionar,
basta ter uma fita, um ponteiro, e, após algumas instruções iniciais usando 1 e 0, será possível
ver movimentos da máquina.
 
Pergunta 3
0 / 0,2 pts
Leia o trecho abaixo:
[...] Turing projetou sua máquina universal para estudar um problema apresentado por David
Hilbert em 1928: o Entscheidungsproblem, o problema de decisão. Este problema foi formulado
dentro da estrutura do programa de Hilbert que visa garantir a fundação da matemática,
axiomatizando rigorosamente vários ramos do campo. Este programa estabelece os três eixos
mais importantes a serem comprovados para a fundação de um sistema matemático sólido, a
saber:
A completude, ou seja, qualquer predicado apenas no sistema pode ser comprovado.
12/06/2024, 09:20Atividade 4: Linguagens Formais e Autômatos
Página 6 de 10https://famonline.instructure.com/courses/35817/quizzes/177213?headless=1
 
Devido à sua complexidade, a máquina de Turing pode simular qualquer algoritmo de computador, por mais
complicado que ele seja.
Resposta correta
 
O Entscheidungsproblem de Hilbert, declarado em 1928, é o problema de decisão para teorias de primeira
ordem.
Você respondeu
 
O Entscheidungsproblem questiona se há um algoritmo que determine a veracidade de uma afirmação em
determinados modelos de uma teoria.
Esta alternativa está incorreta, pois Entscheidungsproblem representa o alemão de ‘problema de
A consistência, ou seja, não deve haver contradições no sistema.
A decidibilidade ou o fato de que para um determinado predicado, podemos através do "método
efetivo" (a noção de algoritmo não é válida na época) decidir sua veracidade.
O Entscheidungsproblem é precisamente uma tentativa de formalizar o problema da
decidibilidade, usando um formalismo desenvolvido por Gottlob Frege, o cálculo dos predicados.
Uma das possíveis afirmações desse problema é:
Encontre um algoritmo que determine se uma frase declarada no formalismo do cálculo de
predicados é válida, isto é, verdadeira qualquer que seja a semântica dos objetos e relações que
ela implementa.
Agora é a hora de os lógicos Alonzo Church e Alan Turing intervirem.
Para responder negativamente ao problema de decisão enunciado por Hilbert, Church define o
cálculo lambda, a primeira teoria que define com rigor o que é um “método” ou “procedimento”
eficiente para resolver um problema e usa os conceitos de funções recursivas introduzidos por
Jacques Herbrand e Kurt Gödel. De fato, ele provou, pelo absurdo, que não pode existir um
método geral para decidir se um predicado é correto ou não.
Alan Turing, por sua vez, criou o conceito de máquinas de Turing com o mesmo propósito,
independentemente de Church, no mesmo ano. Ele também consegue demonstrar que há
sentenças cuja validade não pode ser determinada por um algoritmo, destacando o problema da
parada [...]. 
Fonte: MÁQUINA de Turing Universal. Friwiki, Disponível em:
https://pt.frwiki.wiki/wiki/Machine_de_Turing_universelle. Acesso em: 05 ago. 2023.
Considerando as informações apresentadas, assinale a opção correta:
12/06/2024, 09:20Atividade 4: Linguagens Formais e Autômatos
Página 7 de 10https://famonline.instructure.com/courses/35817/quizzes/177213?headless=1
decisão’, proposto por David Hilbert em 1928. Quando simplificado, Entscheidungsproblem
questiona se existe um algoritmo para determinar se uma afirmação é verdadeira em todos os
modelos de uma teoria, e não apenas em um ou mais modelos específicos. A alternativa correta é
“O Entscheidungsproblem de Hilbert, declarado em 1928, é o problema de decisão para teorias
de primeira ordem”.
 Em 1928, o conceito de um algoritmo de computador já havia sido criado por David Hilbert.
 
Turing mostrou decisivamente que tal algoritmo existia e, no processo de fazê-lo, habilmente lançou a era do
computador.
 
Pergunta 4
0 / 0,2 pts
Leia o trecho abaixo:
[...] Após o final da guerra, Turing seguiu trabalhando com criptografia e computação. Entre 1945
e 1947 trabalhou no projeto do ACE (Automatic Computing Engine) e escreveu um artigo com o
primeiro projeto detalhado de computador capaz de guardar instruções computacionais na
memória [...].
“Computadores e inteligência” (Computer Machinery and Intelligence, no original em inglês) foi
publicado na revista de filosofia Mind em outubro de 1950 e é precursor da inteligência artificial (o
termo só seria criado em 1956). É um artigo no qual Turing, motivado pela experiência com os
primeiros computadores digitais e adotando um tom bastante especulativo, se coloca a pergunta:
“as máquinas podem pensar?” A questão que despertava interesse filosófico para Turing há 70
anos desperta hoje interesse generalizado na medida em que temos computadores potentes,
onipresentes e interconectados, coleta massiva de dados e muita pesquisa na área de
aprendizagem de máquina.
No artigo, Turing re-apresenta de forma sucinta seu modelo teórico de computador e propõe um
jogo (o jogo da imitação) que hoje chamamos de Teste de Turing quando jogado por uma
máquina. Ele conjectura que os computadores do futuro serão capazes de passar no teste, isso é,
serão capazes de imitar seres humanos, e discute com algumas das objeções da época a essa
ideia. Na última seção, ainda sugere uma ideia do que hoje chamamos de “aprendizagem por
reforço”. A leitura do artigo é um interessante passeio por algumas de suas ideias e
principalmente pelo seu jeito de pensar e argumentar [...].
Fonte: MADEIRA, T. Alan Turing e máquinas inteligentes. Revista Movimento, 23 jun. 2021.
Disponível em: https://movimentorevista.com.br/2021/06/alan-turing-e-maquinas-inteligentes/.
Acesso em: 10 fev. 2023.
12/06/2024, 09:20Atividade 4: Linguagens Formais e Autômatos
Página 8 de 10https://famonline.instructure.com/courses/35817/quizzes/177213?headless=1
 A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
Você respondeu
 As asserções I e II são proposições verdadeiras,mas a II não é uma justificativa da I.
 A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
 As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
Resposta correta
 As asserções I e II são proposições falsas.
A alternativa está incorreta. As asserções I e II são proposições falsas.
A asserção I é falsa, pois Alan Turing fez um modelo matemático de computação que hoje
chamamos de “Máquina de Turing”. É uma máquina simples que pode ler símbolos no papel, tem
memória interna e pode escrever símbolos. É um modelo bastante simplificado de como fazemos
cálculos, pois permite modelar um estado possível para outro, além de simplificar ações de leitura
e escrita. Em suma, embora seja uma máquina simples, pode executar diversas funções
diferentes.
A asserção II é falsa, pois uma diferença prática importante com os computadores modernos de
hoje é a velocidade. Uma Máquina de Turing é uma ideia abstrata, e a velocidade com que ela
pode ler, escrever e mudar de estado não importa, enquanto na prática, a velocidade com que
nossos computadores podem funcionar é crucial. Outra diferença prática importante é que as
Máquinas de Turing são algoritmos executados isoladamente. Uma vez configuradas para
executar, presume-se que não tocamos nelas e as deixamos em execução, enquanto obviamente
para os computadores modernos de hoje temos muito mais interação.
 
Com base nas informações sobre máquinas de Turing e em sua relação com a inteligência
artificial, avalie as seguintes asserções e a relação proposta entre elas.
I. Uma máquina de Turing é um modelo complexo que pode ler símbolos no papel, tem
memória interna e pode escrever símbolos. É um modelo bastante elaborado de como
fazemos cálculos.
PORQUE
II. Uma semelhança prática importante dos computadores modernos de hoje com as
máquinas de Turing é a velocidade. A velocidade com que elas podem ler, escrever e mudar
de estado é crucial.
Com base nas asserções, assinale a opção correta:
12/06/2024, 09:20Atividade 4: Linguagens Formais e Autômatos
Página 9 de 10https://famonline.instructure.com/courses/35817/quizzes/177213?headless=1
Pergunta 5
0,2 / 0,2 pts
Observe a imagem e leia o texto abaixo:
Considerado o "pai da computação", o britânico Alan Turing formulou, na década de 1930, um
modelo teórico que seria responsável pela criação de conceitos como o algoritmo e o
desenvolvimento dos computadores modernos. Conhecido como Máquina de Turing, o dispositivo
escrevia e interpretava símbolos limitados em 0, 1 e conjunto vazio — basicamente, a
estruturação das linhas de códigos atuais. 
Inspirado pelo filme O Jogo da Imitação, o entusiasta por tecnologia Richard J. Ridel passou seis
meses desenvolvendo uma Máquina de Turing em madeira, em um processo que envolveu
tentativa e erro até o funcionamento do dispositivo [...].
Turing também teve um papel decisivo na Segunda Guerra Mundial. Em uma mansão vitoriana na
cidade de Bletchley, um grupo de gênios contratados pelo serviço de inteligência britânico foi
reunido durante para desvendar o código militar alemão gerado pela Enigma, máquina de
criptografia supostamente impenetrável.
Com a equipe, o matemático começou a trabalhar na produção de uma máquina chamada “a
bomba”. O instrumento identificava pontos fracos da codificação e foi responsável por revelar a
posição dos submarinos alemães. Com as diversas informações interceptadas, o grupo também
12/06/2024, 09:20Atividade 4: Linguagens Formais e Autômatos
Página 10 de 10https://famonline.instructure.com/courses/35817/quizzes/177213?headless=1
Correto!
 
Sua invenção, conhecida como Máquina de Turing, escrevia e interpretava símbolos limitados em 0, 1 e
conjunto vazio.
 
A máquina “Jogo da Imitação” identificava pontos fracos da codificação e era responsável por identificar a
posição de submarinos alemães.
 
Turing formulou um modelo prático usado na criação de conceitos, como algoritmo e desenvolvimento de
computadores modernos.
 
Um grupo de gênios, incluindo Ridel, foi reunido para desvendar o código militar alemão gerado pela Enigma.
 Richard J. Ridel passou seis meses desenvolvendo uma máquina chamada a bomba.
Alternativa correta. A invenção, conhecida como Máquina de Turing, escrevia e interpretava
símbolos limitados em 0, 1 e conjunto vazio – basicamente a estruturação das linhas de códigos
atuais.
Pontuação do teste: 0,6 de 1
pode ter colaborado para encurtar a duração da guerra [...]. 
Fonte: ORIGEM da computação, Máquina de Turing é construída em madeira. Revista Galileu, 13 mar. 2019.
Disponível em: https://revistagalileu.globo.com/Tecnologia/noticia/2018/03/origem-da-computacao-maquina-de-turing-
e-construida-em-madeira.html. Acesso em: 05 ago. 2023.
Alan Turing foi, portanto, considerado o “pai da computação”.
Com base no texto, assinale a alternativa que apresenta informações corretas sobre as
invenções de Turing: