Diagonalization argument: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
==Definition== | ==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 | 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. | ||
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. | 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. | ||
The rough idea behind the relevance of the diagonalization argument is as follows: The number of available Turing machines is ''small'' because any Turing machine can itself be described by a string that is input to a universal Turing machine. On the other hand, the number of languages is ''large'' because it involves choosing arbitrary subsets of the set of all permissible strings. Thus, we can mimic the diagonalization argument and try to derive a contradiction from the assumption that all languages can be decided by machines. | |||
==Examples== | |||
* The existence of [[undecidable language]]s, i.e., it is possible for there to be a language such that membership of the language cannot be decided by any Turing machine. | |||
* The unsolvability of the [[halting problem]], i.e., it is not possible to construct a Turing machine that can take as input a string and the code for a Turing machine and determine whether the Turing machine will halt on that string. | |||
* [[Deterministic time hierarchy theorem]] | |||
* [[Nondeterministic time hierarchy theorem]] | |||
* [[Deterministic space hierarchy theorem]] | |||
* [[Nondeterministic space hierarchy theorem]] | |||
Latest revision as of 02:14, 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.
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.
The rough idea behind the relevance of the diagonalization argument is as follows: The number of available Turing machines is small because any Turing machine can itself be described by a string that is input to a universal Turing machine. On the other hand, the number of languages is large because it involves choosing arbitrary subsets of the set of all permissible strings. Thus, we can mimic the diagonalization argument and try to derive a contradiction from the assumption that all languages can be decided by machines.
Examples
- The existence of undecidable languages, i.e., it is possible for there to be a language such that membership of the language cannot be decided by any Turing machine.
- The unsolvability of the halting problem, i.e., it is not possible to construct a Turing machine that can take as input a string and the code for a Turing machine and determine whether the Turing machine will halt on that string.
- Deterministic time hierarchy theorem
- Nondeterministic time hierarchy theorem
- Deterministic space hierarchy theorem
- Nondeterministic space hierarchy theorem