Monday, August 20, 2012

What is computation?

Computation has many forms, but they all lead to the same result, and they are thus all equally valid. One of those forms is simplification, as in reduction. This is what allows lambda-calculus to compute. When I state the expression x + 5 = 8, the answer is already there. Every bit of information needed to "solve for x" is already embedded in the statement itself. Thus we can simplify, reduce it, to the statement x = 3. This makes it more clearer what x is, and is thus simplified.

That, in its essence, is what computation is. It's the simplification of statements into simpler statements. It is shown in languages such as Haskell, that one can do very powerful things without manipulating variables, by using just the reduction of statements into their simpler forms to compute. It has been shown that lambda-calculus is Turing complete, and can thus compute all efficiently computable expressions.

But what about NP problems? NP problems are problems that cannot be computed in polynomial time as of what we know now. It has however, not been proven that NP =/= P nor that NP = P, so we don't know whether they can or cannot be computed in P time. But as we have seen, they contain all the information needed to solve them, we just don't know any better ways than to try all the different combinations. But they are computable.

No comments:

Post a Comment