Ken Thompson

Life and career

Kenneth Lane Thompson was born in New Orleans in 1943 into a Navy family, which meant a childhood spent moving — including a stretch overseas. He studied electrical engineering and computer science at the University of California, Berkeley, taking both his bachelor's and master's degrees there in the mid-1960s, and by his own account spent much of that time simply playing with the computers, which were then new enough that playing with them was research. He joined Bell Labs in 1966.

Thompson's early work at the Labs was on **Multics**, the enormous joint MIT–GE–Bell time-sharing project. Bell Labs withdrew in 1969, and the researchers lost their time-sharing environment. Thompson had written a game, *Space Travel*, that simulated the solar system; wanting somewhere to run it, and wanting a decent programming environment generally, he found a cast-off PDP-7 and, over roughly a month in the summer of 1969, wrote a file system, a kernel, an assembler, and a shell. This is the origin of **Unix**. Dennis Ritchie, Rudd Canaday, Doug McIlroy, and Joe Ossanna joined the effort, and the system moved to a PDP-11 and, in 1973, was rewritten in Ritchie's new language C.

The stories about Thompson's productivity are numerous and, as best anyone can tell, true. He wrote the first Unix shell, the first version of **grep** (extracted from an ed command in an afternoon at McIlroy's request), the regular-expression engine behind it, the B language that became C, the ed editor, and much of the early kernel. He also built **Belle**, a special-purpose chess machine with Joe Condon that became the first computer to achieve a master-level rating and won the World Computer Chess Championship in 1980. He generated exhaustive databases of chess endgames — tablebases — and in the process discovered positions that overturned received endgame theory, forcing revisions to the rules on move limits.

He shared the ACM Turing Award with Ritchie in 1983. His acceptance lecture, "**Reflections on Trusting Trust**," is one of the most-cited talks in the field. He also received the National Medal of Technology and the IEEE Hamming Medal, and is a member of the National Academy of Engineering.

In the late 1980s and 1990s he worked with Rob Pike on **Plan 9**, and the two designed **UTF-8** — reportedly sketching the encoding on a placemat during a diner meal and implementing it within days. In 2006 Thompson left Bell Labs for Google, where he was one of the three principal designers of the **Go** programming language with Rob Pike and Robert Griesemer.

He is, by consistent account, laconic, allergic to ceremony, and driven mainly by whether a problem is interesting. He is also a licensed pilot who once traveled to Russia to fly a MiG-29. The temperament is legible in the work: everything he built is small, sharp, and finished.

Key contributions

**Unix.** Thompson's architectural decisions are the ones that stuck. The **hierarchical file system** with a single rooted tree and mountable subtrees. **Everything is a file** — devices, terminals, and later network resources all accessed through the same open/read/write/close interface, so that a program written for a terminal works on a file with no changes. The **shell as an ordinary user program** rather than a kernel component, meaning it can be replaced, scripted, and composed. Processes created by **fork and exec**, a decomposition that separates "make a copy of me" from "become a different program," giving redirection and pipeline construction a natural place to happen in between. And **pipes** — McIlroy's proposal, implemented by Thompson — which made composition the system's central operation.

The philosophy is worth naming precisely because it is a real design thesis with real trade-offs: build small programs that do one thing, make their interface a stream of text so that anything can talk to anything, and let the user compose. The cost is weak typing at the interface layer and a certain amount of parsing misery. The benefit is that Unix could solve problems its designers never anticipated, which is why it is still here.

**Regular expressions and grep.** Thompson's 1968 paper "Regular Expression Search Algorithm" described compiling a regular expression into machine code that simulates a nondeterministic finite automaton, tracking the set of possible states as it consumes input. This is the **Thompson construction**, and its significance is that it runs in time linear in the input length regardless of the pattern — no catastrophic backtracking. Many modern regex engines abandoned this in favor of backtracking implementations that support backreferences and can therefore exhibit exponential blowup; the ReDoS vulnerability class exists because of that choice. Go's regexp package and Google's RE2 deliberately return to Thompson's approach. Every graduate student who has watched a production system stall on a pathological regex has an object lesson in why the 1968 algorithm mattered.

