In Love With Computer Science

There's a nice article written by a senior lecturer of UCSC, Dr. Chamath Keppitiyagama about the Turing Machine. I really like that article since I'm a big fan of theoretical computer science. It is a good attempt to show up an important concept to the ordinary people. I thought to repost it's content here to make it secure so that if the original article goes off, I won't miss it. :)

Link to original article: http://www.nation.lk/edition/component/k2/item/3666-a-computer-for-hundred-rupees?.html

A computer for hundred rupees?

No, I did not miss by several zeros – I meant it. We can build such a cheap computer and I guarantee that it can solve any problem that can be solved by those fancy and expensive computers. Now do not rush to buy processors, power supplies and other equipments, because we do not need them!

You can get the following ‘parts’ under hundred rupees. You need a long paper tape (a very long one), a pencil, an eraser, and a note pad. Take the long paper tape and using the pencil draw equal-sized squares along the tape.

That is it. Now there are some rules to follow. You can move the tape one square to the left or one to the right. You can write ‘1’ or ‘0’ on the square directly under your hand. If you wish you can erase anything on the square directly under your hand. After taking any action you can write a number in the note pad to indicate your ‘state’. The note pad has a table that you can consult before taking any action. This table tells you what to do – write, erase, move left or right – when you are in a given state and after reading a particular value from the tape. All that you can do is limited to those few actions.

That is your 100 rupee computer. I am not joking, but this machine is so powerful that it can solve any problem that can be solved on fancy computer. In fact, if a problem can be solved using a computing device, this computer can solve it. If this computer cannot solve a problem then it can never be solved using even a super computer. Unbelievable, isn’t it? Yet, it is true.

This machine is called a Turing machine. It was designed by Alan Turing in 1936, quite a long time before anybody made a computing device that resembles modern day computers. He did not propose it as a machine to be built and used for actual computation, even though you can easily build one if you really want to and use it for computation. Alan Turing proposed the Turing machine as a model of computation. He proposed that if any problem can be solved using computers this extremely simple machine can solve it and only the problems that can be computed on this machine can be solved on computers. It makes our 100 rupee computer a very powerful one indeed!

I have simplified the description of the machine quite a bit. A Turing machine needs an infinitely long tape, but let us ignore those details. Initially, the problem to be solved is written on the tape using ones and zeros on the squares (strictly speaking they do not even have to be ones and zeros, they can be any symbols). When the machine stops – that is when you stop moving the tape back and forth – the answer will be on the tape encoded in ones and zeros.

Computer scientists and mathematicians use this simple machine to study whether problems can be solved on computers and if so what are the most efficient ways to solve them. They do not actually build the machine, but use it to think of computing as a sequence of those actions allowed in the Turing machine. Even though they look very complicated, modern day computers try to mimic this machine. The role that you played in our 100 rupee computer is played by the processor and the memory chips take the place of the paper tape. The electronic processor is just faster than you and the problems can be solved faster, but apart from the speed, modern computers are not more powerful than a Turing machine. In fact, they are less powerful since none of them have an infinite memory whereas the Turing machine has an infinitely long tape (memory).

The power of this simple machine does not stop there. I am sure you have heard of those wonderful programming languages such as Java, C# and Python. Those programming languages are no more powerful than the simple set of instructions on our rudimentary computer. If you can write a nice program using those languages, you can write the same one using our simple set of instructions, but that would be tedious. Most of us have the notion that computers are all powerful devices. Well they are in some ways, but so is our Turing machine! I am sure now you have lost your faith in computers.

(The writer is a Senior Lecturer, University of Colombo School of  Computing)

Gnuplot For Visualizing Data

When writing research papers and technical documents, displaying data in a useful manner is really important. Specially when presenting different evaluation results in a statistical form in documents we  need to draw different types of graphs. Since it is important to me, I was looking for a good tool for that for sometime. Since I'm using Ubuntu Linux, the best recommended one I could find on the Internet was Gnuplot. It's a free tool and very powerful to draw different types of graphs.

Since it is a command line tool it takes some time to learn about how to use Gnuplot for our requirements. Therefore I postponed my Gnuplot learning process several times and finally today I got some first hand experience. At first I found this blog post. Then it sent me to this tutorial which contained so many helpful information. I recommend it if you really want to learn to use Gnuplot tool from the beginning.

