Diagonalization argument

From Complexity
Revision as of 02:02, 28 December 2011 by Vipul (talk | contribs) (Created page with "==Definition== A '''diagonalization argument''' is a general format of argument that is used to show the existence of a language that lies outside a certain complexity class or ...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Definition

A diagonalization argument is a general format of argument that is used to show the existence of a language that lies outside a certain complexity class or cannot be decided by machines of a certain type. The classic application is to showing the existence of undecidable languages via the halting problem.

Retrieved from "https://complexity.subwiki.org/w/index.php?title=Diagonalization_argument&oldid=49"