To be sure, you certainly didn't mean it this way, but for the sake of the poor guy who has seen GEB touted as one of these books that "every programmer/computer scientist/CS major has to read" and sees your post in the same light:
You don't have to read GEB. You will be a fine techie without reading it. And you'll be a fine person in general without reading it. There is no spiritual revelation you can only get from GEB or some important technical knowledge that you'll get that you wouldn't get from a normal CS degree program. Try it out and see if you enjoy Hofstadter's writing - if you do, you might be in for a really enlightening and enjoyable experience. If you don't, no worries - your time is better spent elsewhere - there is no need to put yourself through the pain of slogging through a >700 page book that you don't enjoy. There are many other perfectly fine entry points for learning about topics in computer science, cognitive science, or philosophy of mind.
Right. And to be sure, GEB might have Godel in the name, but it's not really a book about Godel's incompleteness theorems. It mentions them, but that is not really the main thrust of the book. It's not a book about Godel, Escher, and/or Bach, really (though of course it discusses the ideas of these three people a lot). Hofstadter, if I recall correctly, even says as much (or something along these lines) in the preface.
So of course, there are more to-the-point resources for the technical concepts that Hofstadter employs. It's an understandable misconception to have when people so often say GEB is a must-read for techies and when it has a name that includes "Godel". So remember - GEB is about Hofstadter trying to argue for a point about a particular thesis (how the mind ("I") arises from the brain), and to that end, he employs many different concepts (many of which are from computer science) and explains them poetically (at least, a lot of people think so). But teaching you these concepts is just a secondary, even tertiary, goal of his. If you find his writing engaging, it might be a more fun way to learn about that stuff - but if not, don't worry, GEB wasn't primarily written to teach you anyway. I'm sure even the biggest GEB fans will agree.
It sounds like you're making a distinction between the plot and the theme.
I'd argue the plot is entirely about Godel's incompleteness theorem. It's not just "mentioned in passing", the entire book is centered around a series of increasingly complex explanations that culminate in explaining the actual theorem itself.
But just like a good novel is way, way more than just the plot, GEB is way more than just the Godel incompleteness theorem.
Personally I didn't really find any other thesis or theme that compelling. However, I absolutely loved the clever ways in which he illustrated each concept. Others may have appreciated other aspects of it, and that's great too. Many people can enjoy the book for different reasons.
The Godel proof chapter feels like the apotheosis of the book. The rest almost feels tacked on, e.g. the whole dna-computing ... , even the "strange loops" part, which I would not think is the main crux of the book.
I shouldn't have said "mentioned" to insinuate "mentioned in passing", you are right. But no, though it plays a central role in his argument, GEB is not about Godel's incompleteness theorem (I believe Hofstadter even says as much in the preface, and he laments that readers didn't get the overall point of the book - though I don't have my copy with me to confirm, so I might be misremembering exactly what he says).
But anyway - you and anyone else of course are free to enjoy Hofstadter's explanations of Godel's incompleteness theorem - maybe you even think that it is the best/most interesting/most fun/most insightful explanation. I just mean to say that Hofstadter isn't writing this book primarily to explain technical concepts - his explanations are a means to an end. So someone who struggles to get through this book shouldn't feel bad - its main goal was never to be a "must-read for programmers" anyway.
Never understood this logical jump in reductio ad absurdum argument. "If one finds a contradiction, therefore the initial premise is wrong". The argument always assumes a binary state, either true or false. It excludes another valid state which is "undefined". The premise of the video above is effectively to prove that one can't build a machine that is capable of resolving a paradox. As if computers have limited capabilities and that they are uncapable to reason the way humans can. But that's not true. If you allow a machine to produce 3 answers, "yes", "true" and "unresolvable", then it is very much possible to build such a machine that produces such output, i.e. detects that a problem is indeed a paradox. By simply implementing this reductio ad absurdum algorithm.
The halting problem asks, "Is it possible to write a program which correctly outputs YES or NO to the halting question for every possible input which is the code of a program?"
The binary requirement comes from the question, not a failure to think differently. The consequences of binary requirement with completeness (correct output for every input) is the point.
If you modify the question as you suggest, to output UNRESOLVABLE in exactly the cases where the input is a paradox, that doesn't work either. It is not possible to reliably detect every self-referential paradox, for reasons analogous to (but more complicated than) it not being possible to reliably say for every program if it will eventually halt.
Even so, it is possible to write a program which outputs UNRESOLVABLE in cases where that particular implementation of a halt-test program gets stumped and gives up despite there being another correct answer it hasn't found, or when it detects specific patterns. But that's more about hitting arbitrary limits of a particular implementation, so not as interesting theoretically. It is what you'd do in practice, if someone asked you to write a halting detector in the real world.
The halting problem computation model has unlimited memory. Sometimes people say this means you can "solve" the halting problem in practice because real machines have bounded memory, therefore finite states, which must eventually repeat if a program does not halt. But this isn't really a solution, because the halt-test program needs exponentially more memory than the input program would be allowed if run. However you look at it, that is not "in practice", it is prevented by computational inaccessibility, and it also doesn't satisfy the principle of the halting problem, which is to ask if halt-test can be written in the same kind of universal programming system as the programs it analyses. (Besides, you can run programs with unlimited memory, by always being willing to pause, upgrade machine, and resume, whenever current memory is filled.)
When analysed with denotational semantics, there actually is a third output called "bottom" (⊥) which means "mathematical value representing doesn't terminate". But even using mathematical approaches, there is no way to calculate when that's the output for all possible inputs to a correct halt-test function.
although, as schoen and jlokier have patiently explained, you're mistaken about the halting problem, it's a productive and interesting mistake, and others have taken your line of thinking a great deal further than you have even begun to imagine! you may be interested in reading about their work: https://en.wikipedia.org/wiki/Intuitionistic_logic
In fact, there is an obvious way how to build a machine that tells whether the program will stop or not. One only needs to track all the states that the machine was in, and if a program enters a state that was already encountered before then it's obviously stuck. And there are only that many permutations of possible states that machine can be in. So a number (time) can be given of when the result will be guaranteed to be found (which of course could be beyond physical resources of the universe, but mathematics are fine not to take those into account)
This is totally true for some models of computation (including some studied in academic computer science), but it's not true for the models of computation that the halting problem applies to, like the Turing machine, which explicitly has an infinite tape and therefore has the potential for an unbounded number of machine states.
In fact, this unboundedness is a core part of what makes these models of computation so expressive. In the Gödel's incompleteness theorem analogy, you can say "there is an integer such that ..." or "there is no integer such that ...". In the Turing machine model, you can write programs that search for counterexamples to mathematical claims. Because these programs are written to try every integer, you can only tell if they eventually halt by yourself resolving the mathematical claim.
For example, we can write a program that tests the Goldbach conjecture or the 3n+1 conjecture by brute force. Determining if these programs' search through all integers will halt or not is equivalent to resolving the status of these conjectures!
Here's an example of a Python program whose halting behavior -- if run on a hypothetical Python interpreter with infinite RAM and the ability to make use of it -- is currently unknown. It looks for counterexamples to the 3n+1 conjecture, and it tries every integer to see if it's a counterexample.
start = i = 1
visited = []
while True:
if i in visited:
if 1 not in visited:
break
else:
print(start, visited)
visited = []
start += 1
i = start
continue
visited.append(i)
if i % 2:
i = 3*i + 1
else:
i //= 2
On an actual computer's Python interpreter, I believe this will eventually halt with a MemoryError exception (although I'm not at all sure that you can actually run it long enough to hit that, as it will probably take many years!), failing to resolve the mathematical question. That potential for the MemoryError is why it matters whether your model has infinite memory or not!
(You can make a considerably more memory-efficient version of this which should be able to search much further before hitting a MemoryError, but I don't expect it changes the ultimate fate of the program when run on a real physical computer.)
To be sure, you certainly didn't mean it this way, but for the sake of the poor guy who has seen GEB touted as one of these books that "every programmer/computer scientist/CS major has to read" and sees your post in the same light:
You don't have to read GEB. You will be a fine techie without reading it. And you'll be a fine person in general without reading it. There is no spiritual revelation you can only get from GEB or some important technical knowledge that you'll get that you wouldn't get from a normal CS degree program. Try it out and see if you enjoy Hofstadter's writing - if you do, you might be in for a really enlightening and enjoyable experience. If you don't, no worries - your time is better spent elsewhere - there is no need to put yourself through the pain of slogging through a >700 page book that you don't enjoy. There are many other perfectly fine entry points for learning about topics in computer science, cognitive science, or philosophy of mind.