Computability Overview

• Focus on languages, the Chomsky hierarchy, Turing machines, and undecidable problems.

• Importance of understanding the limitations of computation to avoid focusing on unsolvable problems.

References

• Introduction to Languages and the Theory of Computation by John Martin, McGraw-Hill publishing.

• Introduction to the Theory of Computation by Michael Sipser, 2012 (Sections 3.2 and 3.3).

• Introduction to Automata Theory, Languages, and Computation by John Hopcroft, Rajeev Motwani, and Jeffrey Ullman, Addison-Wesley.

• Introduction to Computer Theory (second edition) by Daniel Cohen, John Wiley & Sons.

• Gödel’s Proof (revised edition) by Ernest Nagel and James R. Newman, New York University Press, 2001.

Motivation

• Early 20th-century mathematicians like Gödel, Turing, and Church identified inherent limits to what can be solved computationally.

• One fundamental unsolvable problem is determining the truth of mathematical statements.

• This led to the development of theoretical models (Turing machines) to investigate the boundaries of computation.

• Two primary themes in study:

  • Decidability of problems: Some problems can be solved algorithmically, while others cannot.

  • Complexity of problems: Some algorithmic solutions exist theoretically but may not solve in a feasible time.

• Understanding unsolvability is vital for recognizing when problems need simplification or alteration to become solvable algorithmically.

Languages

## Hierarchy of Languages

• The machine language hierarchy consists of:

  • Regular languages ⊆ Context-free languages ⊆ Context-sensitive languages ⊆ Recursively enumerable languages.

  The Chomsky Hierarchy

• Proposed by Noam Chomsky (2015):

  • Type 0: Recursively enumerable - Turing Machine.

  • Type 1: Context-sensitive - Turing machine with bounded tape (linear bounded automaton).

  • Type 2: Context-free - Non-deterministic pushdown automaton.

  • Type 3: Regular - Finite state automaton.

  Turing Machines as Language Acceptors

• A Turing machine (TM) can have three outcomes for an input:

  • Accept

  • Reject and halt

  • Reject by entering an infinite loop.

• The TM accepts an input string if it halts in an accepting state after a finite number of steps.

• The language of a Turing machine T, denoted as L(T), comprises the set of strings accepted by T.

• For example, the language generated by the pattern x^n y^n z^n is Turing acceptable for any natural number n.

  TM Languages (Formal Definitions)

• Language L over alphabet Σ:

  • A language is recursively enumerable (or recognisable, or semi-decidable) if a Turing machine T exists that:

    • Accepts every word in L

    • Rejects or loops forever on words not in L.

• Formal representation:

  • Accepting Turing Machine: $ext{accept}(T) = L$

  • Rejecting/TM that enters loop: $ext{reject} + ext{loop}(T) = L'$

  • Thus, there is no requirement for T to halt for strings not in the language.

  Type 0 Grammar

• Type 0 Grammar has no restrictions on its rewrite rules and generates recursively enumerable languages.

• Also known as Unrestricted grammar or Phrase structure grammar.

  Example 1: Non-context-free Grammar

