Acerca dos conceitos de Computabilidade e Máquinas de Turing, assinale a alternativa INCORRETA. A Todo problema que está na classe P também está na...

Vamos analisar cada alternativa: A) Todo problema que está na classe P também está na classe NP - CORRETO. Todos os problemas em P também estão em NP. B) Seja L uma linguagem recursivamente enumerável, se o complemento de L for recursivamente enumerável, então L é uma linguagem recursiva - INCORRETO. A afirmação está incorreta, pois nem toda linguagem recursivamente enumerável tem seu complemento recursivamente enumerável. C) Segundo a Tese de Church, a capacidade de computação representada pela máquina de Turing é o limite máximo que pode ser atingido por qualquer modelo de computação - CORRETO. A Tese de Church afirma que a máquina de Turing é um modelo de computação universal. D) Um problema X é NP-completo quando X pertence à classe NP e, adicionalmente, X é redutível em tempo polinomial para qualquer outro problema Y na classe NP - CORRETO. Essa é a definição de NP-completude. E) A união de duas linguagens recursivas é uma linguagem recursiva - CORRETO. A união de duas linguagens recursivas é uma linguagem recursiva. Portanto, a alternativa INCORRETA é a letra B) Seja L uma linguagem recursivamente enumerável, se o complemento de L for recursivamente enumerável, então L é uma linguagem recursiva.