Halting problem for one counter machines CM1_HALT
- CM1_HALT is undecidable
- HaltTM 1 reduces to CM1_HALT
Satisfiability of elementary, square, and uniform Diophantine constraints H10C_SAT, H10SQC_SAT, and H10UC_SAT
- H10C_SAT, H10SQC_SAT, and H10UC_SAT are undecidable
- Intensional Axioms
Extensional Model of Z via Class Extensionality
Halting problem for FRACTRAN programs FRACTRAN_HALTING
- FRACTRAN_HALTING is undecidable
- HaltTM_1 reduces to FRACTRAN_HALTING
Halting problem for the call-by-value lambda-calculus HaltL
- HaltL is undecidable
Halting problem for Minsky machines
Halting problem for two counter Minsky machines MM2_HALTING
- MM2_HALTING is undecidable
Halting problem for Minsky machines
Halting problem for Minsky machines MM_HALTING
- Halt_murec is undecidable
Post Correspondence problem PCP
- PCP is undecidable
- HaltTM 1 reduces to PCP
Solvability of finite multiset constraints FMsetC_SAT
- FMsetC_SAT is undecidable
Halting problem for binary stack machines BSM_HALTING
- BSM_HALTING is undecidable
Halting problem for binary stack machines BSM_HALTING
Halting problem for simple binary single-tape Turing machines HaltSBTM
- HaltSBTM is undecidable
Halting problem for multi-tape and single-tape Turing machines HaltMTM and HaltTM 1
- HaltMTM and HaltTM 1 are undecidable