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.
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.
Lista de comentários
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.