🔍

16-1 Decidability

May 27, 2025

Decidability & Recognisability in Computation

Introduction

  • Focus on which languages are decidable by an algorithm.
  • Not all computational problems can be solved by algorithms.
  • Many computation problems can be represented by deciding language membership.
  • Example: Acceptance problem for deterministic finite automata.

Decidability of Problems Concerning Regular Languages

Theorem 17

  • Acceptance of Strings: Testing if a string ( w ) is accepted by a machine ( M ).
  • Decidability: A language is decidable if a Turing machine can decide membership.
  • Proof:
    • Construct a Turing machine ( T ).
    • Simulate ( M ) on ( w ).
    • If ( M ) accepts, output accept; otherwise, output reject.
  • Conclusion: The language is decidable.

Theorem 18

  • Emptiness of Language: Testing if a language is empty.
  • Proof:
    • Use depth-first search on deterministic finite automaton (DFA).
    • If path to accepting state exists, language is not empty.
    • Turing machine implements DFS starting at start state.
    • Outputs reject if accepting state is found; otherwise, accept.
  • Conclusion: The language is decidable.

Theorem 19

  • Equality of Languages: Comparing languages of two DFAs.
  • Proof:
    • Construct a DFA ( C ) accepting strings in either language but not both.
    • If ( C ) is empty, ( A ) and ( B ) accept the same language.
    • Regular languages closed under union, intersection, complement.
  • Conclusion: The language is decidable.

Decidability of Problems Concerning Context-Free Languages

Theorem 20

  • Derivations in Chomsky Normal Form:
  • Proof:
    • Convert grammar to Chomsky normal form.
    • List derivations of length equal to the string.
    • Accept if derivation generates string, otherwise reject.
  • Conclusion: The language is decidable.

Theorem 21

  • Empty Language from Context-Free Grammar:
  • Proof:
    • Determine if all non-terminals can be removed.
    • Mark terminals.
    • Mark variables that can produce strings without non-terminals.
    • Accept if start variable can generate a string, otherwise reject.
  • Conclusion: The language is decidable.

Recognisability of Problems Concerning Turing Languages

Theorem 22

  • Recognisability:
  • Proof:
    • Construct a Turing machine to recognize language.
    • Simulate another Turing machine ( U ).
    • Accept if ( U ) accepts; reject if ( U ) rejects.
    • ( U ) could run indefinitely, only recognises not decides.
  • Conclusion: The language is recognisable, not necessarily decidable.