5

I took a Theory of Computation class years ago through my university's math department that I really enjoyed and found interesting. If I wanted to further pursue study/research/specialization with Theory of Computation what what kind of Ph.D program should I be looking for? Computer Science or Math. I am leaning towards Math grad school since I not inclined to take take classes about Database and OS design.

Has the prevalence of computer science programs in major universities during the past 30 years made the new researcher in the Theory of Computation normally a CS grad student or is it normal for pure math grad students specializing in theory of computation?

  • 8
    I am leaning towards Math grad school since I not inclined to take take classes about Database and OS design. — That is a really terrible reason. – JeffE Dec 29 '15 at 19:39
  • You might consider programs specific to ToC like Georgia Tech's "Algorithms, Combinatorics, and Optimization" PhD program. But you might also find that the course requirements (at least for the ones you don't like) are not that heavy in CS programs. – David Cash Dec 29 '15 at 20:15
  • 1
    I am surprised at someone going into theory of computation in an era of big data wanting to avoid studying databases. – Patricia Shanahan Dec 29 '15 at 20:59
  • 3
    @PatriciaShanahan: I think you might be unintentionally insulting pure mathematics. – Alexander Woo Dec 29 '15 at 21:26
  • 2
    What specifically do you mean by Theory of Computation? – Oswald Veblen Dec 30 '15 at 1:56
6

Generally speaking, in the US, the theorists will be in the computer science department, but it will not be hard to make arrangements for you to work with them as a student in the math PhD program.

Would you prefer to TA and eventually teach introductory programming courses, or calculus courses? That's probably going to be the biggest difference (especially down the line after you graduate) between the two options.

|improve this answer|||||
  • 4
    "Theorist" can mean many things - what do you mean by it? Almost none of the computability theorists I work with in the U.S. works in a computer science department. I think there are quite severe topical and methodological differences between a PhD in math and a PhD in computer science; there is an intersection in some cases, but the two fields are not at all interchangeable. The prerequisites are also not at all the same - in math, you will almost certainly have to pass a qualifier in analysis or abstract algebra, while in computer science the qualifiers will be about other topics altogether. – Oswald Veblen Dec 30 '15 at 1:57
  • @OswaldVeblen: I meant the subfield whose primary long-term aim is to resolve P vs NP and related problems. Usually that's called something like "complexity theory", whereas I think the subfield you are referring to I usually here spoken of as "recursion theory" (which I agree is studied in mathematics departments). – Alexander Woo Dec 30 '15 at 6:54
4

I can't say much about the CS side, but I can write about what it would mean to study computation on the mathematics side. Perhaps if someone else writes about the CS side, the OP can compare.

In mathematics, computability is studied as part of mathematical logic. The key initial concept is Turing computability, but the focus is just as much on non-computable objects. So the structure of the Turing degrees is a key topic at first. Within computability theory, there are many areas: "classical" computability, higher computability, Reverse Mathematics, computable analysis, and crossover with areas such as proof theory, effective model theory, and effective descriptive set theory. Topics such as computational complexity theory, compiler/language theory, and automata are not studied as often in mathematics departments.

The methods used are very mathematical. Mathematical computability theorists tend to focus much more on proving results than on implementing anything. For your qualifying exams, you will need to learn several other basic areas of mathematics at an introductory graduate level, such as real analysis and/or abstract algebra. An undergraduate degree in mathematics, or very good mathematical preparation otherwise, is required to be admitted to a PhD program in math.

The field of computability is not extremely large, which can make both finding a PhD program and finding an academic job more challenging. Essentially, mathematical logic as a whole is only as big as a subfield of many other areas of logic, and then computability theory is only a part of mathematical logic.

|improve this answer|||||
1

Check the curricula of prospective schools, contact potential advisors/research groups. I'd wager that graduate studies in theoretical computer science will rarely include the kind of subjects you want to avoid, at least not as mandatory classes.

|improve this answer|||||
0

I was just in this situation, graduating with a PhD in Theory of Computing. I would recommend looking for an Applied Math department. Although most applied math departments are oriented to scientific applications (like partial-differential equations), you may find that they offer a great deal of flexibility in coursework. I was able to take all the math classes and all the CS courses I wanted. I was able to skip a lot of the non-theory CS classes (operating systems, databases, etc.) and a lot of math classes that didn't appeal to me either (analysis, algebra, etc.)

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.