Atividade Objetiva 4 - Linguagens Formais e Autômatos - Nota 0.6 de 1.0

Prévia do material em texto

Atividade 4
Iniciado: 22 mai em 11:31
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.
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
A+
A
A-
NOTA: 0.6 de 1.0

Pergunta 2 0,2 pts
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:
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.
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.
Richard J. Ridel passou seis meses desenvolvendo uma máquina chamada a bomba.
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.
A+
A
A-

Pergunta 3 0,2 pts
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:
Em 1928, o conceito de um algoritmo de computador já havia sido criado por David Hilbert.
O Entscheidungsproblem de Hilbert, declarado em 1928, é o problema de decisão para teorias de primeira ordem.
Turing mostrou decisivamente que tal algoritmo existia e, no processo de fazê-lo, habilmente lançou a era do
computador.
Devido à sua complexidade, a máquina de Turing pode simular qualquer algoritmo de computador, por mais
complicado que ele seja.
O Entscheidungsproblem questiona se há um algoritmo que determine a veracidade de uma afirmação em
determinados modelos de uma teoria.
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
A+
A
A-
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.
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
umamá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:
A+
A
A-

Pergunta 4 0,2 pts
II e III, apenas.
II, III e IV, apenas.
I e IV, apenas.
III e IV, apenas.
I, II e III, apenas.
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-

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:
III e IV, apenas.
I e II, apenas.
I, II e IV, apenas.
II e III, apenas.
I, III e IV, apenas.
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.
A+
A
A-
Salvo em 10:36 
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á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:
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
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 verdadeira, e a II é uma proposição falsa.
Enviar teste
A+
A
A-