Atividade Objetiva 4 - Linguagens Formais e Autômatos - Nota 0 8 de 1 0

Prévia do material em texto

Atividade 4
Iniciado: 11 mai em 11:41
Instruções do teste

Pergunta 1 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:
[...] 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 [...]. 
A+
A
A-
5/11/25, 11:42 AM Teste: Atividade 4
https://famonline.instructure.com/courses/44680/quizzes/214796/take 1/8

Pergunta 2 0,2 pts
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.
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.
Devido à sua complexidade, a máquina de Turing pode simular qualquer algoritmo de computador, por mais
complicado que ele seja.
Observe a imagem e leia o texto abaixo:
A+
A
A-
5/11/25, 11:42 AM Teste: Atividade 4
https://famonline.instructure.com/courses/44680/quizzes/214796/take 2/8
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 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:
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.
Richard J. Ridel passou seis meses desenvolvendo uma máquina chamada a bomba.
Um grupo de gênios, incluindo Ridel, foi reunido para desvendar o código militar alemão gerado pela Enigma.
Sua invenção, conhecida como Máquina de Turing, escrevia e interpretava símbolos limitados em 0, 1 e conjunto
vazio.
Turing formulou um modelo prático usado na criação de conceitos, como algoritmo e desenvolvimento de
computadores modernos.
A+
A
A-
5/11/25, 11:42 AM Teste: Atividade 4
https://famonline.instructure.com/courses/44680/quizzes/214796/take 3/8

Pergunta 3 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.
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áquinasde
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:
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
A+
A
A-
5/11/25, 11:42 AM Teste: Atividade 4
https://famonline.instructure.com/courses/44680/quizzes/214796/take 4/8

Pergunta 4 0,2 pts
As asserções I e II são proposições falsas.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
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.
A+
A
A-
5/11/25, 11:42 AM Teste: Atividade 4
https://famonline.instructure.com/courses/44680/quizzes/214796/take 5/8

Pergunta 5 0,2 pts
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:
II e III, apenas.
I, III e IV, apenas.
I e II, apenas.
I, II e IV, apenas.
III e IV, apenas.
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 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.
A+
A
A-
5/11/25, 11:42 AM Teste: Atividade 4
https://famonline.instructure.com/courses/44680/quizzes/214796/take 6/8
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:
I e IV, apenas.
II, III e IV, apenas.
I, II e III, apenas.
II e III, apenas.
A+
A
A-
5/11/25, 11:42 AM Teste: Atividade 4
https://famonline.instructure.com/courses/44680/quizzes/214796/take 7/8
Salvo em 11:42 
III e IV, apenas.
Enviar teste
A+
A
A-
5/11/25, 11:42 AM Teste: Atividade 4
https://famonline.instructure.com/courses/44680/quizzes/214796/take 8/8