Home » Miscellanea » Theory of Computation

Theory of Computation

In this section I will discuss on some of the fundamental concepts and results about Computability and Complexity Theory.
Other than highly fascinating from an historical perspective, these subjects are extremely important to understand what computing actually means.
In a nutshell, computability theory answers the question: “What does it mean for a function (on natural numbers) to be computable?”. Moreover, “Is there any function which cannot be computed?”.
Intuitively, a “computable function” is a function that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. As we will see, this exactly reminds to the idea of algorithm, which is just the mechanical application of a sequence of mathematical steps.
On the other hand, (computational) complexity theory focuses on computable functions (i.e., problems that can be solved by an algorithm), and tries to provide a “classification” of those according to their difficulty. Indeed, some computable functions (i.e., solvable problems) seem significantly simpler than others. For instance, consider the very simple computable function mult(a,b), which returns the product between two natural numbers a and b. A very simple algorithm to compute this function comes directly from the definition of multiplication, and requires summing b times a to itself.
Then, consider the computable function subset_sum(S,n), which instead return 1 if there exists a subset s in S whose elements sum up to n, 0 otherwise. Just having a look at this second function and you realize that it appears a way more difficult to compute than the multiplication above.
… Is that really true?


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s