Atividade 4 - Entrega 6 jun

Prévia do material em texto

Atividade 4
Entrega 6 jun em 23:59 Pontos 1 Perguntas 5 Disponível 17 fev em 23:59 - 6 jun em 23:59 Limite de tempo Nenhum Tentativas permitidas 2
Instruções
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.
Este teste foi travado 6 jun em 23:59.
Histórico de tentativas
Tentativa	Tempo	Pontuação
MAIS RECENTE	Tentativa 1	2 minutos	0,6 de 1
Pontuação desta tentativa: 0,6 de 1
Enviado 23 mar em 10:55
Esta tentativa levou 2 minutos.
 
Pergunta 1
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.
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:
 Turing mostrou decisivamente que tal algoritmo existia e, no processo de fazê-lo, habilmente lançou a era do computador. 
 Resposta certa ->> O Entscheidungsproblem de Hilbert, declarado em 1928, é o problema de decisão para teorias de primeira ordem. 
 Devido à sua complexidade, a máquina de Turing pode simular qualquer algoritmo de computador, por mais complicado que ele seja. 
Esta alternativa está incorreta, pois apesar de sua simplicidade, a máquina de Turing pode simular qualquer algoritmo de computador, por mais complexo que seja. Alan Turing demonstrou que tudo o que pode ser razoavelmente considerado computado por um ser humano usando um procedimento padrão pode ser computado pela máquina de Turing.
A alternativa correta é “O Entscheidungsproblem de Hilbert, declarado em 1928, é o problema de decisão para teorias de primeira ordem”.
 O Entscheidungsproblem questiona se há um algoritmo que determine a veracidade de uma afirmação em determinados modelos de uma teoria. 
 Em 1928, o conceito de um algoritmo de computador já havia sido criado por David Hilbert. 
 
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.
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ímbolo e 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:
Correto!- >> I, II e IV, apenas. 
 I e II, apenas. 
 III e IV, apenas. 
 I, III e IV, 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á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:
 II, III e IV, apenas. 
 I e IV, apenas. 
 I, II e III, apenas. 
Correto! - >> III e IV, apenas. 
 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.
Pontuação do teste: 0,6 de 1disponí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:
 II, III e IV, apenas. 
 I e IV, apenas. 
 I, II e III, apenas. 
Correto! - >> III e IV, apenas. 
 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.
Pontuação do teste: 0,6 de 1