| |
Abstract:
(Contributed Talk)
Ideas about computation have come to play an increasingly
important role in many contemporary philosophical debates. These
intuitions are underwritten by a long tradition in theoretical
computer science. In this essay, however, I present an open
question from complexity theory where the received theoretical
understanding runs counter to some very natural intuitions about
algorithms. I point to the nondeterministic Turing machine as the
source of these troubles and then sketch a brief history of
nondeterminism in theoretical computer science. Finally, I
suggest that more recent developments in complexity theory are
unlikely to resolve these philosophical tensions.
|