**Reflections on Trusting Trust.** The Turing lecture presents a three-stage argument that remains the deepest statement of a genuine security limit. Stage one: write a compiler that, when compiling the login program, inserts a backdoor. Anyone reading the compiler source sees the attack. Stage two: also make the compiler recognize when it is compiling *itself*, and insert both the login backdoor and the self-recognition logic into the output. Stage three: compile that compiler once, keep the binary, and **delete the malicious source**. The clean-looking compiler source now produces a compiler binary that backdoors login and propagates the attack into every future compiler it builds. No amount of source auditing can find it, because the source is clean. Thompson's conclusion: you cannot trust code you did not totally create yourself, and trust in software is ultimately social, not technical. The observation drove decades of later work on reproducible builds and diverse double-compiling.

**UTF-8.** With Rob Pike, Thompson designed a variable-length encoding of Unicode with a set of properties so well-chosen that it displaced every alternative. ASCII is a subset, so all existing text and all existing C string code keeps working. It is self-synchronizing — from any byte you can find a character boundary by inspecting a couple of bytes — so a corrupted stream recovers. Byte-wise lexicographic sort order matches code-point order. There are no embedded null bytes in multibyte sequences, so C strings are safe. UTF-8 is now the encoding of well over ninety percent of the web.

**Go.** With Pike and Griesemer, Thompson designed a language for large-scale server software: fast compilation, garbage collection, a simple type system with structural interfaces, and CSP-style concurrency via goroutines and channels. The deliberate austerity — long resistance to generics, no inheritance, no exceptions — is recognizably the same taste that produced Unix.

In battle

Thompson's computed profile is a near-pure counter-pick. He carries 100 problems at a mean of **18.8** with a median of 12, sixty-eight of them at or below 20, and exactly **one** dominant problem — but that one is a 99. His only strong category is **systems** at 40.1 across eighteen problems, followed by `information` at 25.8, `search` at 23.7, and `computability` at 21.5.

The 99 is **P246, "Small tools, loosely joined"** — his own 1969 workbench. The game's explanation is emphatic that there is no more direct match anywhere on the roster: the hierarchical file system, everything-is-a-file, the shell's pipeline notation, and grep itself all came from him. He edges Ritchie's 96 on this problem because he led the original kernel and shell design; Ritchie's contribution was the language that made it portable.

His secondary strengths are modest but coherent. **P252, "The document that links anywhere"** (74) reflects the text-processing lineage of Unix, though Berners-Lee's 100 owns that problem outright. **P194, "Prune the adversary's replies"** (72) is alpha-beta pruning in game search, and this is a genuinely earned score — Belle was a serious chess engine and Thompson's endgame tablebase work was original research in exhaustive game analysis. **P079, "The language for the job"** (65) covers B, C's antecedent, and Go. **P082, "Ship it to a hundred contributors"** (62) and **P245, "A computer shared by fifty"** (57) reward Unix's role as shared infrastructure and time-sharing system. **P046, "Shortest path through the map"** (51) and **P048, "Prove the program correct"** (50) are middling; note that Trusting Trust is arguably an *anti*-result for program verification, which may explain why he does not score higher there.

His losses are a wall. **P285, "Test the many with the blood of few"** (3) is group testing; **P176, "Cut through the interior"** (3) is interior-point methods for linear programming; **P177, "The certificate of optimality"** (3) is LP duality; **P183, "Cool it slowly"** (3) is simulated annealing; **P184, "Fill in the hidden variables"** (3) is EM; **P185, "Optimize across the datacenter"** (3) is large-scale distributed optimization. His `regression` average is 3.0 — the lowest of any category on any card in this group — and `high-dim` and `small-sample` are both 6.5. Notably his `optimization` average is 9.3 across seventeen problems, meaning the single largest category on the board is nearly a total loss for him.

The strategic read: Thompson has one of the highest ceilings and one of the lowest floors on the roster. He is the correct answer to exactly one question — how do you build a system out of composable minimal parts — and he answers it better than anyone alive. His stated battle identity is candid about the rest: he wins on ruthless simplicity and code no one else could write, and loses interest once a problem stops being fun. Twelve is his median. Field him for the matchup, never for the average.