Questão-1-Linguagens-formais-e-autômatos

Prévia do material em texto

Questão 01 Linguagens formais e autômatos 
 
Leia o trecho a seguir: 
“Em 1936, Alonzo Church demonstrou a tese de Church, na qual afirmou que qualquer 
função computável poderia ser processada através de uma máquina de Turing, dessa 
forma, se criou a premissa de que sempre existirá um procedimento definido, no qual 
uma máquina de Turing processará uma função computacional”. 
 
MENEZES, P. B. Linguagens formais e autômatos. São Paulo: Sagah, 2015. p. 159. 
 
Considerando o excerto apresentado sobre as propriedades da máquina de Turing, 
analise as afirmativas a seguir. 
 
I. É impossível apresentar formalmente se a máquina de Turing é, de fato, o modelo 
mais genérico de dispositivo computacional. 
II. Todos os modelos conhecidos propostos após a máquina de Turing possuem, no 
máximo, a mesma capacidade computacional da máquina de Turing. 
III. A tese de Church não foi assumida como uma hipótese para toda a teoria da 
computação, razão pela qual não é empregada. 
IV. A máquina de Turing é um autômato cuja fita possui tamanho máximo e pode ser 
usada simultaneamente como dispositivo de entrada e de saída. 
 
Está correto o que se afirma em: 
 
Resposta: 
 
Vamos analisar cada uma das afirmativas: 
 
I. É impossível apresentar formalmente se a máquina de Turing é, de fato, o modelo 
mais genérico de dispositivo computacional. 
 
- Esta afirmativa está correta. Não é possível provar formalmente que a máquina de 
Turing é o modelo mais genérico de dispositivo computacional. Existem outros modelos 
teóricos equivalentes, como a Máquina de Registro, que também são considerados 
modelos genéricos. 
 
II. Todos os modelos conhecidos propostos após a máquina de Turing possuem, no 
máximo, a mesma capacidade computacional da máquina de Turing. 
 
- Esta afirmativa está correta. A máquina de Turing é um modelo universal de 
computação, o que significa que qualquer função computável pode ser calculada por 
uma máquina de Turing. Outros modelos posteriores, como máquinas de registro, são 
equivalentes em termos de capacidade computacional. 
 
III. A tese de Church não foi assumida como uma hipótese para toda a teoria da 
computação, razão pela qual não é empregada. 
 
- Esta afirmativa está incorreta. A tese de Church, que afirma que qualquer função 
computável pode ser processada por uma máquina de Turing, é um princípio 
fundamental na teoria da computação e é amplamente empregada na área. 
 
IV. A máquina de Turing é um autômato cuja fita possui tamanho máximo e pode ser 
usada simultaneamente como dispositivo de entrada e de saída. 
 
- Esta afirmativa está incorreta. A máquina de Turing possui uma fita infinita, não com 
tamanho máximo, e pode ser usada tanto para entrada quanto para saída de dados. 
 
Portanto, as afirmativas corretas são I e II.