In recognition of his seminal paper with Richard E. Stearns which established the foundations for the field of computational complexity theory, Hartmanis was awarded the Turing Award in 1993.