Saturday, January 29, 2011

Theory of Computing and Intelligent Design

The concept of intelligent design is very intimately related to the field of artificial intelligence. My main argument is that human beings are intelligent information processing systems designed by a superior form of intelligence.

In my view,  a human being is sort of advanced information processing system. DNA represents the code that builds the system and maintains its existence. The hardware consists of atoms and molecules and the laws of physics govern its dynamics. Computers are useless in terms of performing higher levels of intelligent tasks such as laughing for a good joke, recognizing a beautiful face, enjoying a good movie, and recognizing the beauty in mathematics and the laws of physics.

In addition, Turing machines can't solve the Halting problem. However, biological systems like animals avoided running for ever and they do halt. It is evident that the Halting problem is not an issue for biological systems. This implies an intelligent originator (programmer) that designed the first DNA so that biological systems always halt and die (excluding reproduction).

In conclusion, human intelligence is not simulatable by any Turing machine (unless anyone can be the supreme originator). Also, instead of attributing creativity to Nature, it is smarter to attribute creativity to a supreme originator.

Here is an interesting quote from Wikipedia about Artificial Intelligence: "The field was founded on the claim that a central property of humans, intelligence—the sapience of Homo sapiens—can be so precisely described that it can be simulated by a machine".

Thursday, September 16, 2010

A candidate NP-complete problem related to Mandelbrot set

This problem related to Mandelbrot set seems to be $NP$-complete:
$M=\{(c,k,r) |$ In the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ of first $k$ complex numbers, there is a subset $T$ of complex numbers such that the sum of the real parts $\gt r.k$ and the sum of imaginary parts $\gt r.k\}$.

$r$ is real number and $k$ is an integer in unary.

Here is a geometric interpretation, since each $P_c^i(0)$ is a vector in 2D, we want to find the maximum size square obtainable by the summation of a subset of two dimensional vectors. A promising reduction is from (optimization) number partition problem where each partition has the same number of elements (in the optimization version, we minimize the difference between the two sums).

Sunday, August 15, 2010

My criteria for what I consider a serious proof for the P vs NP problem

In light of Deolalikar's proof for P!=NP , Any valid resolution of the P vs NP problem must shed light and offer new insights into some of the fundamental concepts in mathematics and computer science. We want to really understand the true relationship between concepts like efficient computation of functions, randomness, and the computational nature of proofs. Why are some functions hard to compute while others are easy? What does constitute a random function? The ultimate resolution of the P vs NP problem must provide new insights into the nature of randomness and how it relates to efficient computation.

In my opinion, what is needed is a paradigm shift. This is what the history of scientific revolutions taught us. I believe we need to abandon the tradition of using polynomial functions to define the various notions of efficient computation. Invoking polynomial growth rates could be a symptom of paradigm blindness. I call it the Polynomial Disease.