Imagine you’re in a queue to purchase food at a restaurant, for which pregnant women have priority. And there’s just a whole bunch of pregnant women arriving all the time. You’ll soon be starving. 😉 Now imagine you are a low-priority process and the pregnant women are higher priority ones. =)
Paul Rendell implemented a Turing machine in Life. Gliders represent signals, and interactions between them are gates and logic that together can create larger components which implement the Turing machine. Basically, any automatic machinery that can implement AND, OR, and NOT can be combined together in complex enough ways to be Turing-complete. It’s not a … Read more
Programming the Mandelbrot is easy. My quick-n-dirty code is below (not guaranteed to be bug-free, but a good outline). Here’s the outline: The Mandelbrot-set lies in the Complex-grid completely within a circle with radius 2. So, start by scanning every point in that rectangular area. Each point represents a Complex number (x + yi). Iterate … Read more
The pumping lemma is a simple proof to show that a language is not regular, meaning that a Finite State Machine cannot be built for it. The canonical example is the language (a^n)(b^n). This is the simple language which is just any number of as, followed by the same number of bs. So the strings … Read more
Wolfram has organized the 256 possible 1-D cellular automata based on nearest neighbors in this way: RULES: 0: 0 0 0 1: 0 0 1 2: 0 1 0 3: 0 1 1 4: 1 0 0 5: 1 0 1 6: 1 1 0 7: 1 1 1 If you’re evaluating a stage in … Read more
Ok, they’re fundamentally a pretty simple idea. A DHT gives you a dictionary-like interface, but the nodes are distributed across the network. The trick with DHTs is that the node that gets to store a particular key is found by hashing that key, so in effect your hash-table buckets are now independent nodes in a … Read more
This question isn’t as silly as it might seem to some. At least theoretically, something such as O(1/n) is completely sensible when we take the mathematical definition of the Big O notation: Now you can easily substitute g(x) for 1/x … it’s obvious that the above definition still holds for some f. For the purpose … Read more
Here’s the briefest explanation: A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory). So, if somebody says “my new thing is Turing Complete” that means in principle (although often not in practice) it could be used to … Read more