gen-define-turing-completeness-and-give-one-short-worked-example-03a6

Define Turing completeness and give one short worked example.

# Turing Completeness **Definition:** A system is Turing complete if it can simulate any Turing machine, meaning it can compute anything that is computable given enough time and memory. **Practical requirements:** - Conditional branching (if/else) - Ability to change arbitrary amounts of memory - Ability to loop indefinitely --- ## Worked Example: Rule 110 Cellular Automaton Rule 110 is a simple 1D cellular automaton that's surprisingly Turing complete. **The rule:** Each cell updates based on itself and its two neighbors: ``` Current pattern: 111 110 101 100 011 010 001 000 New cell value: 0 1 1 0 1 1 1 0 (hence "Rule 110" in binary: 01101110) ``` **Example evolution:** ``` Generation 0: 000010000 Generation 1: 000111000 Generation 2: 001100100 Generation 3: 011011110 Generation 4: 110110001 ``` **Why it's Turing complete:** Matthew Cook proved (2004) that Rule 110 can simulate a universal Turing machine by encoding the machine's tape and states into specific spatial patterns. Despite having just one simple rule, it can perform any computation—demonstrating that Turing completeness can emerge from extremely simple systems.