Recognizable Flashcards
1
Q
A_TM
A
RE: we can simulate M on w
Not co-RE detecting non-acceptance requires resolving an infinite loop
2
Q
HALT_TM
A
RE: we can simulate M on w
Not co-RE: detecting non-acceptance requires resolving an infinite loop
3
Q
E_TM
A
Not RE
Co-RE: if a machine does accept something, we can eventually detect that
4
Q
EQ_TM
A
neither: comparing two infinite sets of accepted strings is undecidable
5
Q
101_TM
A
RE: we can check whether M(101) halts and accepts
Not Co-RE
