Post Correspondence problem PCP
Halting problem for FRACTRAN programs FRACTRAN_HALTING
- FRACTRAN_HALTING is undecidable
- HaltTM_1 reduces to FRACTRAN_HALTING
Satisfiability of elementary, square, and uniform Diophantine constraints H10C_SAT, H10SQC_SAT, and H10UC_SAT
- H10C_SAT, H10SQC_SAT, and H10UC_SAT are undecidable
Halting problem for one counter machines CM1_HALT
- HaltTM 1 reduces to CM1_HALT
- CM1_HALT is undecidable
Solvability of finite multiset constraints FMsetC_SAT
- FMsetC_SAT is undecidable
Halting problem for the weak call-by-value lambda-calculus HaltL
- HaltL is undecidable
Halting problem for multi-tape and single-tape Turing machines HaltMTM and HaltTM 1
Halting problem for a fixed, universal, single-tape, binary Turing machine (HaltUTM)
- HaltUTM is undecidable
Halting problem for (micro-programmed) Turing machines with a PC counter
Halting problem for binary stack machines BSM_HALTING
- BSM_HALTING is undecidable
Halting problem for Minsky machines
Basic First-Order Logic
Undecidability
Halting problem for Minsky machines
Halting problem for Minsky machines MM_HALTING
- Halt_murec is undecidable
- HaltL is enumerable
Halting problem for binary stack machines BSM_HALTING
Halting problem for simple binary single-tape Turing machines HaltKOSBTM