The most fascinating paper I've read in ages deals with this idea that computer science is not mathematics. It is rather academic, but a real page-turner nonetheless. It is called Towards Empirical Computer Science
, and it is at http://www.cs.brown.edu/~pw/
. -- MichaelFeathers
most fascinating...in ages
sounds like a strong claim for you, Michael! Must be quite the paper.
It made a lot of things click for me, but, truth be told, I leave a lot of things unclicked. -- mf
(moved from FormalDeveloper
In some ways I don't get this paper. There are some things I understand and some things I don't, and of the things I understand, or think I understand, there are some I agree with and some I disagree with.
While it is true that Turing machines don't have a continuous stream of external input, there is also the ancestor of the Turing machine, the finite state machine.
Finite state machines (FSMs) have input and change state according to their input. There is no requirement that the input
to an FSM be finite; only the number of states in the machine must be finite.
You can make a Moore or a Mealy machine, which is a finite state machine which produces output. (A Moore machine produces output as a function of its state; a Mealy machine produces output as a function of its state and
the input which is going to govern its next state change.)
You can even feed a Moore machine's output back through a complicated system to its input. Suppose we make a black box and label it "the Universe" and feed the output into that. Feed the Universe's output back into the state machine. This is of course the FourProcessesOfConsciousness
but applied to a machine instead of a consciousness.
If you really
want to do something fun, you can take a finite state machine and equip it with an infinitely long piece of memory tape. Let it change states and move the tape based on the content of the tape and
its external input. If the machine has been running for a finite amount of time, only a finite amount of the tape will have been used.
How does the machine's connection to the Universe make it or its behavior non-amenable to logic? Am I missing something?
At the same time, though, this paper says something tantalizingly similar to what is said on InterpretersAreForTesting
: that an unchanging UnitTest
cannot test or demonstrate an abstract
characteristic of a function, such as the idea that it sorts data. Just because a function transforms 2 1 3 into 1 2 3 doesn't mean it sorts.