Timeline for Is there any concrete relation between Gödel's incompleteness theorem, the halting problem and universal Turing machines?

Current License: CC BY-SA 3.0

7 events

when toggle format	what		by	license	comment
Mar 5, 2018 at 15:44	comment	added	Wei Zhan		But diagonal argument is indeed a constructive proof. Along your reduction to Cantor's Theorem, the undecidable language is the set of all the machines whose encoding is not in its accepted language.
Apr 13, 2017 at 12:32	history	edited	CommunityBot		replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Jun 29, 2012 at 16:37	history	tweeted			twitter.com/#!/StackCompSci/status/218745076048871426
May 18, 2012 at 18:05	comment	added	Hernan_eche		Understood, you are very clear, I agree the counting argument is not totally satisfactory, but even without the example, I think perhaps the worst part is that $L\subseteq \Sigma^$ is infinite, then there is no big surprise in saying there are undecidable languages, would be great to extend (better said to limit*) the reasoning for a finite case, ( I am not asking for an example of an undecidable problem), but a similar proof (or disproof) being valid for a finite set of input admited instead of $\mathbb{N}$
May 17, 2012 at 22:57	comment	added	Dai		@Hernan_e There's no "difference" really. A decision problem in computation theory can be defined as any yes-or-no question on the set of inputs $x\in \Sigma^$. Thus, we can assign each decision problem $P$ to the set $L\subseteq \Sigma^$ of inputs for which the answer is yes. The set $L$ is the language defined by the problem $P$.
May 15, 2012 at 16:24	comment	added	Hernan_eche		+1 This is a more simple approach, but I still doubt about this: "and thus we know there must exist an undecidable language." Could you specify the difference between undecidable language and undecidable problem?
Mar 17, 2012 at 15:45	history	answered	Dai	CC BY-SA 3.0