Introduction to Computability Theory

My research interests lie in mathematical logic particularly Computability Theory. That is I study in some very abstract sense what computers can theoretically calculate. Quite surprisingly it turns out that even with unlimited time and memory there are some perfectly well-defined questions that a computer can't be programed to answer. The most famous example of this phenomenon is the halting problem. Sometimes computer programs can get stuck in infinite loops never yielding useful output and one might hope that you could write a computer program VERIFY(s) that takes as input the code s to some program (we assume s doesn't require any input and can output only a single value) and tells you if program s every gets stuck in an infinite loop. Surely there is a fact of the matter about whether any program s gets stuck in an infinite loop. Just run it and it will either spit out an answer or it won't. But no matter how cleverly you write the VERIFY program there will always be a program DO_OPPOSITE which contains the VERIFY program as a procedure and by examining it's own code in memory runs the procedure VERIFY on it's own code (code for DO_OPPOSITE). The DO_OPPOSITE then, like a willful child, purposefully does the exact opposite of what VERIFY says it does. So if VERIFY says DO_OPPOSITE gets stuck in an infinite loop DO_OPPOSITE immediately stops and spits out a result. If VERIFY says DO_OPPOSITE returns an answer DO_OPPOSITE promptly enters a mindless infinite loop.

Of course it's perfectly possible to write a VERIFY program that tells you some programs will get stuck in infinite loops and certifies others as infinite loop free. Computer language designers put a great deal of effort into making more and more useful partial versions of VERIFY but you can never write VERIFY so it always tells you the correct answer for every possible program. The VERIFY program isn't a special case, frequently one can employ the strategy of doing the opposite of what is expected (called diagonalization) to prove some problem can't be solved on a computer. Since it quickly gets boring just listing things computers can't do what we do in computability theory is relate the difficulty of various non-computable problems. For instance it turns out that if you could ask a magic oracle whether a given program gets stuck in an infinite loop you could also decide whether program P eventually enumerates the value n (i.e. returns n on some input) but you couldn't tell if P will enumerate infinitely many different values.

You might wonder why anyone should care about what computer programs that can consult magical oracles are able to accomplish since such oracles don't really exist. Well it turns out that whether or not some property can be captured in a mathematical formula with a particular number of quantifiers, e.g., is there a boy that every girl loves would use an existential followed by a universal quantifier, is closely related to the existence of programs which can use certain oracles. In other words often thinking of the problem in terms of writing or diagonalizing against a computer program gives a better way to attack other questions in math and logic.

You can find more details about my mathematical research and results in the math section of this website.