Sobre a máquina de Turing, analise as seguintes afirmações: Uma máquina de Turing com múltiplas fitas pode reconhecer qualquer linguagem recursivamente enumerável. II. Para refutar a Hipótese de Church, basta apresentar uma modificação da máquina de Turing que comprovadamente tenha mais poder computacional que uma máquina de Turing determinística. III. Por padrão, uma máquina de Turing determinística pode alterar diversos pontos da fita em cada transição e é capaz de transferir sua atenção para mais de uma posição da fita em cada argumento da função de transição. Quais(is) dessas afirmações está(ão) corret(as)?

Alternativa C

A questão aborda os fundamentos teóricos das Máquinas de Turing, um modelo matemático essencial para o estudo da computabilidade. Vamos analisar cada afirmativa detalhadamente para identificar quais estão corretas.

Análise dos Enunciados

Afirmativa I: Correta

"Uma máquina de Turing com múltiplas fitas pode reconhecer qualquer linguagem recursivamente enumerável."

Esta afirmação está correta. Embora uma Máquina de Turing Multifita seja estruturalmente diferente da versão clássica de fita única (possuindo cabeçotes independentes), ela possui o mesmo poder computacional. Isso significa que qualquer linguagem que possa ser reconhecida por uma multifita também pode ser reconhecida por uma unifita. Ambas aceitam exatamente a classe das Linguagens Recursivamente Enumeráveis (Tipo 0 na Hierarquia de Chomsky).

Afirmativa II: Correta

"Para refutar a Hipótese de Church, basta apresentar uma modificação da máquina de Turing que comprovadamente tenha mais poder computacional que uma máquina de Turing determinística."

Esta afirmação está correta do ponto de vista lógico. A Hipótese de Church-Turing postula que toda função efetivamente calculável é computável por uma Máquina de Turing. Se fosse demonstrada a existência de um modelo de computação (uma "modificação") capaz de resolver problemas que uma Máquina de Turing não consegue (como o problema da parada, por exemplo), isso provaria que a hipótese é falsa. Até hoje, nenhum tal modelo foi encontrado na prática física.

Afirmativa III: Incorreta

"Por padrão, uma máquina de Turing determinística pode alterar diversos pontos da fita em cada transição e é capaz de transferir sua atenção para mais de uma posição da fita em cada argumento da função de transição."

Esta afirmação é falsa. A definição padrão de uma Máquina de Turing Determinística impõe restrições rígidas:

• O cabeçote lê e escreve apenas um símbolo por vez.
• O movimento é limitado a uma célula à esquerda ou à direita (movimento unitário).
• O estado muda para um único novo estado.

Se uma máquina pudesse escrever em múltiplos pontos simultaneamente ou mover-se para posições arbitrárias distantes, seria um modelo mais forte que o padrão, mas não corresponde à definição básica utilizada na teoria da computação.

Conclusão

Com base na análise acima:

• A afirmativa I é verdadeira.
• A afirmativa II é verdadeira.
• A afirmativa III é falsa.

Portanto, a combinação correta é I e II, correspondendo à alternativa C.