- Quantum Computing Since Democritus (course notes)
- Why Philosophers Should Care About Computational Complexity -- Scott Aaronson
One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory — the field that studies the resources (such as time, space, and randomness) needed to solve computational problems — leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume’s problem of induction, Goodman’s grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis.
mechanical compute engine & code to simulate
#The Numbotron is a simple electromechanical computer. The basic component #of the computer is an odometer-style, 3-digit, base-10 counter, driven #by a stepper motor. By means of 3 reed switches wired in series, in combination #with magnets embedded in the face of each digit wheel, an output signal is #grounded when the counter contains the value 000. Decrementing a counter already at #zero will result in it underflowing to 999, and incrementing a counter at 999 will #result in it overflowing to 000. # #Programs are stored on a motor-driven drum that may contain up to 20 instructions. #Instructions are encoded by means of knobs protruding from the surface of the #drum, which directly act on a bank of mechanical switches. 16 switches control #the 'Enable' and 'Direction' signals for each counter, allowing individual control #over whether a counter is incremented, decremented or left disabled. 8 additional #switches control which counters have their 'zero-detect' outputs connected to a #central 'zero-detect' bus bar. # #Each instruction is executed by repeatedly incrementing/decrementing the selected #set of counters simultaneously, until one or more of the observed counters reaches zero. #If the zero condition is true at the beginning of execution, it becomes a NOP. # #For now, the only 'input' is the starting state of the counters, which may be #configured by hand prior to program execution. All programs run indefinitely, #although a 'halt' can be executed by means of an instruction that consists #solely of a false zero-detect condition without accompanying increment/decrement commands. #The real machine has a giant button that will force the zero-detect condition true, and can #be used to pause the machine while the operator manually changes the state of one or more registers, #resuming operation once the button has been pressed. Implementing this has been left as an exercise #for the reader.