Philosophy behind Theory of Computation

Posted: December 16, 2013 in algorithms, Mathematics, philosophy, programming

There is really an interesting fact associated with the Theory of Computation (ToC). Like we say failures are stepping stones to success, the different aspects of ToC flourished out of failures.

McCulloch and Pitts were initially trying to formalize a mathematical model to simulate the functioning of brain through abstract neuron networks, but it failed to capture the entire notion of brain function, but this failure lead to the development of Finite State Machines.

Noam Chomsky was trying to formalize the human languages, but he realized that to frame the human languages into a mathematical set of rules is extremely complex, but this failure lead to the development of Context Free Grammar (CFG), which eventually lead to Backus Norm Form (a notation technique for CFG). It is surprisingly similar to the grammar of Sanskrit formalized by Panini (4th century BCE). So, CFG shares the grammar of Sanskrit, and this is one way by which Sanskrit is related to computation.

David Hilbert challenged the mathematicians with a famous question – “does there exists a general procedure/method to solve all the mathematical problems?”.  Hilbert believed there exists a procedure to do so (popularly known as entscheidungsproblem). This intrigued many mathematicians, and eventually Church and Turing proved that there is no such method. Hilbert did failed in his belief, but this has lead to the development of an elegant idea called Turing Machines. Turing wanted to first formalize what does Hilbert meant by “general procedure/method”, and he came up with a formal definition for “Algorithms” based on the idea of Turing Machine, and the notion of what is computable (tractable) and what is not computable (intractable) in reasonable amount of time.

How elegant it is to see that such failures had lead to a beautiful subject called Theory of Computation :)which eventually rules the entire modern day computer innovations.


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s