https://scottaaronson.blog/?p=8106 Shtetl-Optimized The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel. --------------------------------------------------------------------- << BusyBeaver(5) is now known to be 47,176,870 The Zombie Misconception of Theoretical Computer Science In Michael Sipser's Introduction to the Theory of Computation textbook, he has one Platonically perfect homework exercise, so perfect that I can reconstruct it from memory despite not having opened the book for over a decade. It goes like this: * Let f:{0,1}*-{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? ( Hint: The answer does not depend on your religious beliefs.) The correct answer is that yes, f is computable. Why? Because the constant 1 function is computable, and so is the constant 0 function, so if f is one or the other, then it's computable. If you're still tempted to quibble, then consider the following parallel question: * Let n equal 3 if God exists, or 5 if God does not exist. Is n prime? The answer is again yes: even though n hasn't been completely mathematically specified, it's been specified enough for us to say that it's prime (just like if we'd said, "n is an element of the set {3,5}; is n prime?"). Similarly, f has been specified enough for us to say that it's computable. The deeper lesson Sipser was trying to impart is that the concept of computability applies to functions or infinite sequences, not to individual yes-or-no questions or individual integers. Relatedly, and even more to the point: computability is about whether a computer program exists to map inputs to outputs in a specified way; it says nothing about how hard it might be to choose or find or write that program. Writing the program could even require settling God's existence, for all the definition of computability cares. --------------------------------------------------------------------- Dozens of times in the past 25 years, I've gotten some variant on the following question, always with the air that I'm about to bowled over by its brilliance: * Could the P versus NP question itself be NP-hard, and therefore impossible to solve? Every time I get this one, I struggle to unpack the layers of misconceptions. But for starters: the concept of "NP-hard" applies to functions or languages, like 3SAT or Independent Set or Clique or whatnot, all of which take an input (a Boolean formula, a graph, etc) and produce a corresponding output. NP-hardness means that, if you had a polynomial-time algorithm to map the inputs to the outputs, then you could convert it via reductions into a polynomial-time algorithm for any language or function in the class NP. P versus NP, by contrast, is an individual yes-or-no question. Its answer (for all we know) could be independent of the Zermelo-Fraenkel axioms of set theory, but there's no sense in which the question could be uncomputable or NP-hard. Indeed, a fast program that correctly answers the P vs. NP question trivially exists: * If P=NP, then the program prints "P=NP." * If P[?]NP, then the program prints "P[?]NP." --------------------------------------------------------------------- In the comments of last week's post on the breakthrough determination of Busy Beaver 5, I got several variants on the following question: * What's the smallest n for which the value of BB(n) is uncomputable? Could BB(6) already be uncomputable? Once again, I explained that the Busy Beaver function is uncomputable, but the concept of computability doesn't apply to individual integers like BB(6). Indeed, whichever integer k turns out to equal BB(6), the program "print k" clearly exists, and it clearly outputs that integer! Again, we can ask for the smallest n such that the value of BB(n) is unprovable in ZF set theory (or some other system of axioms) --precisely the question that Adam Yedidia and I did ask in 2016 (the current record stands at n=745, improving my and Adam's n=8000). But every specific integer is "computable"; it's only the BB function as a whole that's uncomputable. Alas, in return for explaining this, I got more pushback, and even ridicule and abuse that I chose to leave in the moderation queue. --------------------------------------------------------------------- So, I've come to think of this as the Zombie Misconception of Theoretical Computer Science: this constant misapplication of concepts that were designed for infinite sequences and functions, to individual integers and open problems. (Or, relatedly: the constant conflation of the uncomputability of the halting problem with Godel incompleteness. While they're closely related, only Godel lets you talk about individual statements rather than infinite families of statements, and only Turing-computability is absolute, rather than relative to a system of axioms.) Anyway, I'm writing this post mostly just so that I have a place to link the next time this pedagogical zombie rises from its grave, muttering "UNCOMPUTABLE INTEGERRRRRRS...." But also so I can query my readers: what are your ideas for how to keep this zombie down? Email, RSS Follow This entry was posted on Monday, July 8th, 2024 at 3:07 pm and is filed under Complexity. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site. 133 Responses to "The Zombie Misconception of Theoretical Computer Science" 1. skaladom Says: Comment #1 July 8th, 2024 at 3:35 pm But might the perfect reply to this post be uncomputable? OK OK I'll see myself out... 2. Scott Says: Comment #2 July 8th, 2024 at 3:47 pm skaladom #1: No, the perfect reply to this post is not uncomputable, as proven by the fact that you just computed it. 3. Andrew B. Says: Comment #3 July 8th, 2024 at 3:52 pm Maybe a small syllogism is enlightening? 1. All integers are computable 2. BB(6) is an integer 3. Therefore, BB(6) is computable The misunderstanding occurs, I think, in step (1), particularly in the data type of 'integer'. (It's integer.) 4. Gil Kalai Says: Comment #4 July 8th, 2024 at 3:57 pm Maybe some variant of the misconception still makes sense. Let me try: Let C be a (simple to state) mathematical conjecture. We can talk about three potential inherent obstacles for proving C: 1) Independence from ZFC, 2) There is a proof but any proof is too long for us to ever find. 3) There is even a short proof (that we can verify once presented to us) but it is computationally intractable to find a proof Regarding the third item, As Scott says, indeed it does not make sense to say "it is NP-hard to find a proof" because we do not have an asymptotic statement but a single instance. However, as we do believe that the asymptotic statements have a practical implications we can still say 3') There is a short proof, however, any algorithm for finding a proof takes too many steps for us to ever complete. Or if you want to refer to computational complexity you can say 3") There is a short proof, however, any algorithm for finding a proof requires more steps than running an algorithm for computing a 10000 by 10000 permanent. Some remarks: a) Also in the second item, it makes no sense to say "the length of the proof tends to infinity" but it does make sense to say, "the length of the proof is more than 10^10000 lines." b) Having said all that, while 2) and 3) seem valid inherent obstacles for proving a conjecture C (and maybe there are more possible obstructions), I am not aware of any specific example where one can expect them to hold. c) Referring specifically to the NP=!P problem adds some confusion but I don't think it changes matters. d) Some people believe that people's creativity can lead them to finding short proof so that there is no (practically) efficient algorithm for finding the proof. But I don't see any reason for that. 5. Dave Orr Says: Comment #5 July 8th, 2024 at 3:57 pm "I got more pushback, and even ridicule and abuse that I chose to leave in the moderation queue" Do you think you might be happier if you delegated moderation and didn't have to read that stuff? I bet it would be pretty easy to find a few volunteers to help. 6. Scott Says: Comment #6 July 8th, 2024 at 4:15 pm Dave Orr #5: Yeah, you're right. While I've been relying on a Committee of Guardians for the past couple years, maybe we should redesign things so that I don't even need to see comments until a Guardian has reviewed them. 7. Scott Says: Comment #7 July 8th, 2024 at 4:16 pm Gil Kalai #4: Yes, of course there can be individual mathematical questions to which we'll never know the answers, either because the shortest proof is too long or because it's too hard to find. Even in those cases, however, the tools of computability and complexity theory almost never let us make that sort of statement about the individual questions we care about. 8. Ching-Tsun Chou Says: Comment #8 July 8th, 2024 at 4:26 pm Well, what do you say about the common practice of dropping in a specific hash function (say, SHA-256, which plainly has collisions when the input size is greater than 256 bits) when, properly speaking, a collision-resistant hash is needed? Would you consider this to be an instance of "this constant misapplication of concepts that were designed for infinite sequences and functions, to individual integers and open problems"? 9. Pascal Ochem Says: Comment #9 July 8th, 2024 at 4:36 pm Or a fast program for a single diophantine equation that prints either "A solution is (42, 65537, 666, 47176870)." or "There is no solution." 10. Izzy Grosof Says: Comment #10 July 8th, 2024 at 4:36 pm Even more specifically than saying that BB(6) is computed by some program of the forn "print k", we can say that BB(6) is computed by some program of the form "run turing machine M to completion, then print how many steps it took to halt", for a finite list of programs M. We've identified a finite list of programs, one of which outputs BB(6). We just don't know which one. It's very akin to these "1 if this statement is true, 0 if it's false" questions. 11. Ernest Davis Says: Comment #11 July 8th, 2024 at 4:53 pm I am puzzled by Gil Kalai's #4 formulation 3': "There is a short proof, however, any algorithm for finding a proof takes too many steps for us to ever complete." I don't see how this helps. If there is a short proof F (short when written in Coq or Lean) of some particular statement (P != NP, Goldbach's conjecture, whatever), then there is an algorithm that finds the proof that runs quickly viz, print out F and verify it. A much more elementary but much more wide-spread close relative of this zombie is the unkillable tendency of people to use "exponential" to refer to some very large, specific, number. (In more technical writing I have also often seen "exponential growth" used to describe functions that were quite obviously quadratic growth, and at least once seen it used to describe a function with linear growth, albeit with a largish constant factor.) 12. rrb Says: Comment #12 July 8th, 2024 at 5:00 pm I think that Cooley's paper "The Re-Discovery of the Fast Fourier Transform Algorithm" is extremely interesting to get a sense of how non-obvious the idea of asymptotic analysis of runtime is. People looked right at the central idea of "unzipping" the sequence but it didn't stand out from other calculation tricks which only reduce the constant, as we now say. I think once you get the value of the asymptotic perspective, and I'm not sure how that happens, only then are you in a position to understand the concept of NP-hardness. To easily see that it doesn't apply to individual questions and only to sequences, I think you have to get the value of talking about sequences. Like, it shouldn't feel like a technicality or "gotcha". (EDIT: by the way, this time I tried to actually verify my e-mail address the way you want us to, but when I click the link in my e-mail it says "Your address could not be verified." Not sure how it looks on your end.) 13. Gary Drescher Says: Comment #13 July 8th, 2024 at 5:12 pm Perhaps a way to understand (and maybe slay) the zombie confusion is to focus on *why* complexity theory looks at infinite sequences. Complexity theory wants to talk about how hard it is to figure out the answer to "What is f(x)?". And intuitively, it makes perfect sense to ask how hard it is for some particular value. But if we ask about a particular value, we let the function cheat by hardwiring a constant answer and not doing any real work So in effect, the infinite-sequence limit is an indirect hack to rule out that cheating, because a finitely specified function can incorporate only a finite crib sheet. Past some finite point, the crib sheet runs out and the function is on its own and really does have to figure out the answer. Maybe then the solution is to be explicit that the infinite-sequence hack only partly succeeds in ruling out cheating, and thus only partially succeeds in formalizing the how-hard-is-it intuition. To avoid confusion, we have to be careful to notice when the formalism diverges from the underlying intuition, namely when asking about a specific value rather than an entire function. 14. Ernest Davis Says: Comment #14 July 8th, 2024 at 5:14 pm To some extent, there is a de dicto/de re ambiguity here. If you interpret the phrase "The value of BB(1000)" de re then the statement "The value of BB(1000) is uncomputable" is either false or meaning less. However, if you interpret it de dicto, then the same statement is true; no computation can establish the truth of a statement of the form "BB(1000) = XYZ... " where XYZ is the number written out in decimal notation. 15. Scott Says: Comment #15 July 8th, 2024 at 5:24 pm Ernest Davis #14: I don't agree that "BB(1000) is uncomputable" is known to be true "de dicto" (whatever that means in this context). Humans just figured out BB(5), which means that presumably a computation that simulated life on earth from its earliest days would eventually output BB(5) as well. Maybe God likewise has a program that eventually figures out BB(1000) "starting from nothing." 16. Ernest Davis Says: Comment #16 July 8th, 2024 at 5:50 pm I had thought for a minute that you might be able to get out of this by invoking Kolmogorov complexity: Asserting that the Kolmogorov complexity of the proof that P != NP is large. But obviously, that's wrong: if there is a proof of P != NP, then there is a proof with reasonably small Kolmogorov complexity (Small machine: generate all strings in sequence, and check each one until one of them is a proof of P != NP.) 17. Ernest Davis Says: Comment #17 July 8th, 2024 at 5:56 pm Scott #15. That's why I said "BB(1000)" rather than "BB(6)". My understanding is that you and Adam Yedidia proved that the value of BB(7910) could not be proved from ZFC and that this has been lowered to BB(745) by Johannes Riebel. 18. Joshua Grochow Says: Comment #18 July 8th, 2024 at 6:00 pm While those questions are indeed technically nonsensical - and its nice to have a place to point students to when they make such misconceptions, thanks! - there are still potentially good versions of them that do make sense and still try to get at what the OQ was asking. For example, re: "Is BB(6) uncomputable?" a technically sensical version of that question might be: is there a program p such that p(n), if it halts, outputs BB(n), p(6) halts, and such that K^{O (n)}(BB(6)|p) < K^{O(n)}(BB(6)) using some standard universal TM for the definition of time-bounded Kolmogorov complexity here (here I'm using linear-time-bounded Kolmogorov complexity to try to formalize the intuitive idea that "the value of BB(6) is not hard-coded into the program p"). Or we might even ask for something stronger like K^{O(n)}(BB(6)|p) < log K^{O(n)}(BB(6)). Similarly, "is P vs NP an NP-hard problem?" could be formulated (with a bit of a change to NP vs P/poly) as: is it NP-hard to decide, given n,k in unary as input, whether there is a Boolean circuit of size at most k that solves SAT up to length n? Indeed, formalizations along these lines lead to some interesting conditional results in proof complexity about the hardness of proving finitary versions of P vs NP (as this one) in various proof systems. 19. Scott Says: Comment #19 July 8th, 2024 at 6:22 pm Joshua Grochow #18: Yes to all of that! P vs NP absolutely has profound self-referential aspects; they're just not as simple as people want them to be... 20. Scott Says: Comment #20 July 8th, 2024 at 6:24 pm Ernest Davis #17: We did show that, but ZFC is just one system! God's Program, you see, simulates the process of humans inventing a far more powerful formal system, one that does decide BB(1000). And if that sounds silly ... well, unlike a program to solve the halting problem, I know of no argument whatsoever to rule it out! 21. BT_Uytya Says: Comment #21 July 8th, 2024 at 6:30 pm I feel like this is very similar to the common misconception that 0.999... != 1. You see, 0.999... is merely "asymptotically tends to" 1, but never actually reaches it. Here we have another instance of confusion between a specific single object (a real number written as 0.999..., whatever element of R it could be equal to) and an infinite collection (a sequence of 0, 9/10, 99/100, ...). Arguably, it's the construction of real numbers is weird and non-intuitive here, but even a most exotic calculus variant would say that the difference between 0.999... and 1 is infinitisimal, not that a specific number "approaches" something else. 22. Scott Says: Comment #22 July 8th, 2024 at 6:36 pm BT_Uytya #21: Interesting! I hadn't made that connection. 23. Travis Allison Says: Comment #23 July 8th, 2024 at 7:28 pm I was always so confused by this issue. What finally clicked for me was imagining a long line of Turing Machines ordered alphanumerically and by length, stretching off to infinity. The question whether there exists a TM that computes BB(6) means, "Is there, in that long line of TMs, some TM that prints the number BB(6)?" Right now, we don't know which TM does this (and maybe we will never know), but that TM exists, because for any number there is a TM that prints that number, and BB(6) is a number. Due to the recent discovery, we do know which particular TM computes BB(5). Notice that the TM that computes BB(5) existed before we knew which particular one did the job. Also notice that the particular TM that we know for certain computes BB(5) doesn't compute BB(6) (they are different numbers). Finally, there isn't any *single* TM in that long line of TMs which, for every number you write on its tape as input, will output the Busy Beaver number for that number you wrote on the tape as input. It is because of that latter fact that we say Busy Beaver function is not computable. 24. S Says: Comment #24 July 8th, 2024 at 7:42 pm IMO, the confusion is linguistic. The problem here is that: * "computable" is a technical term, with a specific meaning that applies to functions / infinite sequences, * "computable" is also an English word, meaning something like "can be computed". I imagine it takes a level of "mathematical maturity" to know which words have precise meanings that must be looked up and one cannot try to infer their meaning from everyday contexts -- especially words like "regular", "normal", etc. Many of us have even read (or written) proofs with terms locally made up on the spot, like "Let us call n 'good' if it satisfies the following property", where it was never intended that such an n is indeed "good" in any everyday sense. But those who read "computable" as an English word (even if they know at some level that it has a technical meaning, the everyday meaning may still intrude upon their mind) will find it reasonable to ask questions like "Is BB(6) computable?" because they're still thinking of something like "Is it possible to compute BB(6)?", which is a reasonable question to ask. (A bunch of people were able to write some programs and compute BB(5) = 47176870; is it possible that no program will establish the value of BB(6)? Not programs of the "print k" type, because those were not the programs that "computed" BB(5), in their view, i.e. gave us knowledge about its value -- here once again using "computed" in an everyday sense that excludes "print k" programs as "computation".) 25. Udi Says: Comment #25 July 8th, 2024 at 7:47 pm What if god's existence depends on the day of the week? We could defined f(n) to be zero or one for different values of n between 1 and 7 representing the days of the weeks. If I understand correctly, f(n) is still computable since it is just one of 2^7 possible functions. Next, if god's existence depends on the number of days since the world was created, n can be any natural number. Would it be valid to claim that f(n) is not computable? 26. Scott Says: Comment #26 July 8th, 2024 at 7:56 pm Udi #25: Yes, any Boolean function with finitely many inputs is computable. A function with infinitely many inputs might or might not be computable--it depends on the function! 27. Scott Says: Comment #27 July 8th, 2024 at 7:57 pm Travis Allison #23: YES!!!!! 28. Milk Enjoyer Says: Comment #28 July 8th, 2024 at 8:05 pm By the way, am I right in thinking that we CAN prove from ZFC that BB(n) has some value for all n, even though there are n for which BB(n)=x is not provable for any x? If so, does it even make sense to talk about "the value of BB(n)" in that case? Sorry for the philosophical distraction. 29. flergalwit Says: Comment #29 July 8th, 2024 at 8:44 pm S #24 yes in particular, with the informal "can be computed" notion I think some people have in mind the intuition that this entails being able to compute the answer to the problem _without already knowing the answer_. Hence excluding the trivial program that prints whatever the value happens to be, or anything obviously equivalent to that. On an intuitive level this makes sense - the computation is supposed to give us knowledge we didn't already have. Beforehand we don't know BB(5). After running the computation, we do. Unfortunately, it's difficult or impossible to make this intuition precise, which is (one reason) why the formal notion of computability is defined differently. I've seen people react similarly on hearing the fact that axioms do have proofs (in the system they define). In fact they have a trivial one-line proof. To some, this seems like cheating, because I think they have in mind the intuition that a proof should be a convincing demonstration to a (rational) skeptic, i.e. someone who wasn't already convinced of an axiom's truth. I think it's similar here - a program to compute BB(5) in this sense would necessarily have to be designable without already knowing anything about the value. Again, unfortunately it's probably impossible to make this precise. Another similar issue arises in formal security analysis, when quantifying the difficulty of breaking the collision resistance of a particular hash (with no key, or any kind of free parameter). As any collision can be hard coded into the attack algorithm, formally there is always an efficient collision finding algorithm (assuming a collision actually exists). See Rogaway's _Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys_ for interesting discussion. 30. Scott Says: Comment #30 July 8th, 2024 at 9:00 pm Ching-Tsun Chou #8: Well, what do you say about the common practice of dropping in a specific hash function (say, SHA-256, which plainly has collisions when the input size is greater than 256 bits) when, properly speaking, a collision-resistant hash is needed? Would you consider this to be an instance of "this constant misapplication of concepts that were designed for infinite sequences and functions, to individual integers and open problems"? Of course in practical cryptography you're constantly making those sorts of tradeoffs. It's fine as long as you understand what you're doing--the relationships but also the differences between asymptotic and finite-n security statements--which understanding is therefore a large part of cryptographers' job. 31. Scott Says: Comment #31 July 8th, 2024 at 9:04 pm Milk Enjoyer #28: Yes, ZFC and even PA will prove that BB is a total function and that it's well-defined. 32. Avocado Says: Comment #32 July 8th, 2024 at 11:17 pm I feel like you claimed (in #92) that I made this Zombie misconception (in #90) when actually I was agreeing with you (from #56), although I did state this in the form of a question and could have been unclear. I said it because you made it sound like delineating math problems as interesting based on computability may not work because it's "a lot harder than you suggest to draw a clean line separating the mathematical questions we're allowed to ask from those we aren't. Like, are we allowed to define BB(6), but not BB(7)?" But BB(6) and BB(7) are computable (maybe computability isn't the right word, but we can compute them), so why wouldn't we be allowed to study them based on the concern of getting lost trying to handle uncomputable objects and manipulate them paradoxically (like Banach-Tarski)? I don't dislike computability, Godel, Turing, or proofs that certain problems are indeed uncomputable. I love it. I don't think we're worrying ENOUGH about those. It doesn't make sense to me to worry about making set theory work for uncountable sets, because they are uncomputable. I don't think it makes sense getting lost in a world of massive paradoxes with transfinite sets when we have nothing to show for it. I also think my view is consistent with (and follows directly from) the Church-Turing thesis. However, I am left feeling troubled about the possibility of trying to find the value of BB(745) with more powerful axioms. How would we even start? I think the axioms should be about tersely capturing the formal manipulation of a Turing machine with a finite transition state memory and a (countably) infinite tape to write on. I think, like Putnam, these axioms should be empirical. I don't like the idea of using a very obscure axiomatic system to try and prove BB(745) or any other BB(n). And I don't see how Con(ZF), etc. could provide any valuable reductions with first-order logic to prove something about these machines. 33. BTernaryTau Says: Comment #33 July 8th, 2024 at 11:25 pm Scott #20: Could you accomplish this by adding an axiom that asserts a value for BB(1000)? If so, how difficult would it be to find a value that doesn't lead to a contradiction? 34. Gabriel Says: Comment #34 July 8th, 2024 at 11:26 pm A similar issue, perhaps, is that in a first-order logic, the notion of "equivalent formulas" loses its expected meaning for closed formulas (i.e. with no free variables). Any two true closed formulas are equivalent, and any two false closed formulas are equivalent. For example, Fermat's last theorem is equivalent to the four-color theorem. (A more conventional example of equivalence would be to say, for example, that over the natural numbers, the formulas "exists x x+y=z" and "not exists x y=z+x+1" are equivalent, since they are two different ways of saying "y <= z".) 35. BTernaryTau Says: Comment #35 July 8th, 2024 at 11:30 pm "Let f:{0,1}*-{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? (Hint: The answer does not depend on your religious beliefs.)" I'm not sure this is true. If someone had a religious belief that God both exists and doesn't exist, or that God neither exists nor doesn't exist, then they could say that they believe f is ill-defined and thus cannot be a computable function. 36. Danylo Yakymenko Says: Comment #36 July 9th, 2024 at 12:23 am I saw this misconception many times too, on various places such as stackexchange, hacker news, etc. I think the essence of the falty logic is the following. "If BB (n) is a definite number that can be found for every n, then BB should be computable. Thus we can't find BB(n) for some n". What uninvolved people don't realize is that there is no absolute truth after Godel anymore. We can only work in theories which have limited power, there is no all-powerful God's theory to rule them all (available to us). Finding a concrete value of BB(n) depends on a theory we choose. To explain this seemingly paradoxical state of affairs I like an analogy with compression. A formal theory is like a compression of a part of mathematical knowledge. It turns out that we can't compress all the knowledge into a finite form, which every formal theory has. 37. Simon Tatham Says: Comment #37 July 9th, 2024 at 12:42 am To slightly shorten a thing Gil Kalai said in #4: since checking a proof of a statement S is in P, finding a proof of S is in NP (provided, unrealistically, that we know some upper bound on its length). So it's easy to see why someone might imagine that a proof of P[?]NP platonically exists, but that there might be a "solving a big instance of an NP-hard problem" practical issue with any human finding it. But far weirder is if they think the *opposite* might happen: that on the one hand P=NP, but on the other hand a "solving a big instance of an NP-hard problem" style of difficulty faces anyone trying to prove it. That way round, the problem resembles the joke proof of Fermat's last theorem in one of the silly dialogues in "Godel, Escher, Bach", in which one of the characters wrote down a Diophantine equation describing the Godel number of a proof of FLT, simplified it vigorously, and was startled to find it came out to be the Fermat equation itself, an+bn=cn. So then they knew they had only to find a counterexample, and they'd have the proof! But then, perhaps the apparent paradox is resolved by viewing it as a mere bootstrapping issue. *Until* we know the description of the magic Turing machine that solves NP-complete problems in polynomial time, we can't use it to find itself. ("He did this, and was rather startled to discover that he had managed to create the long-sought-after golden Infinite Improbability generator out of thin air.") 38. Simon Tatham Says: Comment #38 July 9th, 2024 at 12:54 am On the pedagogical issue: I must admit that I rather sympathise with the confused students. If you exhibit an infinite sequence of trivial computer programs each printing out an integer - or just two, printing TRUE and FALSE - and say "Of course the answer to one-off question Q is computable, because *one* of those programs computes it, but I'm totally unable to give you any help figuring out which", I find it easy to see the point of view from which the computability of the answer is a mere technicality. Surely the *important* point is not "one of these programs works", but the fact that we don't know which one! Certainly that would seem like the important point to the person currently holding your Zombie Misconception. I think the interesting part is not to explain to the student *that* there's a subtle distinction here, but to explain *why* the "technically yes this is computable" side of the distinction should win, and why it's not much more natural to consider "no we can't find this out" to be by far the more important aspect. Otherwise you run into one of the biggest pedagogical problems of all: the student won't bother taking in your explanation because they're convinced the thing you're explaining is just not very important. 39. FeepingCreature Says: Comment #39 July 9th, 2024 at 2:13 am Isn't the God thing highly misleading? The function is defined as: - f = 1 if God exists - f = 0 if God does not exist. But this is just to say that the function is undefined! Thus, intuitively, the reader completes it to: - f = 1 if God exists else 0. And now this may or may not be computable, depending in good part on definitions. The point is, you can say it's a constant function, but it's only a constant function cause you've hidden 99% of the actual function in the statement of the problem. In other words, the problem starts with, implicitly, "Say you had already computed whether God existed." That rather answers the question right there, doesn't it? And if it was impossible to do that, then you would be faced with a function that - has one possible value, sure, but the *name* of the function resolves to two possible *functions*, and that assignment was uncomputable. Sorry, but this just sounds like a rhetorical gotcha. 40. asdf Says: Comment #40 July 9th, 2024 at 2:34 am The zombie there prefers intuitionistic over classical logic, so any particular number n can only be treated as equal to BB(6) if it is accompanied by a proof that it is equal to BB(6). The term "uncomputable" is still misused, but maybe only slightly. If there is no pair (n, proof(N=BB(6))) where the proof is in your favorite axiom system, N is "uncomputable" in that misuse. So is there such a thing as a truly uncomputable N? Maybe not in Peano arithmetic, but PA asserts or proves the existence of integers 0, 1, 2... by iterating a successor function. It also contains "forall" axioms that quantity over all the integers, including integers whose existence has not been proved! It uses those axioms to prove the existence of yet more integers. That is called an impredicative theory. It's ok to reject that approach and still get a reasonable fragment of PA. There is a book about that called "Predicative Arithmetic" by Ed Nelson (RIP). But, if you do that, I'm pretty sure that the BB function is no longer total, and maybe BB(6) doesn't exist (or anyway, is not finite). Even the exponential function in this system is not total. Nelson talks about this some here: https://web.math.princeton.edu /~nelson/papers/e.pdf Some other related stuff of his is here: https:// web.math.princeton.edu/~nelson/papers.html Finally a joke by Shachaf Ben-Kiki on #haskell some years back: "In ultrafinitism, Peano arithmetic goes from 1 to 88" 41. John Baez Says: Comment #41 July 9th, 2024 at 2:57 am Is there only one zombie misconception in theoretical computer science? Physics is littered with them, from "a ball swung around on a string shoots straight out if you cut the string" to "nothing ever really falls into a black hole, because it takes forever". That's why we created the Physics FAQ. I think these misconceptions are like the fossil record of the growth of physics over the ages -- and since "ontogeny recapitulates phylogeny", each student should work through them all, to transform their naive intuition into the trained intuition of an expert. So I imagine there should also be plenty of misconceptions in theoretical computer science. Has someone listed them somewhere? 42. asdf Says: Comment #42 July 9th, 2024 at 3:21 am Ok, found old page (domain now squatted) that I was thinking of: see question 6, equivalent to your question about 3 and 5 and the existence of God, and a bunch of astute people (at the bottom of the page) giving different answers to it and the other questions: https://web.archive.org/web/20110726182755/https:// www.intuitionism.org/ Clicking the respondents' names gives more detailed answers. In the table, + is "yes", - is "no", and # is "question is meaningless, answer is messy, etc." 43. Seth Schoen Says: Comment #43 July 9th, 2024 at 3:32 am Scott #31: I guess the proofs are nonconstructive and you do need to invoke excluded middle for that, though? Otherwise you can't even prove that all Turing machines either halt or don't halt. (I guess you can never exhibit a specific noncomputable total function in constructive logic, although you can still reason about the behavior of such functions.) 44. Edan Maor Says: Comment #44 July 9th, 2024 at 3:36 am > While they're closely related, only Godel lets you talk about individual statements rather than infinite families of statements, and only Turing-computability is absolute, rather than relative to a system of axioms.) This question might not make much sense, but - do you consider Turing-Computability to be "absolute" only insofar as the Church-Turing thesis is true? I'm not actually sure what you mean by absolute, actually. And I'm not sure how Turing Machines are formalized in terms of specific axiom systems; are you saying that in whatever way they are formalized, they are "equally powerful" in terms of what functions they can compute? -- In any case, I tend to think that the issue with these zombie questions is people just fundamentally misunderstanding the actual meaning of the words used here (as S #24 also suggested). It's like people learning probability/statistics, and talking about Random Variables in a kind of handwavy way, without understanding the underlying mathematical concepts; since an RV is a function, it's not like they don't understand the concept itself, they're just not mapping the abstract concept of a "Random thing" used in everyday language to a specific mathematical object. I think this describes a decent amount, maybe even 90+% of people who even know what a Random Variable is. (I should know - I was in this camp before more seriously studying probability!) 45. Martin Says: Comment #45 July 9th, 2024 at 4:31 am The number of times people bring up uncomputable integers is equal to the amount of people who think they appear smarter for bringing them up. Interestingly, this article also seems match in the spirit of that. And so does this comment. 46. Scott Says: Comment #46 July 9th, 2024 at 6:24 am Avocado #32: There are a lot of big issues that you've mashed together into guacamole, as it were. Step 1 is to clearly separate the concepts of "uncountable" and "uncomputable." When we talk about computability, we're normally talking about subsets of the integers--sets that are all countable but that might or might not have a Turing machine that computes them. You have to do something nonstandard even to make it meaningful to ask whether an uncountable set is computable (how is the input provided? to what kind of machine?). On the broader question of the relevance of the transfinite to real life--well, I don't spend my own career on questions whose answers depend on CH or AC or the like! But the questions are so natural that someone would have asked them. They would have been dissatisfied as long as there were obtainable answers that weren't being obtained--even if those answers turned out to be "it depends on your axioms." And the clincher: if you banned me from talking about uncountable sets, in my day-to-day work and teaching in CS I'd have to invent a circumlocution for it, because the concept is that central. Regarding the determination of Busy Beaver numbers, I should be clear that I expect "merely practical" difficulties to kill us long before axiomatic ones do! But it's possible that, in principle, more BB values would become determinable "merely" by assuming large cardinal axioms and the like, rather than anything "nonstandard." 47. Scott Says: Comment #47 July 9th, 2024 at 7:26 am BTernaryTau #33: Could you accomplish this by adding an axiom that asserts a value for BB(1000)? If so, how difficult would it be to find a value that doesn't lead to a contradiction? The big problem with "adding an axiom that asserts the value" is, what if you're objectively wrong? That is, what if there's a different machine that halts after more steps than your machine? You'd need damn good confidence, even if short of proof, that every machine that runs for longer than your machine actually runs forever. In the case of BB(5), we'd known what ultimately turned out to be the correct machine since 1990-the one that halts in 47,176,870 steps. And there was a list of at most 43 candidate machines that might beat it, but none of them halted within a trillion steps--thereby proving that BB(5) was either 47,176,870 or more than a trillion. But until this year's achievement, I for one didn't have any great confidence that none of those machines halted, and certainly wouldn't have wanted to add an axiom saying so! And that's merely for BB(5), let alone BB(6), let alone BB(1000)... 48. Scott Says: Comment #48 July 9th, 2024 at 7:33 am BTernaryTau #35: I'm not sure this is true. If someone had a religious belief that God both exists and doesn't exist, or that God neither exists nor doesn't exist, then they could say that they believe f is ill-defined and thus cannot be a computable function. We might as well talk about the equivalent case of the number that's 3 if God exists or 5 if God doesn't exist. Would this person likewise say that that number isn't prime? I hope this makes clear that the dispute has nothing to do with computability (or primality, or theology): it's just about the person's rejection of basic rules of logic (in a technical sense, not necessarily a pejorative one). 49. Scott Says: Comment #49 July 9th, 2024 at 7:46 am Danylo Yakymenko #36: The first part of your comment is brilliant! Yes, absolutely, people imagine that if BB is uncomputable, then we must be able to point to a specific n such that BB(n) is uncomputable. They don't grok the intermediate case, that there's no general procedure that works for all n but also nothing to rule out an ad hoc solution for any particular n. On the other hand, I would not say that "there is no absolute truth after Godel anymore." And Godel himself, a arch-Platonist, certainly wouldn't have said that! There is an absolute truth about the values of BB function; it's just that any fixed formal system can tell us only a finite initial segment of that truth. 50. Nicolai Says: Comment #50 July 9th, 2024 at 7:52 am You could ask the P vs. NP question relative to an oracle. Given a description x of an oracle, x \in L if P!=NP given access to oracle x. Surely L isn't even in P, but it feels like it should be possible to show that it's NP-hard. Which is probably one of the less interesting and weaker properties of L, but still ... 51. Scott Says: Comment #51 July 9th, 2024 at 8:06 am Gary Drescher #14 and Simon Tatham #38: Yes, on reflection, maybe I should tell theoretical computer science beginners: "I am offering to place into your hands a weapon of almost unimaginable power. With this weapon, 'hard,' 'easy,' 'computable,' 'uncomputable' will be no longer vague descriptors but precise technical terms. Vast new realms of knowledge will open before your eyes. But you must learn to respect the weapon. You must use it only as it was meant to be used, and not otherwise. Above all, you must remember that we speak only about the existence or nonexistence of particular kinds of finite algorithms for infinite sequences. The day you demand the weapon tell you whether some specific bit of information is knowable or not is the day the weapon will fail you. I will now set some challenges to test your understanding of this..." 52. Scott Says: Comment #52 July 9th, 2024 at 8:13 am FeepingCreature #39: Nope, there's the Zombie Misconception again! The point you're still missing is that the computability of f is about the relationship between f's inputs and f's outputs--that's it. It has nothing to do with how hard it might be for us to find the program that maps the inputs to the outputs, which is also an important question but a completely different one. Once more, the view that f is uncomputable, is precisely equivalent to the view that the number that's 3 if God exists and 5 if God does not exist is not prime. 53. Scott Says: Comment #53 July 9th, 2024 at 8:19 am asdf #40 and Seth Schoen #43: To extend my analogy from comment # 50, intuitionistic logic, the rejection of the Law of the Excluded Middle, etc are dark weapons. I don't use them. If they should ever be used by anyone, they should be used by only experts who know exactly what they're doing and why. In the hands of anyone else, these weapons will produce no end of forehead-banging confusions. 54. Scott Says: Comment #54 July 9th, 2024 at 8:28 am John Baez #41: Oh, there are lots more zombie misconceptions in TCS! And I love your idea of collecting a list of them; maybe I'll try that in a future post. Just off the top of my head, for example, there's "but if time travel to the past is possible, then P=NP, regardless of what the math says!" I.e. conflating the mathematical question of whether P=NP, with the (equally profound) question of whether NP-complete problems are efficiently solvable by any physical means. Having said that, the misapplication of infinite or asymptotic concepts to individual instances is probably indeed the elementary TCS misconception that I most often encounter in the wild (at least, say, once per week), partially justifying the title "The Zombie Misconception." 55. Alex Shibakov Says: Comment #55 July 9th, 2024 at 8:45 am As you write in #47, the ZFC status of BB(1000) is tricky. For a given correct value x of BB(1000) there is no ZFC proof of correctness but for any wrong x there is a ZFC proof of that: if x is too small than a TM that runs longer that x steps is (the basis of) such a proof and if x is too large, simply run every machine in the pool to show none of them stop exactly after x steps. An even more intriguing and depressing thought is that ZFC itself is inconsistent but the proof of that is so unimaginably long that we will never be able to see it in full. It may even derive some of its expressive power from this inconsistency. So all we are doing is living in this `local bubble of consistency' without ever being able to perceive the full truth. This also means that if there is a theory that establishes a certain value for BB(1000) we will forever be ignorant if it and ZFC are equiconsistent. 56. Nick Drozd Says: Comment #56 July 9th, 2024 at 9:03 am Scott #52 Constructivists don't reject the Law of Excluded Middle. They just accept only those instances which have been proved. And constructive logic is not some niche specialty topic: it's the reality on the ground for anyone who uses theorem provers (Coq, Lean, etc). When it comes to actually using computers to compute stuff, it's clear that general LEM -- accepting every single instance as perfectly valid -- is wild and extravagant. Real-world provers will not prove BB to be total. Functions like that will be flagged as partial. The partial flag is contagious, so that any function that relies on a partial function is itself flagged as partial. So on the one hand there are constructivist extremists who would eliminate any talk of uncomputable functions as meaningless. Of course, that is throwing the baby out with the bathwater. There are lots of interesting things to be said about BB, BBB, etc, in spite of (and because of!) various difficulties. On the other hand there are classical extremists who think that it is just pointless nitpicking to bother with these distinctions, and it's too much work to sort out the details, and the whole endeavor only serves to shackle the power of true mathematical thinking. Far from throwing the baby out with the bathwater, classical extremists don't even recognize a difference between the two! Personally I am open to all sorts of reasoning about uncomputable and uncountable entities, provided that the proof / reasoning resources involved are made explicit and sharply delineated. 57. Dominik Lukes Says: Comment #57 July 9th, 2024 at 9:03 am I'd like to ponder a bit on your final question - "how to keep this zombie down?" I think this sort of misconception is the inevitable consequence of learning. We all need to go through these steps and have multiple such misconceptions corrected. But they are never corrected perfectly - which is why many persist in the published literature. But in some ways the internet popularization has made easier to engage in "drive-by" learning without the close-knit community to exercise corrective messaging on common misconceptions. All teachers get these 'naive' questions from students in private but because you engage in such public popularization you are bound to see more of them. I find your blog useful precisely because it also addresses misconceptions and gives me useful feedback on my own thinking - I usually get to ask silly questions in private and then read the answers when you address them here. Having reference posts like these is very useful because people who are having similar conversations can point others to them. I think this is about as good as it can ever get on this issue. But the bigger question is whether we can keep these misconceptions from multidisciplinary efforts where they can actually do more harm. I like Gelman's repeated points: thinking about this is hard, it's easy to make mistakes, getting and giving feedback on thinking is a part of the process. 58. Johnny D Says: Comment #58 July 9th, 2024 at 9:25 am The following has bothered me for 4 decades. Please help! Classifying closed manifolds of dimension 4 or greater is one of these problems that any finite formal system only gives a partial answer. Since string theory is in greater than 4 dimensions of space, isn't modeling reality with string theory as practical as modeling it with bb function? 59. Milan Says: Comment #59 July 9th, 2024 at 9:25 am Maybe the misconception is aggravated by our use of the English language in describing programs. Conditionals, assignments and quantifiers can all be used to describe source code in a specific programming language, the abstract workings of a program and a statement about programs. Take the problem from the beginning of the post: > Let f:{0,1}*-{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? (Hint: The answer does not depend on your religious beliefs.) If I forget for a moment that I already know what the sentence means, I could understand three or four different questions: 1) If God exists, I ask: "Is the constant 1 function computable?" If God does not exist, I ask instead: "Is the constant 0 function computable?" 2) If God exists, I define: "f is the constant 1 function." If God does not exist, I define instead: "f is the constant 0 function." And now, having defined a simple f without knowing what it is, I ask: "Is f computable?" 3a) I ask: "Is there a computer program which does the following: We give it all our philosophy and science books as input, and it determines whether God exists, outputting either 0 or 1. It must be correct at least mumble mumble epsilon mumble distribution over worlds mumble mumble." 3b) The same setup as 3a), but instead of being a passive consumer of information, the program instantiates an active agent in the world. The program does not need our input. Instead, it constructs telescopes and Von Neumann probes and goes searching for God. After some time, it will be certain of the answer. And then it will finally output a single 0 or a single 1, depending on the answer it found. Does such a program exist? The cases differ in how the conditional in the problem description is understood: In 1), the conditional of the problem description is turned into a disjunction of propositions about programs. In 2), the conditional is used to change which definition we bind to a function, but not inside of the function. In 3a) and 3b), the conditional is used inside of the function/ program that we seek. For 3a), the notion of computability could apply, if we imagine measuring the performance in different universes. I would not describe 3b) as a problem about computability in the normal sense. A careful reading of the problem should evoke 2). I think 1) and 2) are equivalent and that 1) is even clearer. But when I first learned math, upon hearing the problem, all the different cases would have formed a big tangle in my mind. I blame the language at least a little bit. Explicitly listing these cases and sternly pointing to 2) may be good pedagogy. 60. Scott Says: Comment #60 July 9th, 2024 at 10:01 am Nick Drozd #56: Here's a better way of putting my point. Constructive logic, and anything less than total acceptance of LEM, are best thought of as technical tools for people doing formal verification. I'll take your word that they're great for that! The way to get endless nonsense is to inflate them into metaphysical claims about how to reason about what's objectively true in the world. In the real world, if you should do X if God exists, and you should also do X if God doesn't exist, then you should do X, end of story. Likewise, if someone proves that Riemann Hypothesis follows from P=NP and also from P[?]NP, they've proved the Riemann Hypothesis. By analogy, there's a whole class of howlers in the foundations of quantum mechanics that comes from taking approximation methods that are occasionally useful in dealing with the Schrodinger equation in practice (eg the nonlinear Gross-Pitaevski equation, hidden-variable models based on fluid mechanics), and inflating them into metaphysical claims about what's actually true about the world. 61. Peter Donis Says: Comment #61 July 9th, 2024 at 10:14 am @Scott #52: "It has nothing to do with how hard it might be for us to find the program that maps the inputs to the outputs, which is also an important question but a completely different one." But you're still assuming that there *is* such a program, correct? In other words, you're assuming that there is *some* program that *computes* whether or not God exists, so that the overall function knows what to output. Which, when made explicit, does not seem like an assumption that you can just help yourself to. Or are you instead assuming that the function can make use of an Oracle that just *tells* it whether or not God exists? 62. Scott Says: Comment #62 July 9th, 2024 at 10:20 am Peter Donis #61: In other words, you're assuming that there is *some* program that *computes* whether or not God exists. Which, when made explicit, does not seem like an assumption that you can just help yourself to. Or are you instead assuming that the function can make use of an Oracle that just *tells* it whether or not God exists? No. Neither. You're still in the grip of the Misconception. I'm "assuming" that there's a program that always outputs 1, and another program that always outputs 0. And if you like, I'm "assuming" the Law of the Excluded Middle, which implies that f is computed by one of those programs (for purposes of the question, it doesn't matter which). That's all. The existence nor nonexistence of a program to decide God's existence (whatever we mean by that) never enters into it--that's just a totally different question from the one that was asked. 63. Peter Donis Says: Comment #63 July 9th, 2024 at 10:32 am Re my #61: after reading Milan #59, I see the point, but I think the question as it's phrased is more a test of reading comprehension than math misconceptions. If we define f0 as the constant function that takes no input and outputs 0, and f1 as the constant function that takes no inputs and outputs 1, then the question can be rephrased as: "The label f refers to f1 if God exists and f0 if God does not exist. Does the label f refer to a computable function?" Put this way, the answer is obviously yes (at least as long as we accept the Law of the Excluded Middle for this case, as you say in #60). However, the way the original question is phrased invites the reader to imagine a third function fG, which is defined as: "Compute whether or not God exists. If God exists, output the result of f1, otherwise output the result of f0." *This* function is *not* computable unless whether or not God exists is computable. 64. Scott Says: Comment #64 July 9th, 2024 at 10:47 am Peter Donis #63: I mean, yes, reading comprehension is a big part of math (and any other technical field, along with most nontechnical fields)! And it's totally fair game to say: if a problem "invites" you to give a wrong answer based on an irrelevant consideration that the problem never mentioned, then that's a wonderful opportunity to hone your intuitions so you become less likely to do that (hence why Sipser gave this as homework). 65. Jim Hefferon Says: Comment #65 July 9th, 2024 at 10:47 am Thanks for a most enjoyable blog. To follow up on Simon Tatham and John Baez: when students repeatedly get something like this wrong, and I see it also in my students, then folks who teach (and write texts) should look into adjusting how they present the topic. For instance, it might make sense in Sipser's text to move this from an exercise to being directly addressed in class (assuming that he sees it among his audience). It also makes sense for these folks to see if they can understand why students are making this mistake, such as by asking them (the StackExchange group is another good resource). For instance, are students forming a wrong mental model, or confused about fine point in the definition? There is a lot of work to be done here that could help make things better. 66. Jay L Gischer Says: Comment #66 July 9th, 2024 at 10:49 am I love Sipser's question. I wish I could have used it when I was teaching. I think the issue stems from "functions as first-class objects". This comes up in programming languages too. Maybe in other branches. This was a definite leap I had to take. 67. Scott Says: Comment #67 July 9th, 2024 at 10:51 am On reflection, maybe it would help some people to consider a function f that encodes the halting problem if God exists, or the solvability problem for Diophantine equations if God doesn't exist. Is this f computable? The answer is no, it isn't, but the reason why not has nothing to do with God; it's simply that the halting problem and Diophantine equations are both uncomputable. 68. Scott Says: Comment #68 July 9th, 2024 at 10:55 am Jim Hefferon #65: I actually think this could work great as homework. If students are confused, let them sit and discuss it among themselves until enlightenment dawns. 69. Peter Donis Says: Comment #69 July 9th, 2024 at 11:00 am @Scott #64: "it's totally fair game to say: if a problem "invites" you to give a wrong answer based on an irrelevant consideration that the problem never mentioned, then that's a wonderful opportunity to hone your intuitions so you become less likely to do that" Oh, definitely. I'm not saying the question isn't a good opportunity for learning. I'm just saying that, before you conclude from someone's answer that they have a misconception about computability, you should first make sure they don't just have a simpler misconception about which question you actually asked. I am an example of the latter. 70. Ashley Says: Comment #70 July 9th, 2024 at 11:09 am Hi Scott, Maybe, after you have linked them to this blog post, you could also point them to the following for a more general solution- https://x.com/wtgowers/status/1715037875786457420 71. Danylo Yakymenko Says: Comment #71 July 9th, 2024 at 11:20 am Scott #49 Agree, it seems the consensus is that an absolute mathematical truth exists, however, there is no way to verify all of it by a finitely described method. On the other hand, we have a way to extend any such finite method to verify a strictly larger portion of the truth. I still can't wrap my head around it. Although, today I'm less worried about it since QM scrambles the notion of the truth even more severely 72. fred Says: Comment #72 July 9th, 2024 at 11:31 am I think there might be a difficulty with computability because it isn't anchored in reality since any Turing machine has a finite number of states but it has an infinite memory/tape, but then BB (n) refers to n-state Turing machines, and when n is potentially an infinite sequence, then the state (program) of the Turing machine is itself unbounded. At that point data memory and program memory are the same and potentially unbounded (it also comes up when considering that a Turing machine can simulate Turing machines with bigger states thanks to its infinite tape). And then we ask whether an infinite program (takes infinite memory to store it) counts as a computable realization? That's like when we say BB(5) is computable because the program itself just needs to output BB(5). And then BB(n) with n < 100 is computable too because the program can just be a lookup table with 100 entries. But when we say a program for BB(n) for all n, then the lookup table would be infinite, making the program infinite. And in that case we'd say it's no longer computable? 73. Matthew House Says: Comment #73 July 9th, 2024 at 11:36 am Perhaps one objection against "\(\operatorname{BB}(n)\) is a well-defined function which always results in a natural number" arises not from a rejection of LEM, but from a rejection of the standard model of the natural numbers, relative to which we can say "for all natural numbers \(n\), \(P(n)\) holds". If such a \ (\Pi_1\) sentence has no truth value, then we can't even apply LEM to it in the first place. \(\operatorname{BB}(n)\) is a victim of this, since to define its value, we need the notion of "a TM running forever and never halting". After all, the standard model is a very slippery thing. We can intuitively guess that induction continues to work forever, and thus derive \(\operatorname{PA}\). But then this induction schema isn't sufficient for showing \(\operatorname{Con}(\operatorname {PA})\), so we formalize some of our second-order intuitions, and derive \(\operatorname{ZF}\). But then this isn't sufficient for showing \(\operatorname{Con}(\operatorname{ZF})\), so we add large cardinal axioms, and so on. There's no way to justify any of these axioms except with more axioms in this (transfinite) upwards regression; we clearly can't choose the additional axioms at random, lest our theory fail to match the standard model, and start making claims about non-standard numbers. And so it would seem that any statement asserting a property of every natural number cannot be treated as absolutely definitive, nor, by extension, any claim about the value of \(\operatorname{BB}(n)\). A retreat to empiricism ("LEM should dictate our actions relative to real-world propositions") doesn't really seem to help with this issue. There's no empirical test for \(\operatorname{Con}(\ operatorname{ZF}+\text{sufficiently powerful axioms})\) that would conceivably have a chance of finding a discrepancy, if one exists. So to escape from this tyranny of the incompleteness theorem, one might be tempted to say, "There is no standard model of the natural numbers, or at least none that is useful: thus we should only consider statements as having truth values relative to particular (computable) axiom systems." And under such a viewpoint, \(\operatorname{BB}(n)\) would indeed become undefined for sufficiently large \(n\). 74. Nick Drozd Says: Comment #74 July 9th, 2024 at 11:41 am Scott #60 Arthur C. Clarke once said: either we humans are alone in the universe, or we are not, and both possibilities are terrifying. This is a profound thought, and I accept it as true. And yet I am not terrified. Why not? Well, what exactly is it that I should be terrified of? Until I know that for sure, terror makes no sense, even if it is ultimately inevitable one way or another. Now say it is proved that P=NP -> RH and P!=NP -> RH. From a constructivist point of view, this is certainly not nothing. For one thing, it means that any search for RH counterexamples can be called off, since no counterexamples exist. And yet, the proof is still kinda crummy. It's really two proofs, one of which of is good and one of which is nonsense, and there's no indication which is which. A constructive proof would be much better. It would give a clearer picture of the mathematical universe. It would be more useful for calculations. It would even be morally better -- a truly non-constructive proof has a certain chickenshit quality to it. Again, a non-constructive proof is certainly better than no proof at all, it's just not as good as a constructive proof. And I don't see any reason to efface the distinction. By the way, for the various prize problems in math, are there published guidelines for proof standards? Are there different prize committees with different policies? 75. fred Says: Comment #75 July 9th, 2024 at 11:44 am Maybe this is a dumb objection, but either "God exists" or "God does not exist" could be ill-defined. Like the function f that outputs 0 if the sentence "this is a lie" is true and outputs 1 if the sentence "this is a lie" is false (self-reference creating an oscillating state). Or the function f that outputs 0 if "yellow is smaller than blue" and outputs 1 if "yellow is not smaller than blue" (comparison of incompatible categories). 76. Scott Says: Comment #76 July 9th, 2024 at 11:50 am fred #72: Don't make this more complicated than it is! An integer function is computable if there's a Turing machine that computes it on all inputs. Otherwise, it's uncomputable. So for example, f(n)=n^2 is computable, but BB(n) is uncomputable (because it would let us solve the halting problem). 77. Christopher Says: Comment #77 July 9th, 2024 at 11:53 am Okay, here's my take on informally what "x is computable" means, where x is an expression instead of just a numeral. When I say "x is computable", it means that I know of a specific algorithm that outputs x. If I say "x is uncomputable", it means that I don't know which specific algorithm outputs x. Under this definition "BB(6) is uncomputable" is technically true, but that can change in the future. In particular, this terminology can only be used casually since "knowledge" is vague and changeable. Open problems are also generally "uncomputable" in this sense (I don't know any open problems where we know which algorithm decides it). Finally (and this is quite weird), in constructive mathematics we can ask "is there a 6th busy beaver number", and we can not immediately say "yes, there is"! Assuming that the proof for BB (5) is constructive, than that establishes that "is there a 5th busy beaver" can be answered with "yes", even to a constructivist. This is similar to but not the same as the formalist position. In particular, a platonic constructivist would say that "is there a 6th busy beaver number" has an objective "platonically real" truth value independent of any particular foundation, but that they do not know it yet (just like a platonic set theorist says the continuum hypothesis has a definite truth value despite it being independent of ZFC). 78. Scott Says: Comment #78 July 9th, 2024 at 12:00 pm Christopher #77: Not what any of those terms mean in any language that I speak. (And you probably know that, but I thought I should warn others!) 79. Pierpaolo Frasa Says: Comment #79 July 9th, 2024 at 12:09 pm Only half-jokingly: Maybe the function that takes as an input a complete description of the universe and returns true iff there exists a God in that universe is not computable. Of course, it's practically utterly meaningless to talk about such a "function" (even leaving aside philosophical questions such as whether the universe is even finitely describable at all), but maybe this version gets at the heart of what the "God is uncomputable" people would like to express? I think in a way this ties in with the point made in #13 - we care about theoretical noncomputability because it's a hint that you (usually) can't "cheat" on particular instances either. So if this mystical cross-universe function was uncomputable, it would provide a hint as to why nobody has answered the question in our world yet. (Of course, there's also the possibility that the existence of God is completely independent of the entire physical universe, and in that sense, the function wouldn't even be well defined... which might be my preferred answer) 80. fred Says: Comment #80 July 9th, 2024 at 12:13 pm Scott #76 Ok, so I guess BB(n) and Chaitin's Constant are somewhat equivalent (i.e. as hard to compute for a given N)? https://en.wikipedia.org/wiki/Chaitin%27s_constant 81. Scott Says: Comment #81 July 9th, 2024 at 12:14 pm Matthew House #73: Ah! Now we're dealing with a different misconception, one that I'd give the honor of calling the Zombie Misconception of Metamathematics. Talking about "standard models" versus "nonstandard models" of the natural numbers presupposes that we're talking about first-order axioms and models of those axioms. But in that case I'm already off the train! See, I knew what a natural number was long before I knew what a first-order axiom was. And--here's the crucial part--if I didn't already know what natural numbers were, then I couldn't have understood axiomatic theories either, since the latter presuppose computation and arithmetic. In other words, I claim that the entire way of talking about this where we need axioms to "undergird our confidence in arithmetic" is bass-ackwards. Notably, set theory is fundamentally different. There, we really do conjure entities into existence that we have no way of talking about other than via our axiomatic theories. And if two such theories disagree about the properties of those entities, maybe not even God could resolve the disagreement. Maybe there's no truth of the matter at all. But arithmetic and finite computation are special, because they're the ground of everything else in math. I don't need an axiomatic theory to tell me that 2+2=4 or that the BB function is well-defined (even though PA and ZF do tell me). And if an axiomatic theory said that 2+2=5 or that BB was not well-defined, then so much the worse for the theory. 82. Scott Says: Comment #82 July 9th, 2024 at 12:20 pm Nick Drozd #74: - You're very welcome to say that a constructive proof is better. You're not welcome to say that a nonconstructive proof is not a proof. - If you agree with Arthur C. Clarke, then I'd say you should be terrified and that's all there is to it! - For the Clay problems, they convene a jury to start reviewing a claimed solution two years after it's published in a journal. They don't specify the standards beyond that iirc. 83. Christopher Says: Comment #83 July 9th, 2024 at 12:45 pm Technical point RE: "Now say it is proved that P=NP -> RH and P!=NP -> RH. From a constructivist point of view, this is certainly not nothing. For one thing, it means that any search for RH counterexamples can be called off, since no counterexamples exist. And yet, the proof is still kinda crummy. It's really two proofs, one of which of is good and one of which is nonsense, and there's no indication which is which. A constructive proof would be much better. It would give a clearer picture of the mathematical universe. It would be more useful for calculations. It would even be morally better -- a truly non-constructive proof has a certain chickenshit quality to it." We have already proven that if there is a classical proof of the Riemann hypothesis, there is also a constructive one (and I believe we have efficient algorithms to convert the classical ones directly into constructive ones). I think this is the case for all of the millennium prize problems, but I'm not sure. 84. Pierre B. Says: Comment #84 July 9th, 2024 at 12:53 pm There is a speculation that Goldbach conjecture might be expressible with BB(6). Given that this conjecture might not be provable, then BB(6) might be unknowable, so uncomputable. Even without that, there is a contracdiction in your post since you claim BB(745) can implement an unprovable statement, thus uncomputable, and yet you claim individual BB numbers are always computable. 85. Matthew House Says: Comment #85 July 9th, 2024 at 12:57 pm Scott #79: Of course I have a good intuitive idea of the natural numbers, and so do you. But I don't think that this idea is inherently sufficient to make all claims of the natural numbers that BB(n) wants to make. When we make metamathematical claims about models and axioms, we're usually working in a fairly weak metatheory. We only need very basic forms of induction to make sense of completeness, consistency, etc. None of these forms should be objectionable, except to strict finitists. But when we make claims about BB(n), we find that what we were acceptably doing is no longer sufficient at some point. We find that some machines don't appear to halt no matter how long we look at them, but no amount of simple induction helps us extend this to all integers! So we upgrade our notion of induction to a stronger form which does prove these machines non-halting, even if this stronger induction is slightly less immediately acceptable. But this is eventually insufficient again, so we upgrade our notion of induction again, and so on. Yet we can't keep upgrading our notion of induction forever: at some point we'll accidentally add something that is inconsistent, or that asserts the existence of numbers that can't truly be found anywhere. So BB(n) seems to shake one's confidence in how well-understood the natural numbers really are: no simple inductive understanding can capture all the properties we want to talk about, nor can any process contradict an incorrect understanding within a reasonable time! In other words, I'd draw a distinction between "the natural numbers under the forms of induction sufficient for talking about metamathematics", which are intuitive, well-behaved, and quite necessary for grounding everything, vs. "the general set of natural numbers that second-order theories operate on, where every possible statement about all natural numbers has a truth value". > I don't need an axiomatic theory to tell me that 2+2=4 or that the BB function is well-defined (even though PA and ZF *do* tell me). First off, I'd say 2+2=4 is quite different in form than statements about BB(n), in that the former has no quantifiers at all, and only needs to talk about a few numbers. Second off, I don't think it really helps us here if PA or ZF can say something to the extent that "the BB function is well-defined", if they can't connect it back to the first order. Here, our standard-model objector would say that such a theorem is provable in PA or ZF using LEM, but not necessarily meaningful as far as reality goes. After all, just because PA + !Con(PA) says that "the witness to !Con(PA) exists" doesn't mean that we should listen to it! And I don't see any a priori way to distinguish between the trustworthiness of ZF and of PA + !Con (PA), except via obviousness. But obviousness can't last forever. 86. Christopher Says: Comment #86 July 9th, 2024 at 1:03 pm Scott #88 > See, I knew what a natural number was long before I knew what a first-order axiom was. And--here's the crucial part--if I didn't already know what natural numbers were, then I couldn't have understood axiomatic theories either, since the latter presuppose computation and arithmetic. I think there is quite a bit of merit to the idea that arithmetic being not apriori. Reason: it's clear that the laws of physics "still work" in nonstandard models, and thus our entire universe could be in one. For example, perhaps there is an alternate universe whose laws of physics are run in a nonstandard model M of arithmetic, and Scott's blog regularly gets a nonstandard number of comments. Would the Scott in that universe be able to tell he is M instead of in the standard model? The first place this would be noticeable is in the meta-mathematical of our axiomatic systems as it turns out. For example, maybe in M the statement "PA is inconsistent" holds. In this case, M Scott could write down a proof of 0=1 starting from the PA axioms, and none of the other M mathematicians could find the error. This could be the case even if M itself is a model of Peano Arithmetic ("Peano Arithmetic+'Peano Arithmetic is inconsistent'" is consistent). So, how do you know that you're standard model Scott and not M Scott? 87. Jair Says: Comment #87 July 9th, 2024 at 1:03 pm I love the exercise, but I feel it's leading to a bit of confusion due to lack of well-definedness of God, which is just a distraction from the basic math issue. I mean, can you formally prove the theorem that "if f is the constant 1 function if God exists, or the constant 0 function if God does not exist, then f is computable"? No, because defining f requires also defining the existence of God. Maybe you could use something like the Continuum Hypothesis in place of the existence of God. Then the same point stands, but this is now a theorem that could be formulated and proven in, say, Lean. 88. Peter Donis Says: Comment #88 July 9th, 2024 at 1:16 pm @fred #75: "either "God exists" or "God does not exist" could be ill-defined." In the terminology of my post #63, this would be a problem in deciding which function, f0 or f1, the label f would refer to. But it would still be irrelevant to the question of whether the function the label f refers to is computable, since that function still is going to end up being either f0 or f1, and both are computable. Your other functions f are analogous to the function fG in my post #63: they might not be computable, but they are not functions that the question is even asking about. The question is not talking about a *function* f that could call either f0 or f1 depending on something else. The question is talking about a *label* f that could refer to either f0 or f1, we just might not have any easy way of telling which. But both f0 and f1 are obviously computable, so which one ends up being the referent of the label f doesn't matter. There is no third function in the question whose computability is difficult to decide. 89. Scott Says: Comment #89 July 9th, 2024 at 1:18 pm Pierre B #84: there is a contracdiction in your post since you claim BB (745) can implement an unprovable statement, thus uncomputable, and yet you claim individual BB numbers are always computable. With some of these comments I feel like I'm marking problem sets with a red pen! "Unprovable, thus uncomputable" is where you go off the rails here. Those two adjectives aren't even meant for the same type of thing. 90. Scott Says: Comment #90 July 9th, 2024 at 1:24 pm Matthew House #85: To get that BB is well-defined, I need the following. - A given Turing machine either halts or doesn't halt on a blank input. - If it halts, it does so in some positive integer number of steps. - A finite set of integers has a maximum. Which of those statements do you dispute? Note that I didn't need to say anything about PA or ZF or models or induction schema or anything like that. 91. fred Says: Comment #91 July 9th, 2024 at 1:25 pm While BB(N) is pretty cool, there's also interesting hard questions to answer about stuff that's computable. E.g. there are 1,208,925,819,614,629,174,706,176 problem instances for 3-SAT with just N=5 variables, it'd be interesting to know what proportion of these admit a solution. Does anyone know if this can be answered without actually solving all the instances? (I guess one could pick instances randomly and build a running distribution of the ones with zero solution, one solution, two solutions, etc). 92. Scott Says: Comment #92 July 9th, 2024 at 1:32 pm Christopher #86: What would it even mean to "live in a nonstandard model"? If you want me to accept that as meaningful, you'll need describe for me some hypothetical experiment that would bear on the question. Right now it seems to me like a pure confusion of levels--like saying that we "live in Arabic numerals" or "live in ASCII." It's confusing the actual number systems that we use (or plausibly could use) in physics, with certain artifacts of the first-order theories that we sometimes use to encode our reasoning about those number systems. 93. fred Says: Comment #93 July 9th, 2024 at 1:37 pm Scott #89 yea, the thing about Turing machines (and computers in general) is that they rely on very fundamental well-defined bit wise operations, with zero confusion or uncertainty about them, so it's either going to reach some state or it won't. What's interesting philosophically is that it's similar to how we experience reality, i.e. things clearly either exist or they don't (are observed or are not observed), they don't depend on some theoretical assumptions. Which would indicate that the world is much more like a computer (Church-Turing thesis, and then the whole "simulation hypothesis" stuff) than some murky mathematical construct (a la Tegmark). 94. Scott Says: Comment #94 July 9th, 2024 at 1:44 pm fred #91: The question that's attracted the most interest there, is how the probability of there being a solution changes as you adjust the ratio a of clauses to variables in your random 3SAT instance. The big surprise is that there's a "phase transition" at roughly a=4.25, where the 3SAT instances go from almost certainly satisfiable to almost certainly unsatisfiable (and many algorithms to decide satisfiability need more and more time, the closer you get to that critical ratio). This was discovered empirically 30+ years ago and analyzed by the statistical physicists (including Parisi, who won the Nobel Prize for these sorts of studies); since then mathematicians and theoretical computer scientists managed to get fully rigorous proofs of more and more of the picture. Of course this is all in the limit as the number of variables goes to infinity -- a fixed number of variables like 5 would be considered "just a finite computation," unless there were something broader to learn from it. 95. fred Says: Comment #95 July 9th, 2024 at 1:46 pm Scott #94 Thank you so much! I'll look it up. From now on I will test my algorithm around that transition ratio, or see if I can observe it myself (using random instances). 96. Christopher Says: Comment #96 July 9th, 2024 at 1:54 pm Scott #92 A model of physics is a mathematical object that satisfies the laws of physics. It should hopefully be clear that "being a model of general relativity" or "being a model of QM" is expressible in ZFC. For the sake of argument, let's simplify things a bit. Let's assume that digital physics is true (https://en.wikipedia.org/ wiki/Digital_physics) or even that the simulation hypothesis is true (https://en.wikipedia.org/wiki/Simulation_hypothesis). Even if you don't think there is a good argument for the simulation hypothesis, I'm sure you agree it *could* be true. With that simplification, now consider a Turing Machine T implementing that simulation. (T is our "laws of physics.) The running of a Turing machine is something that can be done in any model of Peano Arithmetic! Running a Turing machine only requires first-order induction, not second-order induction. So in M, there will be a "M Scott" somewhere on T's tape. The cells of T are indexed by nonstandard integers instead of standard integers, and the steps are indexed by nonstandard natural numbers instead of standard numbers. But "inside" of M there is no such distinction. And we can ask questions like "who is the first M mathematician to write down the proof of 0=1 from the ZFC axioms" or what not. (If you don't believe in digital physics, the argument must be adjusted to use some other model of physics instead of Turing Machines. Mathematical platonism can then replace the simulation hypothesis. Such a model will likely use infinite sets, but that's no problem if we use ZFC instead of PA! And there are models of ZFC where ZFC is inconsistent.) I think this is all sensible 97. Matthew House Says: Comment #97 July 9th, 2024 at 2:02 pm Scott #89: Under the anti-standard-model viewpoint (which, I should clarify, I don't personally find very compelling, but which I also can't fully refute), the dispute is that "this particular Turing machine doesn't halt on a blank input" isn't a statement that necessarily corresponds to anything in reality, nor is "this particular Turing machine halts in some positive integer number of steps". We can logically assert that one or the other is true, but then when the time comes to actually run the Turing machine, we might fail to find that some machine we proved to halt actually halts, or we might find that some machine we proved not to halt does halt. So BB(n) would still be well-defined (you can't get around the simple argument within the bounds of second-order logic), but the definition would be useless at best and vacuous at worst. 98. Max Says: Comment #98 July 9th, 2024 at 2:08 pm Hi Scott, Could you please clarify the relationship between your use of "absolute" for uncomputability and the discussion here: https:// mathoverflow.net/questions/186372/ are-there-sets-which-are-computable-in-one-model-but-uncomputable-in-another . They seem to conflict and I have no clue ... Thanks! 99. fred Says: Comment #99 July 9th, 2024 at 2:40 pm Peter Donis if I get your post #63, you're saying the function doesn't itself evaluate whether God exists, we're just told that whoever wrote the function wrote it to output 1 if God exists and 0 otherwise. Basically you're asking some all powerful oracle some hard question, and the answer is always either yes or no, but the oracle doesn't give you the answer, it writes a trivial program to output its answer. Sure, I see the trick here, but in the grand scheme of things, we, as humans, interpret the bits in our computers to mean this or that (the state of a computer is just a bunch of on/off switches, not integers, not a simulated video game city, etc)... actually it's not even that we interpret the state of our computers, the computers are actually extension of our minds, in the sense that we're the only ones to map software over the physical systems we call computers, because we're the ones who built them. It's interesting that this somewhat breaks down with LLMs because, although the basic algorithms came out of our minds (back-propagation over large matrices and whatnot), the actual state of the entire machine is so vast and is being massaged so much (the input variables is so vast, i.e. the training set) that we lost connection to it/explanatory power over it. Very much in the same way that it's not because people procreate new people (i.e. having kids) that they're able to understand/control them. 100. Jonathan Weinstein Says: Comment #100 July 9th, 2024 at 2:52 pm I teach an introduction to formal math in an economics PhD program. A major stumbling block is the ability to use formal language properly. A lot of what people say when they are just learning a language is not even false, but poorly formed. "BB(6) is uncomputable" is in this category. Some of the discussion here has suggested that this is false, when it's just meaningless, like Chomsky's "green ideas." Your original HW problem, by using constant functions, makes "uncomputable" meaningful but (trivially) wrong. One reason this confuses people is that they are not used to thinking about trivially true or false assertions. It's a standard background assumption facilitating natural-language communication that people don't, at least intentionally, say things that are trivially true or false. For formal math, understanding which assertions are trivially true or false is a necessary gateway to understanding the formalism, hence the value of the exercise. But it's helpful as a teacher to have a lot of patience for the fact that this mode of thinking is radically new to many people. While we're in a charitable mood, let's imagine someone who just read the Quanta article on BB and tells someone, "Well, this BB function sounds simple, but it is extremely hard to compute, a huge team just managed it for BB(5), but BB(6) will probably always be uncomputable!" Is this person really suffering from a zombie misconception? No, they just haven't learned the formal language. They are trying to communicate the true fact that humans have just figured out BB(5), but BB(6) may remain forever out of reach to humanity. Usually, when we say something can't be done, we mean by humans, with current technology, in a reasonable amount of time, and they have just extended this natural-language idea to computability. Of course this person would need further education if they were ever going to do anything in theoretical CS, but as a casual consumer of pop-science ideas, they're not even genuinely wrong, just not speaking like an insider. Sometimes it might be useful pedagogically to boldface technical terms that can be mistaken for informal concepts, just for the first few exercises on a topic. 101. Scott Says: Comment #101 July 9th, 2024 at 2:55 pm Matthew House #97: So BB(n) would still be well-defined (you can't get around the simple argument within the bounds of second-order logic) Aha! You've conceded the main point! but the definition would be useless at best and vacuous at worst. Useful? Who said anything about useful? If we cared about usefulness, would we be discussing the Busy Beaver function? As for vacuous: I mean, the first 5 values are 1, 6, 21, 107, and 47,176,870. We didn't know the last one till last week, and now we do. Seems pretty non-vacuous to me! 102. Stammanis Says: Comment #102 July 9th, 2024 at 3:05 pm So I feel like there's a misconception here. One can indeed discuss the computability of a single integer like BB(6), because it's a sequence of digits, and it's valid to consider the computability of that integer sequence. 103. Peter Donis Says: Comment #103 July 9th, 2024 at 3:15 pm @fred #99: > "if I get your post #63, you're saying the function doesn't itself evaluate whether God exists" Yes. > "we're just told that whoever wrote the function wrote it to output 1 if God exists and 0 otherwise." That's not quite how I would put it. I would put it that we're told explicitly that there are two trivial functions, a function f1 that always outputs 1 and a function f0 that always outputs 0. Nobody has to "write" these functions except to the extent of showing that they exist, which should be obvious. And we're told that somebody, who knew that these trivial functions already existed, set up a label "f" to refer to one of those two functions, depending on whether God exists or not. That somebody didn't write any functions at all themselves. > "Basically you're asking some all powerful oracle some hard question, and the answer is always either yes or no, but the oracle doesn't give you the answer, it writes a trivial program to output its answer." Not quite. See above. The point is that we don't have to know the answer to the hard question, or ask the oracle anything, to know that whatever function the label f refers to, that function is computable. 104. Scott Says: Comment #104 July 9th, 2024 at 3:19 pm Edan Maor #44 and Max #98: What I meant by computability being "absolute" is just that it doesn't depend on choosing a system of axioms like PA or ZF. There's one notion of "computable by a Turing machine"; the whole point of the Church-Turing Thesis is that essentially any other reasonable notion anyone has proposed has turned out to coincide with that notion. The fact that there isn't an infinite progression of more and more powerful kinds of "computability," like there is for provability, was what Godel himself regarded as the great surprise of Turing's paper. As usual, Godel was right. 105. Scott Says: Comment #105 July 9th, 2024 at 3:24 pm Stammanis #102: So I feel like there's a misconception here. One can indeed discuss the computability of a single integer like BB(6), because it's a sequence of digits, and it's valid to consider the computability of that integer sequence. One more time, if you choose to look at it that way, then BB(6) (like every integer) is trivially computable; there's not even a question about its computability. The question only arises for an infinite sequence of digits. 106. fred Says: Comment #106 July 9th, 2024 at 3:27 pm Peter Donis, "And we're told that somebody, who knew that these trivial functions already existed, set up a label "f" to refer to one of those two functions, depending on whether God exists or not." well, you do refer to somebody special. you can call "f" some kind of innocent label, I call it a function. As I wrote none of this matters, it's no like functions exist in a vacuum and self-assemble, we're the ones interpreting them. The point is that there's still a big "if" in there (if god exists or doesn't), whether that "if" is implemented in a program or in a mind, it's just kicking the can down the road. 107. Stammanis Says: Comment #107 July 9th, 2024 at 3:27 pm I'm still not getting it, unfortunately. Could you please help refer me to a book, or better yet a paper available online, that shows that this sequence of digits is indeed computable? Or maybe, could you try explaining, not why a NUMBER is computable, but why this specific SEQUENCE OF DIGITS that defines BB(6) is computable? Thanks. 108. Scott Says: Comment #108 July 9th, 2024 at 3:29 pm Jonathan Weinstein #100: I completely agree with you about being maximally charitable with students who are struggling to internalize a new way of thinking. Now, anonymous blog commenters who confidently declare I'm wrong and lecture me while displaying freshman-level ignorance of basic concepts? There I'm slightly less inclined to be charitable... 109. Scott Says: Comment #109 July 9th, 2024 at 3:34 pm Stammanis #107: Let a(1),...,a(n) be any FINITE SEQUENCE OF DIGITS. Then here is a program to compute that sequence: for i=1 to n { print a(i); } Again, the fact that we just hardcoded the sequence is irrelevant. It's a program. It exists. We're done. 110. Stammanis Says: Comment #110 July 9th, 2024 at 3:44 pm Thanks. I'm sorry, but I'm still super confused. Isn't your solution here just "passing the buck," by calling this other function a(i) which is undefined? Where does a(i) come from? 111. fred Says: Comment #111 July 9th, 2024 at 3:47 pm I guess one crucial detail in the definition of a Turing machine is this: "the blank symbol, the only symbol allowed to occur on the tape infinitely often at any step during the computation" Otherwise one could prepare the machine by writing all the BB(N) for N=1,2,3,... in order on its infinite tape, and have the Turing machine spit out the right one based on the input n. You just can't feed it infinite data, that'd be cheating! Hence the thing about "computable" referring to an algorithm for ALL input values, without any such cheating. 112. Scott Says: Comment #112 July 9th, 2024 at 3:54 pm Stammanis #110: It's not a function, it's a hard-coded array. 113. fred Says: Comment #113 July 9th, 2024 at 3:56 pm Stammanis #110 yea, and see my point in #111. Using a lookup table is only valid for a finite number of values for N. Nobody is worried about where that lookup table is coming from, we're just saying someone could just happen to use the right one! But this breaks when the sequence is infinite (BB(N) for all N), you can't use an infinite lookup table, it would violate the definition of a valid Turing machine, which defines computability. 114. Joshua Zelinsky Says: Comment #114 July 9th, 2024 at 3:59 pm @Stammanis # "Where does a(i) come from?" Somewhere. We don't know how to get it doesn't stop it from existing. If you prefer the following analogy: there are infinitely many primes. We cannot point to a prime greater than 10^10^10^10 but that doesn't prevent there from being such a prime. Our own lack of knowledge doesn't enter into the existence of that prime just as it doesn't enter into whether the digits of some number are computable. Does that help? 115. Stammanis Says: Comment #115 July 9th, 2024 at 4:01 pm Okay, fine--It's an array. In the syntax I'm familiar with (C++, Java, Python), you'll want a[i] for array element. So your function prints out the array that "a" points to. But what is the function that actually returns that array? That's what I'm really interested in, and having thought about it, I really don't think there's a function returning the array of digits for BB(6). I know I must sound stupid. I'm not familiar with theory of algorithms. So I'm sorry. But I still need help figuring out this concept. 116. Scott Says: Comment #116 July 9th, 2024 at 4:15 pm Stammanis #115: The question was, does a program exist to print the digits? Not how do we find the program, just does it exist? The program with the hard-coded array answers that question. Note that the situation is completely different for the (infinite) halting problem. There, no program exists, even if you had the resources of God Herself to search for the program. 117. Sophia Says: Comment #117 July 9th, 2024 at 4:18 pm I think there is a genuine question here about how willing we are to apply LEM to non-mathematical statements. Consider the following definition: "Let n equal 3 if the Mona Lisa is beautiful, or 5 if the Mona Lisa is not beautiful. Is n prime?" I don't think this question has a good answer. In particular, I don't think "yes" is a good answer, because in order to deduce "n is prime" we would need to apply the LEM to the statement "The Mona Lisa is beautiful". I think that although this sentence has the semantic form of a proposition, it's not actually a proposition, and the LEM can only be validly applied to propositions. I think "God exists" may be another such case. 118. Jair Says: Comment #118 July 9th, 2024 at 4:19 pm Scott #112, I think this would be more clear to Stammanis if you include the initialization of the array. a = (a(1), a(2), ..., a(n)) // Hard-coded sequence for i=1 to n { print a(i); } Or just write print a. It's one of the infinite sequence of programs print 0, print 1, print 2, ..., we just don't know which one. 119. Stammanis Says: Comment #119 July 9th, 2024 at 4:22 pm Thanks. Still not totally wrapping my mind around what's going on here though. Let me rephrase--does there exist a program that will return the hard-coded array you are using in your program? 120. Stammanis Says: Comment #120 July 9th, 2024 at 4:23 pm Maybe in other words, does there exist a program that will output a program for calculating BB(6)? 121. Peter Donis Says: Comment #121 July 9th, 2024 at 4:26 pm @fred #106: > "you can call "f" some kind of innocent label, I call it a function." But it isn't a function. It's just a label that refers to one of two functions, we don't know which, but both of them are computable. That's the point. If f *were* a function that had to first compute whether God exists in order to determine which of the two constant functions to call to get its output, then f's computability would *not* be obvious. But if f is just a label, then the computability of the function pointed to by f *is* obvious, even if the computability of the process that determines which function f will point to is not. But "f" does *not* refer to that process. It's just a label. > "there's still a big "if" in there" Yes, I agree, and in my personal opinion the question as it's posed is not very interesting, because it ignores the big "if". But it's still true that the question as it's posed does not depend on knowing the answer to the big "if" or whether it is computable. It only depends on the fact that the two constant functions are both computable. 122. Scott Says: Comment #122 July 9th, 2024 at 4:34 pm Stammanis #119, #120: Yes. It's just that that program will also hard-code the array, and so on ad infinitum. Hey, you gotta start somewhere! (Or if you didn't want to start with a hard-coding, you could also have the program enumerate over 6-state Turing machines, simulate them, see which ones halt, and search for proofs that the remaining ones run forever, analogous to what was just successfully done for BB(5). Of course, if you wanted to do this with no human supervision, AI would help, and in any case there would be no guarantee of success ... that's what makes this interesting!) 123. Stammanis Says: Comment #123 July 9th, 2024 at 4:35 pm I've been thinking, and I believe I've discovered a new notion of computability! Somethting is computable if there exists a programming calculating it. Something is second-computable is there exists a program outputting a program that calculates it. Something is third computable if there exists a program outputting a program outputting a program that calculates it. Is this a useful idea? 124. S. Waite Says: Comment #124 July 9th, 2024 at 4:41 pm Scott, you lost me: Your's and/or Sipser's definition "computability is about whether a computer program exists to map inputs to outputs in a specified way" and your example Indeed, a fast program that correctly answers the P vs. NP question trivially exists: If P=NP ... makes no sense to me. Here P is a set and NP is a set, and your "fast program" has done and so far in the relevant math can do nothing to execute this If statement so has done nothing to answer the P vs. NP question. Sounds like 'computability' is a silly concept. Indeed just now I'm writing code where the core is If A = B Then where A and B are files on my computer. I am answering this question by using the Windows program FC.EXE via a command line like fc /B A B where the /B asks for a 'binary' comparison. With that I get an answer for If A = B ... and intend to do so continually and routinely 100s of thousands of times. Looks 'computable' to me. For the math you mentioned, e.g., axiomatic set theory, when I was a student, fine, worked through the treatments by Halmos, Kelley, and Suppes. Sipser's work looks harder? My guess is, Sipser is just wrong. By the way, what's with the asterisk on the {0,1}*???? I don't recall seeing that notation in Halmos, Kelley, Suppes, Buck, Apostol, Rudin, Fleming, Cinlar, Knuth, .... 125. fred Says: Comment #125 July 9th, 2024 at 4:43 pm Stammanis #120 I guess it's easy to get hung up on the idea of outputting the right number for BB(6) is some kind of a cheat, but that's not the point. It's just to show that there is a trivial program that "computes" BB(6): the one that happens to print out the right value. And this is a valid program, therefore BB(6) is computable. But you can't pull that trick for all values of N. Maybe the following practical example could help accept that stupidly trivial programs are still valid: Scott wrote above that for SAT, if the proportion of clauses to variables is above some ratio constant k, then it's likely that there's no solution. Therefore you could just write a crappy solver that measures the ratio for a given problem, and outputs that there's no solution if you're above k. That super trivial and stupid program would be right most of the time, on average (but in this case it's an actual algorithm for all N vars and M clauses). 126. Scott Says: Comment #126 July 9th, 2024 at 4:53 pm Sophia #117: Yeah, that's presumably the reason why Sipser changed the problem, in the latest edition, to "f is the constant 1 function if there's life on Mars or the constant 0 function if there isn't" (which I hadn't known until I read the Hacker News thread about this blog post this morning). Personally, though, I'm totally fine with applying LEM in Sipser's original example, your example, any of them. In each case we're effectively saying, "an integer will be set to either 3 or 5 in some unclear and undetermined way; will it then be prime?" And the answer to that question is yes. 127. Scott Says: Comment #127 July 9th, 2024 at 4:58 pm Stammanis #123: No, not useful. To say it [deep breath] one more time, what makes Turing's definition useful is that it asks whether there exists a finite object (a program) to compute a given function on infinitely many inputs. That's a non-vacuous question to which the answer is not always "yes." 128. fred Says: Comment #128 July 9th, 2024 at 5:00 pm Stammanis #120 Also, you're having some difficulty because you're focused on a specific definition of the number 47176870, that's it's the value for BB(5). But here's another totally valid program that computes and returns 47176870: f() { int a = 4172; int b = 3901; int c = 3814; int d = 83; return (a*a + b*b + c*c + d*d); } Is this enough of a computation for you? 129. Scott Says: Comment #129 July 9th, 2024 at 5:02 pm S. Waite #124: Yes, computability is a silly concept when applied to finite strings (where the answer is always "yep, that's computable"), as opposed to infinite sequences or functions with infinitely many inputs (where the concept is deep and meaningful). That's the point. 130. Scott Says: Comment #130 July 9th, 2024 at 5:05 pm Everyone: I'll close down this thread later tonight, since alas, unlike the value of BB(6), it seems that the supply of people who don't get the definition of computability is infinite, and I lack infinite time to run the finite brain-program that answers them... 131. Stammanis Says: Comment #131 July 9th, 2024 at 5:10 pm But...EVERYTHING that an actual computer does is finite, so this would mean that Turing's definition is useless to actual computers! Please help me make sense of this. Also, with the hard-coded array thing, it doesn't make sense because you're going to get a memory overflow for that code above a certain integer. 132. Matthew House Says: Comment #132 July 9th, 2024 at 5:29 pm Scott #101: The contention here would not be that the definition of BB(n) is useless in the sense of not having amazing use cases, but rather in the sense that "the witness of !Con(PA)" within PA + !Con(PA) is useless, since it most likely says nothing about reality. (So I suppose our objector *would* have a problem with LEM, saying that it should not be generally applied to every possible qualified proposition about "all integers", but only for those specific propositions which can be assigned a truth value using acceptable axioms. This would include basically every proposition that comes up in ordinary mathematics, i.e., every case where our intuitive idea of the integers is known to hold up.) 133. Scott Says: Comment #133 July 9th, 2024 at 5:44 pm Stammanis #131: Turing's definition is an idealization, just like the frictionless planes of Newtonian physics. The memory is unbounded, although in t time steps you can access at most t memory cells. It's best to think of a machine with a gigantic external hard disk, or read/write access to the whole Internet. If you want a programming language that works similarly, you can do it by allowing an unbounded integer data type (using dynamically allocated memory). If you want to learn more, let me recommend in the strongest terms that you check out the Sipser textbook mentioned in this post, or Arora-Barak or Mertens-Moore or other fine theory of computing textbooks. Leave a Reply You can use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations. Comment Policies: 1. All comments are placed in moderation and reviewed prior to appearing. 2. You'll also be sent a verification email to the email address you provided. YOU MUST CLICK THE LINK IN YOUR VERIFICATION EMAIL BEFORE YOUR COMMENT CAN APPEAR. WHY IS THIS BOLD, UNDERLINED, ALL-CAPS, AND IN RED? BECAUSE PEOPLE ARE STILL FORGETTING TO DO IT. 3. This comment section is not a free speech zone. It's my, Scott Aaronson's, virtual living room. Commenters are expected not to say anything they wouldn't say in my actual living room. This means: No trolling. No ad-hominems against me or others. No presumptuous requests (e.g. to respond to a long paper or article). No conspiracy theories. No patronizing me. Comments violating these policies may be left in moderation with no explanation or apology. 4. Whenever I'm in doubt, I'll forward comments to Shtetl-Optimized Committee of Guardians, and respect SOCG's judgments on whether those comments should appear. 5. I sometimes accidentally miss perfectly reasonable comments in the moderation queue, or they get caught in the spam filter. If you feel this may have been the case with your comment, shoot me an email. [ ] Name (required) [ ] Mail (will not be published) (required) [ ] Website [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [Submit Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] --------------------------------------------------------------------- Shtetl-Optimized is proudly powered by WordPress Entries (RSS) and Comments (RSS).