.. include:: global.rst

===============================
Formalisms for Computability
===============================

Overview
========
Formalisms for computability are theoretical models used to define what problems
can be solved by a computer. These models help us understand the limits of
computation and form the foundation of computer science.

Python, as a programming language, is considered *Turing complete*, meaning it
can simulate any of these formalisms (given enough time and memory).

--------------------------------------------------

Key Formalisms
==============

1. Finite Automata (FA)
----------------------
- Abstract machines with a finite number of states.
- Used to recognize *regular languages*.
- No memory beyond current state.

Types:
- Deterministic Finite Automaton (DFA)
- Nondeterministic Finite Automaton (NFA)

Python Connection:
- Can be implemented using classes and state transitions.
- Useful for pattern matching and lexical analysis.

Example Idea:
- Represent states as dictionary keys
- Transitions as nested dictionaries

--------------------------------------------------

2. Pushdown Automata (PDA)
--------------------------
- Extends finite automata with a *stack*.
- Recognizes *context-free languages*.
- Can handle nested structures (e.g., parentheses).

Python Connection:
- Use Python lists as stacks (append/pop).
- Useful in parsing expressions or compilers.

Example:
- Balanced parentheses checker

--------------------------------------------------

3. Turing Machines (TM)
-----------------------
- Most powerful formalism.
- Uses an infinite tape and a read/write head.
- Can simulate any algorithm.

Key Components:
- Tape (memory)
- Head (reads/writes symbols)
- State register
- Transition function

Python Connection:
- Simulated using lists or dictionaries for the tape.
- Demonstrates that Python can compute anything computable.

--------------------------------------------------

4. Lambda Calculus
------------------
- A mathematical system based on function abstraction and application.
- No variables in the traditional sense, only functions.

Core Concepts:
- Functions
- Application
- Substitution

Python Connection:
- Python supports lambda functions:
  
  Example:
    lambda x: x + 1

- Functional programming concepts in Python mirror lambda calculus ideas.

--------------------------------------------------

5. Recursive Functions
----------------------
- Functions defined in terms of themselves.
- Basis for many computability definitions.

Python Connection:
- Directly supported via recursion.

Example:
    def factorial(n):
        if n == 0:
            return 1
        return n * factorial(n - 1)

--------------------------------------------------

Church-Turing Thesis
====================
- States that any function that can be computed algorithmically can be computed
  by a Turing Machine.
- Implies all formalisms above are equivalent in computational power.

Python Implication:
- Python can implement any algorithm that a Turing Machine can.

--------------------------------------------------

Decidability and Undecidability
===============================

Decidable Problems:
-------------------
- Problems for which an algorithm always produces a correct yes/no answer.

Undecidable Problems:
---------------------
- Problems that no algorithm can solve in all cases.

Example:
- Halting Problem: determining if a program will stop or run forever.

Python Connection:
- You cannot write a Python program that solves the halting problem for all programs.

--------------------------------------------------

Summary
=======
- Formalisms define *what is computable*.
- Key models:
  - Finite Automata (limited memory)
  - Pushdown Automata (stack memory)
  - Turing Machines (unbounded memory)
- All equivalent in power (with sufficient resources).
- Python is Turing complete and can simulate all of them.
- Some problems are fundamentally unsolvable by any program.

--------------------------------------------------

Quick Comparison Table
=====================

+----------------------+----------------------+----------------------+
| Formalism            | Memory               | Languages Recognized |
+======================+======================+======================+
| Finite Automata      | None (state only)    | Regular              |
+----------------------+----------------------+----------------------+
| Pushdown Automata    | Stack                | Context-Free         |
+----------------------+----------------------+----------------------+
| Turing Machine       | Infinite Tape        | Recursively Enumerable|
+----------------------+----------------------+----------------------+