Towards Empirical Computer Science

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 by PeterWegner, 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.

CategoryFormalMethods