In computability theory, Putnam investigated the structure of the ramified analytical hierarchy, its connection with the constructible hierarchy and its Turing degrees. He showed that there are many levels of the constructible hierarchy that add no subsets of the integers and later, with his student George Boolos, that the first such "non-index" is the ordinal formula_4 of ramified analysis (this is the smallest formula_5 such that formula_6 is a model of full second-order comprehension), and also, together with a separate paper with Richard Boyd (another of Putnam's students) and Gustav Hensel, how the Davis–Mostowski–Kleene hyperarithmetical hierarchy of arithmetical degrees can be naturally extended up to formula_4.