History of Theory of Computing


Date: May 09, 2008

Throughout recorded history, much of mathematical science has been a search for algorithms for the effective solutions of various problems. Remarkable, for most of this time, while mathematics was being applied to formalize and rigorously investigate many scientific concepts such as motion, light, heat, energy and atomic structure, the notion of algorithm remained intuitive and formal, beyond the reach of mathematical people. Then just over 70 years ago, an important scientific breakthrough changed this. The notion of algorithm was completely formalized, rendering it subject to rigorous mathematical investigation. This occurrence, in the mid 1930’s is the beginning of the theory of computing and arguably computer science.

  • Encouraged by the development of mathematical logic (including Cantor’s Set theory) the mathematician David Hilbert proposed a concerted effort to solve the “Entscheidungs problem” i.e. to find the truth or falsity of arbitrary mathematical statements. This effort became known as Hilbert’s program.
  • In 1931, Godel showed that one approach to Hilbert’s program was impossible. But proving that every logical system adequate for doing mathematics has statements that it cannot prove or disprove.
  • In the early 1930’s, Alonzo Church of Princeton University formulated the lambda calculus as a candidate foundation of mathematics.
  • In 1934, two of Church’s graduate student, Stephen Kleene and Barkley Rosser, proved that the lambda calculus cannot provide a foundation of mathematics.
  • In 1934, Godel defined the class of “general” recursive functions. This extension is based largely on an idea of Herbrand, so these are sometimes called Herbrand-Godel recursive functions.
  • In 1934, Church conjectured that lambda definable functions are exactly the effectively calculable functions (“Church Thesis”). His conjecture was supported by three considerations:
    • All lambda definable functions are calculable.
    • It has become clear that many effectively calculable functions are lambda definable.
    • Church proved that a function is lambda definable if and only if it is Herbrand-Godel recursive. Church presented his work in April 1935, lecture at Princeton and published in 1936 paper. Godel and others were not convinced.
  • In the spring of 1935, Alan Turing, a first year graduate student at King’s College, Cambridge took a course in mathematical logic from M.H.A. Newman. In that course he learned about Godel’s incompleteness theorem and Hilbert’s Entscheidungs problem. He set to prove that the Entscheidungs problem could not be solved effectively by showing that no effective mechanical process can decide the truth or falsity of arbitrary mathematical statements. Turing succeeded by carefully analyzing the notion of “mechanical process”, defining an abstract machine model (The Turing Machine) capable of computing anything computable by mechanical process; proving that there is a universal Turing Machine capable of simulating all others, and using this to prove that no Turing Machine can resolve the truth or falsity of arbitrary mathematical statement. Turing wrote this in a paper and gave it to Newman.
  • In 1936, Church’s paper arrived at Cambridge in the American Journal of Mathematics. Although Church’s paper did not explicitly mention the Entscheidungs problem, it did prove that the existence of problems not solvable by lambda definable functions. (In fact, in a later 1936 paper, Church’s proved the insolvability of Entscheidungs problem). Turing’s analysis of mechanical calculation and his construction of Universal Turing Machine were still new, so he added an appendix to his own paper proving that a function is lambda definable if and only if it s computable by a Turing Machine and send his paper to the proceedings of the London Mathematical Society, which published the paper in 1936.
  • Turing’s analysis immediately convinced Godel and others of Church’s Thesis, which is now usually called the Church – Turing thesis. This says that a function is effectively computable if and only if it is computable by a Turing Machine.
  • Turing went to Princeton, spending 1936-1938 working ether an earning a PhD from Church for a thesis on ordinal notations.
  • In 1938, Kleene defined the class of partial recursive functions. This is a mathematically convenient definition of the class of computable functions – Modern recursive functions is based on this definition and Kleene’s pioneering developments.
  • Since mid 1960’s, the computational complexity (i.e running time and memory) of solving problems has been central to the theory of complexity. For studying computational complexity, the Turing Machine is the usual model of choice, because resources such as running time, workspace etc. have clear meanings in this model.

Acknowledgement - Dr. Jack Lutz.

Topology control for power aware ad - hoc network

Date: May 09, 2008

My recent survey on topology control for power aware ad-hoc network.
Link: Presentation

Tips to write cover letter

Date: January 29, 2008

I have been curious many times how to write a good cover letter, what are the components that I need to include and what it should look like. It should be conrete, precise and attractive. Its an introductory letter to lure your employer to read your resume. Without giving more fundes, I will give you a sample cover letter which I found the most useful.

"{Month Day, Year}"


"{Name of Hiring Manager}"
{Title}
"{Company Name}"
"{Street Address}"
"{City, State Zip Code}"

Dear "{Mr./Ms. Last Name}" ,

This letter is to express my interest in the X position listed on X. Based on my skills in X and X (match what is listed in the posting), I am confident that I would be a great addition to your team.

My resume that highlights my ability/knowledge/expertise in X and X areas/industries is enclosed. During my time at X (past company), I was able to (succeed/save money/save time/increase sales/increase productivity) in X . (List a specific example relevant to this position, focusing on how you can help the company.)

I am excited about the X position and the ability to help your company succeed. Thank you in advance for your time. Please do not hesitate to contact me if you have any questions. I would appreciate the opportunity to review my qualifications in more detail and will contact you next X (day of week).

Sincerely,

 

Name
Follow this template and I am sure you will be fine. It could also be used as a standard email format when you are submitting your resume via email. * Courtsey - Deloitte. 

Broswer Testing

Date: Nov 6, 2007

If you have been in the web development, you might know how important it is to have your website tested on different browsers.

URL: http://browsershots.org/

Recently I came across the above mentioned URL which allows you test different URL's across different browsers on different platforms. It's a really cool stuff and acutally useful and believe me it saves a lot of time too :). Thanks to Stumble Toolbar Utility which I have installed on my browser :).

YPOP's

Today, I came across an amazing software: YPOP's. It is registered wtih Sourceforge.net. It helped me to forward my email to Outlook from my free Yahoo mail account.
Link: YPOP

While configuring Outlook, use POP3 Server for incoming mail and SMTP for outgoing mails and put the server location as 127.0.01. Same server for SMTP. and you will be all set.Long Live Open source community!!

Quantification of Randomness:

Personalization adds randomness to the generalization. It adds diferent features and traits which comes from different environment making the current system less coherent. It can be seen in day to day life from Stock Exchange to small farming business. There has to be some governing rule to quantify this randomness in the given n paramters or state of the situation. 

Problem Statement: Given an n - state system and a k personlized variables from m different environment, how the current system will affect. In short, can we determine a random factor f which will define the state of system in the current context?

Interested in Web Application:

We all know that rapid turn around time is one of the key factors for web application development. I think its time to think if we are Java savy and we may need to re visit our decision to use Java as the primary language. Even Google people use Python:) Look at the following data:

No matter what you choose,...start learning Python now. Click here