Der findes et hel hav af turingmaskiner, CFG'ere, DFA'ere, NFA'ere osv. , som kan benyttes til reducering.
Her er dem, som jeg end til videre har set:
Regular_TM (Uafgørbart)
EQ_TM (Uafgørbart)
E_TM (Uafgørbart)
A_TM (Uafgørbart)
HALT_TM (Uafgørbart)
A_LBA (Afgørbart)
E_LBA (Uafgørbart)
ALL_CFG (Uafgørbart)
EQ_CFG (Afgørbart)
E_CFG (Afgørbart)
A_CFG (Afgørbart)
A_REX (Afgørbart)
A_NFA (Afgørbart)
A_DFA (Afgørbart)
EQ_DFA (Afgørbart)
PCP (Uafgørbart)
Ingen kommentarer:
Send en kommentar