UoL CS Notes
Menu

Decidable & Undecidable Languages

COMP218 Lectures

Checking Decidability with a TM

To check whether a DFA is decidable, we can use a Turing machine.

For this we need to simulate the DFA $D$ with the input $w$ on the turing machine:

  • If the simulation ends in an accepting state then the Turing machine accepts.
    • Otherwise reject.

To perform the simulation we complete the following:

  1. Put markers on the start state of $D$ and the first symbol of $w$.
  2. Until the marker for $w$ reaches the last symbol:
    • Update both markers.
  3. If state marker is on accepting state, accept.
    • Else reject.

We can also use our intuition to find decidability.

Decidability

  • Not all CFGs are decidable.
  • Entscheidungs problem states that there is not algorithm to decide whether a given statement is provable from the axioms using the rules of first-order logic.