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.