• Grammar L(T):

  • Production Rules:

    • Prod 1: S → XS | λ (any number of X)

    • Prod 2: X → a X | a (X can be any string of a > 0)

    • Prod 3: aaa X → ba (any three a's and an X, can be transformed to ba)

  • Generates words that cannot be created by a context-free grammar.

  • Derivation:

    • $S <br>ightarrow XXXXXXS$

    • Further reductions show how other strings are derived.

• Reasons why it is not context-free or regular grammar relate to the specific patterns of occurrences.

  Example 2: Context-sensitive Grammar

• Grammar L(T):

  • Production Rules:

    • Prod 1: S → abXSc | λ

    • Prod 2: bXa → abX

    • Prod 3: bXc → bc

    • Prod 4: bXb → bbX

  • Generates strings of the form {a^n b^n c^n | n ≥ 0}.

  • Able to derive examples like abc and aabbcc.

Decidability

## Definition of Decidability

• Language L is decidable (or recursive, computable) if:

  • A Turing Machine exists that halts on all inputs.

  • Accepts every string in L and rejects strings not in L.

• Recognizable languages can be accepted but may enter infinite loops for strings not in L.

• Several alternative systems (Post’s production system, recursive functions, Church’s λ calculus) equate to this in computational power.

  Church-Turing Thesis (1936)

• Universal Turing Machine (UTM) can simulate any Turing machine on given input.

• A decently intuitive definition: A language is decidable if an algorithm can determine membership and halts on inputs.

• Thesis states: Any algorithmic process can be performed by a UTM.

• No more powerful formal system has been identified than the UTM, making the Church-Turing thesis plausible.

• Some problems are algorithmically solvable; others are not.

  Importance of Studying Undecidability

• Understanding computational limits is crucial to avoid ineffectual problem-solving efforts.

• A problem is decidable if it can be represented through a decidable language; undecidable if it cannot.

• Non-decidable problems cannot be computed on any contemporary computer.

  Implications of the Church-Turing Thesis

• Theoretical basis of digital computing derived from UTM; its limits reflect in modern systems, which cannot handle undecidable problems.

• Impacts on cryptographic protocols and complexity of cryptographic algorithms, important for system security.

The Halting Problem

## Description

• Halting Problem: Given a program P and input I, can we determine if P halts on I?

  • Turing proved that no such algorithm exists.

• The Halting Theorem: Declares that the halting problem is undecidable.

  Proof of the Halting Theorem (by Contradiction)

• Assume an algorithm H exists for the halting problem.

• Define an algorithm A(Q) that:

  • Loops forever if Q(Q) halts

  • Halts otherwise.

• Consider A(A):

  • Case 1: If H(A, A) = yes, then A(A) should halt, but will loop forever — contradiction.

  • Case 2: If H(A, A) = no, then A(A) should not halt, which leads to it halting — contradiction.

• Hence, H cannot exist.

Gödel and Turing

## Overview

• Gödel's Incompleteness Theorem (1931): In any consistent formal system encompassing arithmetic, there exist true propositions that cannot be proven within that system.

• Turing (1937): Responded negatively to Hilbert's problem, demonstrating the absence of a systematic algorithmic approach for determining the termination of arbitrary Turing machines.

• Their findings highlight distinct yet interconnected aspects of logical and mathematical unsolvability.

  Recap of Computability

• Chomsky hierarchy: Different language classes defined by grammar types.

• A language is decidable if solvable by a Turing machine that halts on all inputs.

• The Halting Problem exemplifies undecidable problems.

• The Church-Turing thesis affirms the executable nature of all algorithmic processes by the UTM.

Turing Quiz (from Sipser)

• Which is true about Alan Turing?

  1. Broke codes for England during WW2.

  2. Worked in AI.

  3. Worked in Biology.

  4. Was imprisoned for being gay.

  5. Appears on a British banknote.

Exam Questions

## Sample Questions (2022-23)

1. What does the Church-Turing thesis state? Explain the implications and limitations regarding electronic digital computers. (5 marks)

2. Define undecidable problems with examples. (5 marks)

   Hints for Answers

3. The Church-Turing thesis articulates that all algorithmic processes can be executed by a UTM. Its limitation lies in the adherence of digital computers to these same constraints, preventing them from resolving undecidable issues.

4. An undecidable problem is one where it is unknown if a corresponding algorithm will yield a result. Examples include the Halting problem and Post's problem.

   Turing Machine Design Exercises

5. Parity Bit Calculation: Design a Turing Machine that adds a parity bit to a binary string, outputting the string followed by a 1 for odd parity, 0 for even parity.

6. Subtraction of Unary Integers: Design a Turing Machine that subtracts two unary integers represented on the Turing tape.

7. Detailed steps and state transition diagrams will need to be outlined for full marks.