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