Start here
Computability Ideas for Curious Programmers
A plain-language map of computability theory: what can be computed at all, which questions no program can answer, and why it matters for odd languages.
Theory and Tools
Computability Basics
Plain-language computability ideas behind esoteric languages.
Finite Automata Versus Full Programming Languages
What a machine with fixed memory can and cannot do, why it cannot count without limit, and how that separates simple machines from full programming languages.
How to Show a Language Is Turing Complete
The usual recipe for a completeness proof: pick a known universal system, simulate it in your language, and handle the memory and control details carefully.
Infinite Memory Versus Real Machines
Why theoretical models assume unlimited memory, how that differs from finite hardware, and how to read Turing completeness claims about real languages.
Is Befunge Turing Complete
How people reason about Befunge's expressive power, why a fixed playfield complicates the answer, and what changes under idealized or later Funge rules.
Tag Systems and Tiny Universal Machines
Meet tag systems, a rule-rewriting model that can compute anything computable, with a traced example and a look at why tiny universal systems matter.
The Church-Turing Thesis Explained
What the Church-Turing thesis claims, why it is a thesis rather than a proven theorem, and what evidence supports it and what it does not say.
The Halting Problem in Plain Language
Why no general program can decide whether every program eventually stops, explained with a step-by-step contradiction and practical consequences.
Translating One Language into Another
How compilation is a form of translation, and why a faithful translator between two languages shows that one is at least as powerful as the other.
Turing Machines Explained
A step-by-step explanation of the Turing machine model: the tape, the head, the state table, with a small worked example you can trace by hand.
Undecidable Questions About Grid Programs
Which questions about program behavior, like reachability or equivalence, cannot be answered in general for a universal grid language, and what still can.
Related topics