A computational exploration of Turing Machines and Cellular Automata
This project implements core concepts from Theory of Computation, focusing on how computation emerges from simple formal systems.
It demonstrates both the power and limits of computation using classical theoretical models.
- Turing Machines as a universal model of computation
- Busy Beaver problem and undecidability
- Conway’s Game of Life and emergent computation
- Langton’s Ant as a chaotic deterministic system
- Construction of logic gates using cellular automata
A zero-player game where simple local rules generate highly complex global behavior. Patterns such as gliders and oscillators demonstrate computational universality.
A simple agent-based system that evolves from chaotic motion into structured highways, illustrating emergence of order from randomness.
Part 1 - Busy Beaver/
Turing Machine simulator
Unary arithmetic (add, multiply)
Busy Beaver exploration
Part 2 - GoL & Langton's Ant/
Conway’s Game of Life
Langton’s Ant
Logic gates using gliders
pip install -r requirements.txt
Turing Machines:
python test_turing_machine_example1.py
Game of Life:
python test_gameoflife_glider.py
- Computation can be modeled using abstract machines
- Universality of Turing Machines
- Emergence of complexity from simple rules
- Equivalence of different computational models
- Physical interpretation of computation via patterns and signals
Simple rules, when iterated, can generate universal computation.
Each subsystem is independently executable and designed for educational exploration of computation theory.