A complexity-theoretic proof of a Recursion-Theoretic Theorem

ABSTRACT

It is well known that Complexity Theory inherited many tools from Recursion Theory. This note is an example where tools from Complexity Theory simplify the proof of a Recursion Theoretical result, illustrating the value of mingling the two subjects.

REFERENCES

• 1: Jones, Neil D. (1997) Computability and Complexity. MIT Press, Cambridge, Mass., 1997.
• 2: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 3: Robert I. Soare, Recursively enumerable sets and degrees, Springer-Verlag New York, Inc., New York, NY, 1987