My Professor was just going over this in class. He links to Manuel Blum's "classic" paper on the subject http://www.mathunion.org/ICM/ICM1986.2/Main/icm1986.2.1444.1...