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

5 events

when toggle format	what		by	license	comment
Oct 13, 2021 at 19:42	comment	added	user21820		@MarcvanLeeuwen: See here for more, namely not only a computability-based proof of the completely generalized incompleteness theorem, but also an explicit independent sentence. My post was inspired by Scott Aaronson's blog post, but goes quite a bit beyond that.
Mar 25, 2012 at 1:36	comment	added	Marcos Villagra		There is another proof in a similar vein in the book The Nature of Computation (amazon.com/gp/cdp/member-reviews/A2DGFHJVZ92HVI/…) in the chapter about computability. There, the authors avoid the use of Rosser's theorem and only assume the existence of universal machines (i.e., Church-Turing Thesis). The exact reference is section 7.2.5 page 238.
Mar 24, 2012 at 15:53	vote	accept	Marc van Leeuwen
Mar 24, 2012 at 15:53	comment	added	Marc van Leeuwen		Thank you for this link, I'll accept for now as this comes closest to my concerns. At first I was quite disturbed though: I misunderstood "complete" to mean "every truth is a derivable" (a converse to sound) rather than "if $P$ is not derivable then $\lnot P$ is" (a converse to consistent). Scott Aaronson seems beleive the meaning of "complete" is evident to the audience, although he doesn't seem to assume a logician audience (which I certainly am not); with my misunderstanding what he writes makes no sense. Having found my error, I find the post quite interesting.
Mar 21, 2012 at 6:56	history	answered	Marcos Villagra	CC BY-SA 3.0