Post's theorem

In computability theory, Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.

This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.