Shtetl-Optimized » Blog Archive » The Computational Expressiveness of a Model Train Set: A Paperlet
Update (April 5, 2021): So it turns out that Adam Chalcraft and Michael Greene already proved the essential result of this post back in 1994 (hat tip to commenter Dylan). Not terribly surprising in retrospect! My son Daniel had his fourth birthday a couple weeks ago. For a present, he got an electric train set. (For completeness—and since the details of the train set will be rather important to the post—it’s called “WESPREX Create a Dinosaur Track”, but this is not an ad and I’m not getting a kickback for it.) As you can see, the main feature of this set is a Y-shaped junction,...
Source: scottaaronson.com