People close to me are excited by my pursue of PhD, and this is the question they’d like to know the answer.
Imagine a group of people gather around me. When I say “It’s a math topic”, half will leave. When I add “in automated reasoning”, another half will leave.
Math is one of the main subjects in education, and we do math everyday (how much is 30% off), but few are interested in math upon leaving school. Most think of math as calculations, which can be tedious. Some may be remember the tricky math problems, only the smart ones can solve them. Others may recall the frustration with math proofs, and conclude that proving math should be reserved for those with a different brain structure.
So, how am I going to explain what I’m doing to ordinary folks?
I think I’ll start with something everyone is now familiar with — sending text messages, via a mobile phone or the computer.
Once the message is sent, the words, which are symbols, are converted into numbers. There are several levels of this conversion:
- the first level is rather like old-fashion telegraph, where alphabets are coded into digital patterns. Although the details are a bit involved, they are essentially similar to putting A=1, B=2, C=3, etc.
- the second level is about secrecy. The message is supposed not to be readable by a third party, so the coded alphabets will be scrambled in a certain way, called encryption. When the numbers reach the other end, they will be unscrambled, reversing the encryption process, called decryption, so the recipient can read the message.
- the third level is about transmission. In order for the encrypted numbers to be reliably transmitted through a path that is not expected to be error-free, some extra information, or redundancy, are inserted to enable the receiving end to, at least, check if an error has occurred, and, preferably, to recover the intended numbers by a process called error-correction.
These underlying processes in message conversion clearly show that symbols are being handled as numbers, probably in ways you’ve never imagined — all these things happen at the push of a button! All these levels need math, both the theory to show why the method works, and the computations to actually carry out the processes.
On the other hand, numbers are just special symbols. Most civilizations used one-stroke for 1, two-strokes for 2, and three-strokes for 3. After that, the problem “how many more symbols should be invented?” becomes a struggle to the civilization. Even today we keep inventing prefixes – like K for kilo, M for mega, G for giga, T for tera — to describe larger and larger amounts. The name “Google” originates from a misspelling of “googol”, a number represented by a 1 followed by 100-zeros.
Looking at numbers as symbols is a shift in perspective. Once you take this view, math computations become symbolic manipulations: follow rules to move symbols around. That’s what computations really are. By doing so, computers can “compute” a lot of things: the pixels to give a picture, the sound to play a song, both color and sound to play a video. All information are symbols.
Back to math. Besides computations, math people are busy with another activity: proving theorems. On the surface, the process involves reasoning in logic; but most mathematicians hold the view that the reasoning steps can be broken down into elementary rules of moving logical symbols around. Hence, taking another shift in perspective, it is possible to do math proofs by math computations. This technique is called “automated reasoning”.
My project is to apply automated reasoning to investigate a well-known method in modern day communication. The method is used in error-correction of signal transmissions, e.g. wireless networks (Wi-Fi). The method is also used in efficient generation of random-looking bits for signal encryption (in mobile phones) as well as signal synchronization (in GPS devices). The fact that this method can be used in many different ways is fascinating. I would like to show clearly what is the shift in perspective behind the scene.
It is by shifting of perspective that researchers reveal new ways of looking at things. Sometimes these new ways of looking can lead to new ideas, enabling advance in technology. The IT revolution of the past decades is evidence of this happening — researchers solve various technical problems by shifting of perspective.