m i n d c o d e

I recently started to read a book from Keith Devlin about the Millenium Problems of Mathematics. One particular problem which every Computer Scientist have heard about is the P = NP. I say heard, not understood. Most of the people I’ve met, including me, know that this problem is directly related to the complexity of a particular algorithm. Most also know that it states that any known solution of a particular problem performs in superpolynomial time. And that’s all they need to know…

What most don’t know is the exquisite meaning of NP. An NP class problem is one such that a non-deterministic computer can solve it in polynomial time. Got it? Let me express it in other words: A problem which is NP can be efficiently solved by just getting luck in every choice you have to make. For example, in the traveling salesman problem, one can in fact solve it in linear time by correctly guessing the next city. The problem is guessing it right!

Some people have also heard about NP-complete (NPC) problems. What is the difference between a NP and an NPC problem? To put it simple, an NPC problem is an NP problem that has been shown to exhibit the characteristic of being able to be “translated” into any other NPC problem. This means that a polynomial solution found to a particular NPC problem can be easily applied to every other one. It’s like a dictionary of problems; find the solution of a puzzle, and you’ve found the generic solution of that class of puzzles!

And this is where everyone stands… No one have been able to prove that there exists NP problems that can or cannot be solved in polynomial time, since no one ever found a P solution to an NP problem. Of course P = NP could be proved or disproved without actually founding a particular solution: this would mean that every NP problem have an efficient solution, though it hasn’t been found yet.

Keith describes this enigma in such an enthusiastic way that lead me to read the formal problem statement. I must say that even my recently acquired knowledge on formal language semantics is not enough to read it easily. But I couldn’t resist inciting my colleagues and readers to have a glance at it… Enjoy!

P.S.: My apologies to my purist friends from any inaccuracy I’ve made for the sake of simplicity. You are free to flame me in the comments section

Back in the 90’s, I came across an Amiga 500 program that simulated a 2D cellular automaton (CA) called Wireworld. The rational behind this cellular automaton is quite simple. You start with a grid (any size you want). Each cell in the grid has four possible states: 1. Empty, 2. Electron Head, 3. Electron Tail, 4. Conductor (or Wire).

Then, given any initial set of the grid, you apply the following rules in each step:

• Electron head → electron tail
• Electron tail → conductor
• Conductor → electron head iff one or two of the neighboring cells are electron heads

Guess what? You have a turing complete automaton. Let’s look at some examples on building simple gates. First, a diode:

In this picture, Heads are blue, Tails are red and Conductors (or wire) are yellow. Let’s look at a more complex example:

Here we can see two clock generators at the upper and lower left, and a XOR gate at the center right. Can we make AND gates? OR gates? Latches? The answer is yes. Actually, there are several kinds of gates that work depending on the cycle (or frequency) of the “electrons”. You can check a whole list of discovers in this page.

Still, the most amazing thing I’ve seen accomplished since that time was a complete working implementation of a programmable RISC computer. It is just amazing to see it in action. These guys have managed to implement flip-flops, binary adders, and register banks. Ingenious!

Despite the fact that an implementation of a simulator of this automaton is quite a simple exercise, you can check here for the Wireworld computer in action, or download the Mirek’s Cellebration software which includes a highly performant simulator of this and several other 1D and 2D cellular automatas.

P.S.: This is my hundredth post :-) 

I seem to have missed this article posted in Slashdot about the possibility of a new encryption standard published by NIST to be flawed by design. Actually, some assumptions go even further and ruminate about a potential intentionality in this flaw.  Any experts in cryptography out there who want to comment on the veracity of these speculations?

In a previous post I wrote about a prize being offered by Stephen Wolfram, the creator of the Mathematica Software and author of A New Kind of Science, to whomever proved (or disproved) the universality of a 2,3 cellular automata.

Nearly 4 months later, Alex Smith has just won the $25,000 USD prize by demonstrating the universality of Wolfram’s Turing machine in an ingenious 40-page proof.

Congratulations goes to Alex Smith for this amazing scientific contribution.

Stephen Wolfram, creator of Mathematica and author of the idiosyncratic book A New Kind of Science, has offered a prize of $25.000 (18 598€) to whomever proves (or disproves) the universality of a 2,3 (2 states and 3 colors) cellular automata.

This fact (once proven) would show that even with an extremely reduced set of rules/states it is possible to achieve Computational Universality.

Personally, I believe that the probability of such a small set to randomly occur in nature could be surprisingly high, pointing that simple organisms and even physical phenomena capable of Computational Universality, more than just the mere result of chance, can be the product of an universal inevitability.

Done with Blender and Indigo.

Boost “provides free peer-reviewed portable C++ source libraries.” It also provides some very good Graph manipulation functions, one of which is a very fast Dijkstra shortest-path implementation that I wanted to use from within Python.

Bear in mind that for this project I need to host Python in a Windows 2003 Server machine. First thing to do is to get the Python bindings for the Boost Graph Library. Problem is, it isn’t very clear how do you install it… After trying a while, I copied the contents of bgl-python-0.9/python/boost/graph to $python$/lib/site-packages/boost/… it worked

Second problem is to understand all this C++ templating world. If you try to invoke a binded function from within Python you can get something really cryptic (try writting boost.dijkstra_shortest_paths() in the interpreter).

After trying to read the documentation, looking at the usage example of BGL, and banging my head into a wall several times, I finally found how to make it work… I leave a simple example here for anyone who’s interested.

Excelent essay by my friend Paulo Cunha on the statistical analysis of searched keywords by several countries. A *must* see!

I made this yesterday at 3am while playing with Fyre. Here are the parameters I used:

Width: 1280
Height: 800
Oversampling: 4
Exposure: 0,15
Gamma: 1
Oversampling gamma: 1,66
Foreground: White
Background: #2C3755
A: 8
B: 2
C: 2
D: 10
Zoom: 1,2
Aspect: 1,3