Theoretical computer science concerns itself with complexity classes
and their relationships; most famously, the P vs. NP problem, of
whether solutions are easy to find whenever they are easy to check.
P and NP are roughly analogous to the classes of decidable and
recursively enumerable sets, since membership in an RE set can be
confirmed in finite time.
Sadly, we learned from Baker, Gill, and
Solovay that the diagonalization argument of Turing and Church cannot
possibly prove that P != NP. It was recently proposed that the
behavior of random NPcomplete problems near their phase transitions
might shed some light on P vs. NP; but as I will discuss, 3SAT and
XORSAT have similar statistical properties, even though 3SAT is
NPcomplete and XORSAT is in P.
I will end by commenting on
incomputability in physics. It is easy to prove incomputability
whenever we can engineer a computer out of tiles, atoms, or the like,
but I suspect that many physical problems may be incomputable even
when we cannot do this. In other words, I expect there are physical
problems that are incomputable, but not Turing complete.
