Math, Computing, Logics and Me

Comic by Randall Munroe from xkcd.com

The above comic probably explains why a lot of people seemed really confused in class on Thursday when we were talking about problems that computers cannot solve.

Audience: "What? Computers can't solve every problem given enough time?"

Me: "That's right, in fact it took us almost an entire lecture to get that concept drilled into our heads."

Audience: "Tell me (us) more!"

Well the reading for the class period took two routes.  The first was that of Alan Turing and Alonzo Church.  The second was of Murray Leinster.  Turing came up with the idea for a simple computational machine "the Turing Machine."  The Turing Machine is more of a thought experiment than an actual device.  The purpose being, that the Turing machine can help us understand what is and isn't computable.

Audience: "Where does Alonzo Church fall into the picture?"

Church wrote a thesis about the capabilities of a Turing machine.  He is quoted as saying 'Everything computable is computable by a Turing machine.'  This meant that if there was a way of solving a problem (i.e. it is computable), then that problem could be solved by a the Turing Machine.

Audience:  "You haven't told us about why certain problems can't be computed."

I'd like to try to explain it, but really the proof that certain things are not computable would take a lot of math and somebody has already talked about this in their blog (See DigitalCivilization.blogspot.com).

Audience: "Ok, I'll go read that.  So who is Murry Leinster?"

Leinster was a science fiction author who wrote the the short story "A Logic Named Joe."  The interesting thing about this is how Leinster was able to correctly predict the digital age that we live in where we have logics (computers) in every home and they are all connected to each other (Internet).

Somehow the short story that Leinster wrote seems to make quick correlations to us today in our everyday lives.  On the other hand, the concepts of Turning machines and uncomputable problems seem so far distant from application in our real lives that it can be easily dismissed as useless knowledge.  This often seems to be the case with math, because the deeper you get into the field of math, the further you feel like you are going away from reality.

The truth is however, that both math and the consequences of the Turing machine are very much applicable to our daily lives.  Sometimes however it takes a teacher to show you how.

Math:  After learning Calculus, Matrix Algebra, and Differential equations, it took some physics classes for me to realize the applications of this math.

Turing:  Its important to understand what is uncomputable because it offers a realistic boundary for our imaginations on what programs/computers can really do for us.  I'm not saying that letting our imaginations run wild is dangerous, but we ought to understand that we cannot create programs that will debug any code for us.  We cannot create a program that will see if another  program will solve a certain task.  And of course... if we want to tile our kitchens, we should do it ourselves.