Articles
Is A Hole A Real Thing, Or Just A Place Where Something isn’t?
It seems indisputable that there are holes. For example, there are keyholes, black holes and sinkholes; and there are holes in things such as sieves, golf courses and doughnuts. We come into the world through holes, and when we die many of us will be put into specially dug holes. But what are these holes …
On Vagueness, Or, When Is A Heap Of Sand Not A Heap Of Sand?
Imagine a heap of sand. You carefully remove one grain. Is there still a heap? The obvious answer is: yes. Removing one grain doesn’t turn a heap into no heap. That principle can be applied again as you remove another grain, and then another… After each removal, there’s still a heap, according to the principle. …
How Things Go From Straight-Forward To Chaotic
Engineers have developed mathematical tools that determine when randomness emerges in any stochastic (random) system. The research looks to answer a long-standing question: When does randomness set in during a “random walk?” Picture a herd of sheep or cattle emerging from a shed or barn to graze a field. They head straight out of their …
Hundreds Of Impossibility Results For Distributed Computing
1 Introduction What can be computed in a distributed system? This is a very broad question. There are many dierent models of distributed systems that reect dierent system architectures and dierent levels of fault-tolerance. Unlike the situation in sequential models of computation, small changes in the model of a distributed system can radically alter the …
On The Computational Complexity Of Algorithms
I. Introduction. In his celebrated paper [1], A. M. Turing investigated the computability of sequences (functions) by mechanical procedures and showed that the setofsequences can be partitioned into computable and noncomputable sequences. One finds, however, that some computable sequences are very easy to compute whereas other computable sequences seem to have an inherent complexity that …
For A Meaningful Artificial Intelligence
Defining artificial intelligence is no easy matter. Since the mid-20th century when it was first recognized as a specific field of research, AI has always been envisioned as an evolving boundary, rather than a settled research field. Fundamentally, it refers to a programme whose ambitious objective is to understand and reproduce human cognition; creating cognitive …
Millions, Billions, Zillions
February 22, 2010 Big numbers are everywhere these days, what with lost jobs (millions), bailouts (billions), and the budget and its deficits (trillions). I think most of us don’t grasp these numbers at all, to the point where words like million, billion and trillion have become synonyms for “big,” “really big” and “really really big.” …
The Mythical Man-Month
More software projects have gone awry for lack of calendar time than for all other causes combined. Why is this cause of disaster so common? First, our techniques of estimating are poorly developed. More seriously, they reflect an unvoiced assumption which is quite untrue, i.e., that all will go well. Second, our estimating techniques fallaciously …
On Certain Formal Properties Of Grammars
A grammar can be regarded as a device that enumerates the sentences of a language. We study a sequence of restrictions that limit grammars first to Turing machines, then to two types of system from which a phrase structure description of the generated language can be drawn, and finally to finite state Markov sources (finite …
The Cathedral And The Bazaar
I anatomize a successful open-source project, fetchmail, that was run as a deliberate test of some surprising theories about so=ware engineering suggested by the history of Linux. I discuss these theories in terms of two fundamentally di:erent development styles, the “cathedral” model of most of the commercial world versus the “bazaar” model of the Linux …