Diagonalization argument - Revision history

Vipul at 02:14, 28 December 2011

2011-12-28T02:14:42Z

← Older revision		Revision as of 02:14, 28 December 2011
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~~. 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.

	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]]

Vipul at 02:03, 28 December 2011

2011-12-28T02:03:40Z

← Older revision		Revision as of 02:03, 28 December 2011
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.

Vipul: 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 ..."

2011-12-28T02:02:54Z

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 ..."

New page

==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 language]]s via the [[halting problem]].