Diagonalization argument: Difference between revisions
(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 ...") |
(No difference)
|
Revision as of 02:02, 28 December 2011
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.