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.

1 comment:

  1. That means to stroll away with more money than you began with, you need an excellent amount of luck. Here are the three finest on line casino video games to play you'll like|if you'd like} first rate odds of profitable money. There are several of} methods find a way to|you presumably can} earn 파라오카지노 free spins when playing in} slots online. Currently, HoF presents the option model spanking new|for brand new} users determine on} between both a thousand coins of a hundred free spins as their welcome gift. This gift presents plenty of opportunity to earn a ton of in-game forex, with out having to wager any away.

    ReplyDelete