To make my mind easy to memorise what I have learnt up to now, I decided to write a little summary of the basic things I need to use Gnuplot. So, here we go.

 1. To install gnuplot on my Ubuntu-11.04 system, I issued the following command in the terminal.

         sudo apt-get install gnuplot-x11

2. No I can start gnuplot by issuing the following command.

    gnuplot

It will show a prompt like the one showed in the above picture and all the other thing has to be done on this prompt. If you want to exit from the gnuplot, type 'exit' on the prompt.

3. Now let's create an example plot and write it in to an image file. To do that issue the following commands on the prompt.

    set terminal jpeg 

    set output 'our_file_name.jpg'

    plot sin(x)

Now in a new terminal you can go to the working directory of the gnuplot and open the 'our_file_name.jpg' file to view your graph. You can find out the working directory of gnuplot by typing 'pwd' on the prompt just like you do in normal terminal. To change the working directory use 'cd' as follows on the prompt.

cd "/path/to/new/directory"

4. To add the names of the graph, the x axis and the y axis use the following commands.

         set title "My graph title"

    set xlabel 'x axis'

    set ylabel 'y axis'

After changing these settings we have to re-run the previous plot command with new changes. We can do it in shorten way by using 'replot' command as below so that you don't have to write a plot command again and again since sometimes plot command is too long with so many parameters.

    set terminal jpeg

    set output 'plot.jpg'

    replot

5. Even though we set different parameters in gnuplot as above, they are gone if we exit from gnuplot and start it again later. Therefore it's useful to save current configurations so that we can load them again.

View the current configuration by issuing the following command.

    show all

You can save the configuration to a file as below.

     save "savefile.plt"

You can load a saved configuration from a file by the following command

      load "savefile.plt"

6. Now we want to draw a graph using the data which comes from another data file. Consider the following file named 'my_data.dat'.

 1 10 11   
 2 20 23   
 3 30 34   
 4 40 45   
 5 50 56   
 6 60 67        
 7 70 78   
 8 80 89   
 9 90 100  

We have three columns of data in that file. Let's draw a graph with first two columns.

      set terminal jpeg
     set output 'first_graph.jpg'
     plot "./my_data.dat" using 1:2 title "First line" with lines

first_graph.jpg

Now let's draw two graphs in the same figure. The first graph use first column as x-axis and second column as y-axis while the second graph use the first column as x-axis and third column as y-axis. Here's how we do that. 

     set terminal jpeg
     set output 'second_graph.jpg'
     plot "./my_data.dat" using 1:2 title "First line" with lines, "./my_data.dat" using 1:3 title "Second line" with lines

second_graph.jpg

There are so many other things to learn in Gnuplot to create nice graphs. I believe that learning gnupot would not be a wastage of time since good data visualisation is an important skill which should be in a computer scientist. So, I should expertise it in the future.  :)

That's all for now. Enjoy drawing graphs with gnuplot!

Moving Into an Important Time

I couldn't write something useful here for a considerable time. Even though I'm really busy on my final year project works I was unhappy about leaving my blog without writing something. I'm writing this post to make my mind although there's nothing useful in it.

Currently I'm in a crucial time period in my final year project. The designing phase went without any pain but now I'm facing so many issues from the beginning of implementation phase. So, for about a month I had a huge pressure in my head. But I think now most of those issues are solved to a considerable extent and therefore I hope to move in a straightforward process. That's about my project.

EasyPic Board (thanks to Chathika for the picture)

In this semester I'm taking the Robotics & Embedded Systems course and therefore I have to work with electronic stuff. Even though I'm working closely with embedded platforms from a longer time in Wireless Sensor Networks research work, I hadn't step into much lower hardware level. In this semester with this new course I think I will earn the necessary skills in electronics that I was lacking for years.

There's another important thing we have ahead. It's the ICTer 2012 conference. International Conference on Advances in ICT for Emerging Regions (ICTer) is mainly organised by our university with so many partners. As the SCoRe research group we hope to submit a paper to it. So, currently we are completing the paper writing task these days. The call for papers notice can be found here.

So, in every aspect it's a busy time. But I will try my best to keep my blog alive since this is the place which allows me to write anything I like.