Biography of a Computing Pioneer: David Huffman

     "I enjoy pushing things to their theoretical limits." A quote from David Albert Huffman. The biography of David Huffman begins in Ohio on August 9, 1925, where he was born. He got a quick start in life when he earned his B.S. in Electrical Engineering from Ohio State University at the age of 18. After receiving his B.S., he served two years as an officer in the U.S. Navy as a radar maintenance officer. As a radar maintenance officer he served on a destroyer that helped clear mines in the waters around Japan and China after World War II. Following serving in the Navy, Huffman returned to Ohio State to earn his Master's Degree in Electrical Engineering.
     In his final year before receiving his Master's, his professor in a class on information theory gave Huffman and his classmates the option to write a term paper or to take a final exam. The topic, or, I should say, problem, of the term paper was to find the most efficient method of representing numbers, letters or other symbols using a binary code. At first, it appeared to be a simple problem, but after working on it for months he decided to start studying for the final. As he was throwing away his notes, the solution hit him. "It was the most singular moment of my life," says Huffman. "There was the absolute lightning of sudden realization."
     This solution is now knows as the "Huffman Code." The Huffman Code was, and still is, used in many machines. What it is, is an algorithm that finds the frequency of all the characters (letters, symbols, and numbers) in a document. After that, it, basically, creates a tree with the most common character used, at the top. Now, depending on whether the first character is represented as a 0 or a 1, the tree will flow left or right, respectively. The sum of all of the probabilities will always be less than or equal to one. This "tree" is what's known as "biunique," which means the code is the code is "uniquely decodeable," or it can only be decoded in one way, ensuring that the final product is a correct document. (To learn more click on the last link at the bottom)
     After coming up with the Huffman Code and receiving his Master's, he proceeded onto MIT where he received his Doctor of Science in Electrical Engineering. He recognizes that he is best known for his code but Huffman says he is most proud of his doctoral thesis. It may be the first formal methodology for devising asynchronous sequential switching circuits, which is an important type of computer logic. This also helped him receive a faculty position at MIT.
     In 1967, Huffman left his full time position at MIT and moved to the University of California at Santa Cruz in order to become the first head of it's new computer science department. He was there until 1994, but remained active teaching information theory and signal analysis courses.
    Even though he was such an intelligent and innovative thinker, in October, 1999, David Huffman died at the age of 74. Throughout his life he received various awards, they are:

• 1955: The Louis E. Levy Medal From the Franklin Institute for his doctoral thesis on sequential switching circuits
• 1973: The W. Wallace McDowell Award from the IEEE Computer Society
• 1981: Charter recipient of the Computer Pioneer Award From the IEEE Computer Society
• 1998: A Golden Jubilee Award for Technological Innovation from the IEEE Information Theory Society
• "For the invention of the Huffman minimum-length lossless data-compression code"
• 1999: The IEEE Richard W. Hamming Medal
• "For design procedures of minimum redundancy (Huffman) codes and asynchronous sequential circuits, and contributions to analysis of visual imagery."

Thanks to:

• http://en.wikipedia.org/wiki/David_A._Huffman
• http://www1.ucsc.edu/currents/99-00/10-11/huffman.html
• http://www.huffmancoding.com/my-uncle/scientific-american
• http://www.princeton.edu/~achaney/tmve/wiki100k/docs/David_A._Huffman.html
• http://www.ieee.org/documents/hamming_rl.pdf
• http://www.computer.org/portal/web/awards/pioneer#_118_tabs_WAR_pluginsui_INSTANCE_d0QT_tab2
• http://en.wikipedia.org/wiki/Huffman_coding#Problem_definition

