Shared flowchart

Software · L5 · Decidability Hierarchy

Sign in to clone

The relationship between decidable, Turing-recognisable, and co-Turing-recognisable languages, with HALT and its complement placed relative to each class.

by @openstemUpdated Software
All languages over Σ*Turing-recognisable (some TM halts+accepts on every member)Co-Turing-recognisable (complement is recognisable)Decidable = RE ∩ co-RE (Post's theorem)HALT: recognisable but NOT co-recognisablecomplement of HALT: co-recognisable but NOT recognisablee.g. is L(M) empty? regular? equal to L(M')? — all undecidableRice's theorem: no non-trivial semantic property of L(M) is decidable

We use privacy-friendly product analytics (no session recording, PII masked) to improve OpenStem. Load analytics? Privacy Policy