2. Pushdown Automata (PDA)

  1. Pushdown Automata (PDA):

A more powerful automaton than finite automata, which includes a stack to provide additional memory. This enables the PDA to recognize context-free languages (like balanced parentheses or programming language syntax).

    • Description: A finite automaton with a stack for memory.
    • Applications: Parsing context-free languages.
    • Example: Balanced parentheses.
  1. Turing Machines (TM):

A theoretical machine that can simulate any algorithm. It has an infinite tape (memory) and a head that moves left or right over the tape, reading and writing symbols. The Turing machine is a central concept in the theory of computability and can simulate any physical computer.

    • Description: A theoretical machine with an infinite tape and a read/write head.
    • Applications: Defining the limits of computation.
    • Example: Solving any computable problem.

Computability Theory

Computability theory explores the limits of what can be computed by any algorithm or machine.

Computability theory deals with understanding which problems can be solved by computers and which cannot.

  • Decidable Problems: Problems that can be solved by an algorithm in a finite amount of time (i.e., the machine always halts with an answer).
  • Undecidable Problems: Problems for which no algorithm exists that can solve all instances of the problem. A classic example is the Halting Problem, which asks whether a given program will eventually halt (finish execution) or run forever. Alan Turing proved that no algorithm can decide the halting problem for all possible programs.
Church-Turing Thesis: A hypothesis stating that anything computable by a human using an algorithm can also be computed by a Turing machine. It provides a foundational concept in theoretical computer science.