How Connected Are We?

     How connected are we? That's an interesting question. Throughout time people have been more or less disconnected from other people. Until the 1830s no one could be contacted unless you went to talk to them yourself or if you wrote them a letter, both of which would take about the same amount of time. The telegraph, starting about the 1830s, allowed messages to be sent over great distances but it still wasn't perfect. The telegram either had to be delivered to the person addressed or they had to go pick it up. In the 1870s Alexander Graham Bell patented the phone (http://inventors.about.com/od/bstartinventors/a/telephone.htm) and then phones were the next best way of communication. Phones brought people a little closer, in that they could call someone anywhere that they had a phone. After it was first introduced, the phone eventually was made smaller and smaller. Eventually, sometime it the 1980s, it became handheld and portable, now known as the cell phone. Although, not long after that, the internet was invented and people use it every day to communicate around the globe.
     With the internet came e-mail, which allowed for almost instant communication through text sent from one email address to another. Instant messaging had already been developed even before the internet. But, after email came social networks. The first being SixDegrees.com, which only lasted a few years and progressing from there. Some early Social networks are LiveJournal and LunarStorm. Starting in 2003 the social networking industry exploded. With websites such as Friendster (2002), LinkdIn, MySpace, Last.FM, and Hi5 popping up, they all continued to bring people from all over the world closer and closer. Today, there are many different social networks online such as Bebo, Facebook, Flickr, LinkedIn, MySpace and Google+.
     All of these technologies have brought people closer together. With the internet, not only through social networking sites, people in America can meet people in Europe through online video games, both on the computer or a console. Cell phones have also helped connect people.
     Cell phones have, and continue to get smaller and more powerful. With a cell phone you can make calls to anyone in the world who has a phone (though it may cost you a small fortune to do so) and you can text someone, which is almost the same as instant messaging them. Since Blackberry came out with phones that could e-mail, the things phones could do has increased exponentially. Now, with a smartphone, people can not only call and text, but they can access all of the social networking websites and connect to people all over the world. Connect to people that are on computers and also on their phones as well. They can still e-mail and instant message people through almost any IM service. Some phones have more computing power than the spaceships that landed on the moon.
     As to the question, "How connected are we?" I think, as a population, we are almost completely connected. Although, I don't think there is a definite answer, such as a number, there is only a concept. Internet and cellphone towers aren't everywhere, but they almost are. Being so thoroughly connected, I think at times it can be a good thing but I've noticed that people around me, and me as well, are very dependent on this ability to be constantly connected and it can even be a need.

Turing Completeness

     To discuss Turing Completeness, one must first explain that it all (it being the term "Turing Completeness" and everything it encompasses) started with a man named Alan Turing. Turing was born in London, England in June 1912. He was a mathematician, logician, cryptanalyst, and a computer scientist. He invented the Turing Machine. It was a theoretical invention, meaning it was never actually built by him, and, until recently, no one had successfully. Those that succeeded used more advanced parts than Turing had in his time. Such as an electronic scanner. One was even built out of Legos which I think is really cool. (http://www.wired.com/underwire/2012/06/lego-turing-machine/) It was a machine that, given it had access to an infinite roll of tape, could read, write, and erase symbols, such as binary, on that infinite strip of tape according to a table of rules. The table of rules included the implementation of any computable algorithm. The machine would read what was written on the tape then, depending on what was written, usually instructions, it would perform the calculation by writing the answer. Or, if the instruction was to change something that was already written it would change it. The following video does a great job showing the the Turing machine and how it works. http://www.youtube.com/watch?v=E3keLeMwfHY
     Which brings us to Turing Completeness. The Turning Machine was originally thought up to represent computing machines, so when something is Turing Complete it means that it can be represented on a Turing Machine. When deciding whether or not something is Turing Complete one does it without regard to run time or memory usage. It's not about the efficiency, only about the capability. Some people are confused and think that being Turing Complete is about being able to do everything, but it is about the ability to do calculations that a Turing Machine can. It is also about the ability to run forever. Since the Turing Machine is designed with an infinite amount of tape to manipulate symbols on whatever is Turing Complete it must have the ability to run forever, although it doesn't have to run forever.
     The majority of things that are Turing Complete are abstract and not physical entities. Nearly all computer programming languages, such as Java, C, C++, and Pascal, are Turing Complete because they can do any calculation. Also, by using loops and GOTOs they can also run forever. These programming languages differ in how the calculation will be performed, such as the number of loops required, and as stated before maybe not as efficiently as another, or the speed. While it could be using a loop it could just be using a GOTO statement or  recursions, they have the ability to run forever. While most programming languages are Turing Complete there are many that aren't. The largest language I found that isn't Turing Complete, while still being general-purpose, is SQL because without recursion, dynamic SQL, or the WHILE loop it is guaranteed to stop and not run forever.
    All of this is important to computer scientists. Turing was the first computer scientist and knowing what it means to be Turing Complete is important because when asked to do calculations you'll know that some languages can't do all of the calculations you may need to do infinitely.

An Early Computing Machine: The "Millionaire"

     Originally designed by Frenchman Leon Bollee, but later designed and sold by Otto Steiger from St. Gallen, Switzerland, the Millionaire was the first commercial machine to successfully multiply without repetitive addition. It could also divide, add and subtract although it was primarily used for multiplying. There were 4655 units produced and sold between 1893 and the mid 1930s. They were produced by Hans W. Egli and his company H. W. Egli, A.G. It was mostly used by big businesses and industries that used multiplication and other functions every day. Industries such as the insurance, the mining, and the railways industries used it the most at first. Later on, scientists found it useful and government agencies became the prime customers. There was no other machine like it and none were able to compete with it until fully-automatic rotary calculators became available in the 1930s.

The Millionaire machine of Steiger/Egli (Courtesy of Mr. John Wolf and of history-computer.com)

     The Millionaire was operated by the control panel, which was located on the top of the machine just inside the top opening. The control panel, divided into 4 unequal sized section, is about 25" x 11". The right of the upper section contains the control that specifies which calculation is to be done, Add, Multiply, Divide, or Subtract (AMDS), that is knows as the "Regulator". That section also includes the crank which was used to conduct the calculation. As said above, the crank is replaced later on in the 1930s with the automated rotary calculators. The crank is only required to do one full turn clockwise for each calculation. It will come to a stop at its fixed home position. The crank should not ever be turned backwards. To the left of the crank and Regulator is the section that contains eight sliders for the input. The input from these sliders is used as the first factor. Left of the eight input sliders is the "multiplier control lever." It sets the second factor.
     The final section, the bottom half of the control panel, basically displays the answer. It contains an opening for the 8-digit counter and the 16-digit accumulator register. The knobs to the right of each display can be pulled to the right to clear the display. During multiplication and division the carriage is moved automatically to the left, and is pushed back manually while pressing the button at the left side.
     The Millionaire calculates and displays the answer in two separate steps, first the tens place then the units. For example, if someone were to multiply 8 by 7, they would think of the answer as a single number 56. The Millionaire knows the answer first as 5 tens and then as 6 units. When the first factor is selected it engages the respective pinion. Then after the second factor is selected and the crank is turned the pinion will move the display to the correct tens and unit places. So, when the 8 slider is selected it will engage the pinion to rack 8. Then selecting the 7 multiplier it will move 5 places in the tens cycle and 6 places for the units. Then the machine will display the appropriate answer, in this case 56.