Problem  Description  Computability  Notes


A_{FA}  (i,j) ⊆ N × N s.t. FA_{i} accepts j  decidable  run DFA 
E_{FA}  i ⊆ N s.t. L(FA_{i}) = ∅  decidable  nondet guess element in complement 
EQ_{FA}  (i,j) ⊆ N × N s.t. L(FA_{i}) =L(FA_{j})  decidable  emptiness of symmetric difference 
A_{CFG}  (i,j) ⊆ N × N s.t. PDA_{i} accepts j  decidable  Chomsky Normal Form 
E_{CFG}  i ⊆ N s.t. L(CFG_{i}) = ∅  decidable  marking algorithm 
X  x ∉ X, where X is decidable  decidable 
coEQ_{CFG}  (i,j) ∉ EQ_{CFG}  RE  ∃ x s.t. (x,i) ∈ A_{CFG} etc 
EQ_{CFG}  (i,j) ⊆ N × N s.t. L(PDA_{i}) = L(PDA_{j})  coRE  because not recursive 
A_{TM}  (i,j) ⊆ N × N s.t. M_{i}(j) halts accepts  RE  run j on M_{i} 
coA_{TM}  (i,j) ∉ HALT  coRE  because not recursive 
HALT  (i,j) ⊆ N × N s.t. M_{i}(j) halts  RE  run j on M_{i} 
coHALT  (i,j) ∉ HALT  coRE  because not recursive 
E_{TM}  i ⊆ N s.t. L(M_{i}) = ∅  coRE  Rice's theorm 
coE_{TM}  i ∉E_{TM}  RE  ∃ x s.t. (x,i) ∈ A_{TM} 
EQ_{TM}  (i,j) ⊆ N × N s.t. L(M_{i})=L(M_{j})  nonRE
 ɸ_{i,j}(x)=(x!=j)?F:M_{i}(j), solve EQ(ɸ,∅) 
coEQ_{TM}  (i,j) ∉ EQ_{TM }  nonRE
 ɸ_{i,j}(x)=(x!=j)?T:M_{i}(j), solve NEQ(ɸ,Ʃ^{*}) 