Turing Tumble is a toy gravity-fed mechanical computer (similar to the classic Digi-Comp II, but including additional types of pieces such as gears), in which marbles roll down a board, along paths determined by the locations of ramps, toggles and gears, which are placed by the "programmer," and by their current states, which are altered by the passing marbles. Aaronson proved that a Digi-Comp II decision problem (viz., will any marbles reach the sink?) is CC-Complete, i.e., equivalent to evaluating comparator circuits, and posed the question of what additional functionality would raise the machine's computational power beyond CC, speculating that a capability for toggles to affect one another's states (which Turing Tumble's gears happen to provide) might suffice. This turns out to be so: we show, though a simple reduction from a variant of the circuit value problem (CVP), that the Turing Tumble decision problem is P-Complete. The two models also differ in complexity when exponentially (or unboundedly) many marbles are permitted: while Digi-Comp II remains in P, Turing Tumble becomes PSPACE-Complete.
展开▼
