6. Considere dois problemas de decisão, P1 e P2 onde P1 é indecidivel e P2 é decidivel. Além disso, existem outros dois problemas de decisão, P3 e P4 cuja decidibilidade ainda não foi possivel determinar. Suponha que as seguintes reduções foram corretamente estabelecidas: I. Do problema P1 para P3 II. Do problema P4 para P1 III. Do problema P4 para P2 Com base nessas informações é possivel afirmar que: Não é possivel determinar a decidibilidade de ambos os problemas. A decidibilidade de P3 é incerta, mas a de P4 é decidivel. P3é um problema indecidivel P4 é um problema decidivel. Tanto P3 quanto P4 são indecidiveis. P3 é indecidivel, mas não se pode afirmar nada sobre a decidibilidade de P_(4)

Question

Pergunta

6. Considere dois problemas de decisão, P1 e P2 onde P1 é indecidivel e P2 é decidivel. Além disso, existem outros dois problemas de decisão, P3 e P4 cuja decidibilidade ainda não foi possivel determinar. Suponha que as seguintes reduções foram corretamente estabelecidas: I. Do problema P1 para P3 II. Do problema P4 para P1 III. Do problema P4 para P2 Com base nessas informações é possivel afirmar que: Não é possivel determinar a decidibilidade de ambos os problemas. A decidibilidade de P3 é incerta, mas a de P4 é decidivel. P3é um problema indecidivel P4 é um problema decidivel. Tanto P3 quanto P4 são indecidiveis. P3 é indecidivel, mas não se pode afirmar nada sobre a decidibilidade de P_(4)

Answer 1

resposta correta é: P3 é indecidível, mas não se pode afirmar nada sobre a decidibilidade de P4.<br /><br />Explicação: Com base nas reduções fornecidas, podemos afirmar que P1 é indecidível e P2 é decidível. Além disso, P3 é reduzido a P1, o que significa que se P1 é indecidível, então P3 também é indecidível. No entanto, não podemos afirmar nada sobre a decidibilidade de P4, pois não há informações suficientes sobre essa redução. Portanto, a única afirmação que podemos fazer é que P3 é indecidível, mas não podemos afirmar nada sobre a decidibilidade de P4.

Pergunta

Solução

Responder