On Decidability

Today, someone was saying that he/she finds decidability in TOC very hard to understand. And, my mind could not resist the temptation to type this out.

TOC deals with the key notion of “algorithm”. The question that we are interested in answering is, what problems can have an ‘algorithm’ and what cannot? In other words, which problems are solvable and which are not. This forms the theoretical basis for the entire world of software development that follows in courses like Algorithms, Data Structures, Programming, Software Engineering and so on.

If you were asked to answer this key question, how would you approach? There starts the beauty of this subject, TOC. First, we have to build models of machines which can solve something. Then, we have to build models of ‘software’ that solves something. At the end, we need some formalism to prove that depending on the nature of the machine, certain problems are unsolvable.

We first introduce the major idea that everything in this world can be modeled using a set. Yes, the usual normal set notation that we know of, such as A = {1,2,3}. We build and represent machines as sets. We represent input and output as sets. This idea, for itself, must have got a Nobel prize! You should take few days to sink this idea hard into your head.

Next, we show that there are only few classes of machines we could build. Everything else that we can think of is equivalent in power to these machines! I would have given second Nobel prize for this idea. If there are only few such machines, what are they? How do they look like? How do they process the input? How is an algorithm encoded? After answering these usual questions, the last major question we ask is “What is that this machine cannot solve?”.

My dear friends, this last question is your hello world to decidability. If there is one “wow” thing in computer science which stays in my heart forever, it would be the way TOC develops these ideas. Decidability is an extremely easy topic if you have absorbed these ideas correctly and completely. There is no need to mug up any table. There is no need to look at any videos. Just take a nice book, find a calm place, and dive into the beauty. If you have a friend or a parent who will get you a coffee in between, what more do we need in life!

Beautiful computer science.


Author: Venkatesh Vinayakarao

Researcher, Computer Science.

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 )

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