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