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 edit summary |
||
| Line 2: | Line 2: | ||
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 language]]s via the [[halting problem]]. | 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 language]]s via the [[halting problem]]. | ||
These arguments are adaptations of the [[Canton diagonalization argument]] that shows that a set (whether finite or infinite) cannot be put in bijection with its power set. | |||
Revision as of 02:03, 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.
These arguments are adaptations of the Canton diagonalization argument that shows that a set (whether finite or infinite) cannot be put in bijection with its power set.