L = {T | T é uma máquina que reconhece {00, 01}} Prove L é indecidível - máquinas de redução, decidíveis

L = {<T> | T é uma máquina que reconhece {00, 01}}

Prove L é indecidível.

Estou realmente tendo dificuldades até mesmo em entender a redução para usar aqui.

Eu não estou pedindo almoço grátis, apenas um empurrão na direção certa.

Respostas:

Uma aplicação direta do teorema de Rice permitirá que você prove isso sem fazer nenhum trabalho.

Algumas máquinas de Turing reconhecem {00, 01}. Alguns não. A diferença é semântica na medida em que tem a ver com as cordas aceitas, não a estrutura do autômato. Assim, pelo teorema de Rice, este conjunto é indecidível.