David Halasz's wroclove.rb 2024 talk (invited, in his words, by Andrzej 'Andre' Krzywda). A theoretical-computer-science crash course for Ruby programmers in four parts. (1) How computers work — models assembly as a Ruby Instruction class with an instruction pointer and Jump/Add/Subtract subclasses. (2) Formal languages — alphabets, grammars (terminals, non-terminals, production rules), and the Chomsky hierarchy: regular languages (regular grammars, parsable by finite-state machines / regexes; any Ruby regex compiles to such an automaton), context-free languages (single non-terminal on the left; parsable by pushdown automata; deterministic vs non-deterministic have different expressive power; all parenthesis-matching languages live here), context-sensitive languages (multi-symbol left-hand sides; parsable by linearly-bounded automata — close to real computers with finite memory), and recursively enumerable languages (unrestricted grammars; parsable by Turing machines; equivalent to lambda calculus and general recursive functions). (3) Turing machines — infinite tape, read/write head, states, transition function; used for proofs rather than computation; one machine can simulate another; determinism doesn't change expressive power; multitape machines reduce to single-tape (historical proof that a single-memory computer can exist, though physical code/data segments in x86 are separate); Church-Turing thesis; universal Turing machines; algorithmic complexity as space (cells used) vs time (head moves). (4) How compilers and interpreters work — lexical analysis (tokens via regular expressions / FSMs), syntactical analysis (parse tree / abstract syntax tree; sometimes bytecode instead; produces syntax errors), semantical analysis (type coherence, scopes, declarations; Rust's borrow checker lives here), optimizations (constant folding, constant propagation, caching, loop unrolling — including leveraging MMX/SSE for 4-wide multiplication), execution or code generation to assembly. Virtual machines are introduced as the component running intermediate representation — YARV (Yet Another Ruby Virtual Machine by Koji/Koichi Sasada) is Ruby's stack-based VM and also the home of the GVL and GC. Closes by noting that, in practice, nobody writes these by hand: lexer/parser generators and existing VMs (Java VM / JRuby, GraalVM / TruffleRuby, llvm for Ruby, Parrot, .NET) are already available; syntactical analysis uses pushdown automata, semantical analysis uses graph traversal — patterns Rubyists already use.