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 Gödel incompleteness. While they’re closely related, only Gödel 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?
Follow
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…
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. 😀
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.)
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.
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.
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.
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.
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”?
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.”
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.
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.)
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.)
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.
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.
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.” 🙂
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.)
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.
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.
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…
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!
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.
Comment #22 July 8th, 2024 at 6:36 pm
BT_Uytya #21: Interesting! I hadn’t made that connection.
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.
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”.)
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?
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!
Comment #27 July 8th, 2024 at 7:57 pm
Travis Allison #23: YES!!!!!
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.
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.
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.
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.
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.
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?
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".)
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.
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.
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 “Gödel, Escher, Bach”, in which one of the characters wrote down a Diophantine equation describing the Gödel number of a proof of FLT, simplified it vigorously, and was startled to find it came out to be the Fermat equation itself, aⁿ+bⁿ=cⁿ. 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.”)
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.
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.
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”
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?
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.”
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.)
Comment #44 July 9th, 2024 at 3:36 am
> While they’re closely related, only Gödel 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!)
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.
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.”
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)… 🙂
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).
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 Gödel anymore.” And Gödel himself, an 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.
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 …
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…”
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.
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.
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.”
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.
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.
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.
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?
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.
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 the Riemann Hypothesis follows from P=NP and also that it follows from P≠NP … well then, 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 Schrödinger 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.
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?
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.
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.
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).
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.
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.
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.
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.
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.
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
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 🙂
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?
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\).
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?
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).
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)=n2 is computable, but BB(n) is uncomputable (because it would let us solve the halting problem).
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).
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!)
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)
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
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.
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.
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.
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.
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.
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?
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.
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.
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.
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.
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).
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.
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).
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 α of clauses to variables in your random 3SAT instance. The big surprise is that there’s a “phase transition” at roughly α=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 different but related 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.
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).
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 🤔
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.
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!
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.
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.
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!
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.
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.
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 Gödel himself regarded as the great surprise of Turing’s paper. As usual, Gödel was right.
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.
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.
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.
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… 😀
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.
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?
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.
Comment #112 July 9th, 2024 at 3:54 pm
Stammanis #110: It’s not a function, it’s a hard-coded array.
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.
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?
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.
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.
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.
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.
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?
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)?
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.
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!)
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?
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,
….
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).
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.
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.”
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?
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.
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… 😀
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.
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.)
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.
Comment #134 July 9th, 2024 at 6:10 pm
I appreciate your patience, Professor, but I still don’t quite get it. You mentioned that Turing’s definition is an idealization, like frictionless planes. But how can we rely on these idealizations if they don’t apply to real-world scenarios? And about the hard-coded array—if the memory is unbounded in theory, wouldn’t that just mean the program could run indefinitely without actually solving the problem? How do we ensure it doesn’t just keep running forever without giving us the sequence for BB(6)?
Comment #135 July 9th, 2024 at 6:14 pm
Here is the answer of chatgpt:
The function is not computable in the classical sense of computability theory. Here’s why:
1. **Undefined Determination**: The function \( f \) depends on the existence of God, which is not a computable concept. There is no algorithm or procedure that can definitively determine whether God exists or not.
2. **Computability and Formal Systems**: Computability theory deals with functions that can be computed by an algorithm or a Turing machine. This requires a well-defined procedure to compute the output for any given input. The concept of God’s existence does not fit into this framework because it is not something that can be formally decided by a computation process.
3. **Implications of the Definition**:
– If God exists: \( f(x) = 1 \) for all \( x \in \{0,1\}^* \).
– If God does not exist: \( f(x) = 0 \) for all \( x \in \{0,1\}^* \).
The function \( f \) is constant, but its definition hinges on a non-computable predicate (God’s existence).
4. **Non-computable Predicates**: Computable functions are those for which there exists an algorithm that can compute the function’s value for any input. Since the concept of God’s existence is not computable, any function directly depending on it (like the function \( f \) here) cannot be computable either.
In conclusion, \( f \) is not computable because its definition depends on the non-computable predicate of God’s existence. Therefore, \( f \) does not fit into the framework of computable functions as defined in computability theory.
Comment #136 July 9th, 2024 at 6:16 pm
Claude is not better:
This is an interesting question that touches on both computability theory and philosophy. Let’s break it down:
1. Definition of f:
f(x) = 1 if God exists
f(x) = 0 if God does not exist
2. Computability:
A function is considered computable if there exists an algorithm that can produce the output for any given input in a finite amount of time.
3. Analysis:
The computability of f depends on whether we can definitively determine the existence or non-existence of God through a finite computational process.
The problem here is that the existence of God is a metaphysical question that has been debated for millennia without a conclusive, universally accepted answer. It’s not a question that can be resolved through purely logical or empirical means within a finite computation.
4. Conclusion:
Given our current understanding, f is not computable. This is because:
a) There’s no known algorithmic process to definitively determine the existence or non-existence of God.
b) Even if f has a constant value (either always 1 or always 0), we don’t know which constant it is, and we have no computational method to determine it.
This function falls into a category similar to uncomputable functions like the halting problem. While f would always return the same value for all inputs, we have no way to computationally determine what that value should be.
It’s worth noting that this conclusion is based on our current understanding of computation and metaphysics. If a method to definitively prove or disprove the existence of God were to be discovered, this analysis would need to be revisited.
Comment #137 July 9th, 2024 at 6:17 pm
Sisper’s problem is one of my favorite poetic devices the Double Entendre.
Comment #138 July 9th, 2024 at 6:18 pm
ChatGPTo #135: OK, but next try explaining the correct answer and see what GPT says about it! (Or I’ll try.)
Comment #139 July 9th, 2024 at 6:19 pm
Gemini is even more interesting (but still wrong)
The question of whether a function depends on the existence of God is not answerable within the framework of computability theory. Computability deals with what can be mechanically computed, and the existence of God is a philosophical or theological concept that cannot be proven or disproven through computation.
Here’s an analogy:
* Let n equal 3 if God exists, or 5 if God does not exist. Is n prime?
Similar to the function f, the value of n depends on a concept outside the realm of mathematics. Just as we cannot determine the primality of n in this way, we cannot determine the behavior of f using computability.
However, if we rephrase the question to focus solely on the function’s behavior for concrete inputs (strings of 0s and 1s), then it becomes a well-defined question in computability theory.
* There are only two possible well-defined functions f:
* The constant 0 function: f(x) = 0 for all x in {0, 1}*. This is a computable function.
* The constant 1 function: f(x) = 1 for all x in {0, 1}*. This is also a computable function.
Therefore, regardless of the underlying reason for f being a constant function, its computability depends on which constant value it outputs. Both constant 0 and constant 1 functions are computable.
Comment #140 July 9th, 2024 at 6:25 pm
If I explain:
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
Then the answer is
You’re correct. The function \( f \) itself, whether it’s the constant 1 function or the constant 0 function, is indeed computable. Here’s why:
– **Definition of Computability**: A function is computable if there exists a Turing machine that, given any input, produces the correct output in a finite amount of time.
– **Constant Functions**:
– The constant 1 function, which maps any input \( x \) to 1, is computable because there is a Turing machine that, for any input \( x \), outputs 1.
– Similarly, the constant 0 function, which maps any input \( x \) to 0, is computable because there is a Turing machine that, for any input \( x \), outputs 0.
The crux of the problem is that \( f \) is either the constant 1 function or the constant 0 function, depending on whether God exists or not. Regardless of how we determine which constant function \( f \) actually is, both possible functions are computable. Therefore, the function \( f \) is computable.
Here’s a detailed reasoning:
1. **Computability of Constant Functions**:
– There exists a Turing machine \( T_1 \) that, for any input \( x \), always outputs 1.
– There exists a Turing machine \( T_0 \) that, for any input \( x \), always outputs 0.
2. **Behavior of \( f \)**:
– If \( f \) is the constant 1 function (i.e., \( f(x) = 1 \) for all \( x \)), then \( f \) is computable by \( T_1 \).
– If \( f \) is the constant 0 function (i.e., \( f(x) = 0 \) for all \( x \)), then \( f \) is computable by \( T_0 \).
3. **Conclusion**:
– Since both possible forms of \( f \) (the constant 1 function and the constant 0 function) are computable, \( f \) itself is computable.
Thus, regardless of the philosophical implications of determining the existence of God, the function \( f \) is computable because it is defined as a constant function, and both constant functions are computable.
Comment #141 July 9th, 2024 at 6:26 pm
Stammanis #134: We learn about real computers from Turing’s idealization in much the same way we learn about real physics from Newton’s frictionless-plane idealization. Namely, first answer the question in the idealized scenario (with unbounded memory and infinitely many possible inputs), where clean and enlightening answers are possible, then apply whatever corrections are needed in light of the absolute limits on time and memory.
Sure, there are programs that run forever without printing BB(6), but what of it? There are other programs that print BB(6) and halt.
You’ve reached your question limit. For more, please check out the resources I mentioned in comment #133. Best wishes!
Comment #142 July 9th, 2024 at 6:36 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
Because you’re focusing on Turing’s definition as a statement about what computers CAN do whereas (if I understand it correctly), it’s much more relevant as a statement about what computer’s CAN’T do.
You might think that given a computer with infinite memory and infinite time, a computer could do anything — at least anything that could be rendered in a form that the computer could process. It turns out it can’t! Isn’t that fascinating?
Comment #143 July 9th, 2024 at 8:19 pm
Alex Shibiakov #55, ZFC might be consistent but false! So ZFC might prove that some specific TM halts when in fact it never halts. That could very well confuse the status of say BB(500). Nik Weaver has an article suggesting something like that is actually going on with ZFC.
Comment #144 July 9th, 2024 at 8:19 pm
Following up on Scott #133: It’s easy to give a function that’s uncomputable, but we can easily compute it on any input less than 10^100. Namely: Let f(x)=0 if x<10^100, f(x)=BB(x) otherwise. If all the natural examples of uncomputable functions had turned out to be like my f, then Turing-computability would be a much less useful concept and perhaps none of us would have heard of it. However, it so happens that most natural examples, like BB, turn out to get pretty hard (in an informal sense) for fairly small inputs. (And similarly for NP-hardness.) For practical purposes, that informal "hardness" is what we actually care about, but there's no elegant definition of it for finite problems, so we use the definition for infinite sequences of problems. This leads to elegant theory, which doesn't say anything directly about any finite problem, but turns out to be quite illuminating.
I like the analogy to frictionless planes.
Comment #145 July 9th, 2024 at 8:24 pm
Scott #51. I know that your comment on how to introduce CS theory was probably off the cuff, but I want to caution against making something seem mysterious. I think the whole point of learning is to remove mystery. Your introductory description to CS theory only makes sense to someone who has some experience in CS theory. (Is your “weapon” the concept of a TM? I am not even sure what you are talking about.)
I think a mistake that a lot of teachers make is to introduce a topic that makes sense from an abstract point of view based on their years of experience. The words you are using make sense to you because these words (“weapon”, “some specific bit of information is knowable”) are hooked into different concepts in your mind that your students don’t know about. For them, your introduction is just a word salad, using individual words that they know the meanings for in other contexts but not the meaning in the way that CS theory uses them.
There is *not* anything deep about the fact that every finite set of numbers is computable. It’s a vacuous consequence of the current definition of computable. It’s good that your students understand that. There *could be* other definitions of computable that make it such that not every finite set of numbers is computable. Would that definition be useful? Perhaps not, but exploring possible different definitions of computable might allow the student to see the different tradeoffs that occur. Some questions become vacuous, but others become tractable. Learning occurs when a student realizes that these definitions are made by people, often for specific reasons, sometimes just a historical accident. There is nothing god given about them. And in fact, challenging definitions and exploring new ones is often a way to advance a field.
Comment #146 July 9th, 2024 at 8:49 pm
Travis Allison #145: Sometimes, though, the actual truth of the matter is that you have to say, “the spectacular and obvious success that this field (physics, CS, etc) has achieved over the years is a good enough reason for me to devote X time to studying it.” And if, in your study, you constantly dismiss every assumption and idealization that the experts converged on—“but how can you assume a frictionless plane? of course there’s friction! how can you look at the limit as inputs get arbitrarily large, when we know the input length will never exceed a googol?”—well then, you’ll never make any progress.
Granted, most students err in the opposite direction. They don’t question what they’re taught nearly enough, but just receive and regurgitate, as mindlessly as they can without tanking their GPA. But show me someone who thinks it’s impossible to err by questioning basic definitions and concepts too much when first encountering them, and I’ll show you someone who hasn’t spent much time arguing on the Internet. 😀
Comment #147 July 9th, 2024 at 9:58 pm
flergalwit #29: “Unfortunately, it’s difficult or impossible to make this intuition precise, which is (one reason) why the formal notion of computability is defined differently.”
It doesn’t seem at all impossible to make this notion of computability precise, see comment #18 by Joshua Grochow who provided an explicit attempt at that.
Anyway, this common notion of computability essentially tries to achieve the same thing as the usual formal one, but without relying on the infinity trick (against “cheating” in the infinite case) which Gary Drescher #13 pointed out. So the common doesn’t allow”cheating” in general, not just for cases where the algorithm would have to be infinitely long (which isn’t allowed) in order to cheat, but also for cases where the cheat would be of finite length and thus (arguably mistakenly) declared “computable” by the usual formal definition.
Comment #148 July 9th, 2024 at 10:18 pm
Scott #46: Uncomputable elements are the avocado and uncountable sets are the guacamole (just don’t ask me to commit seppuku for your lunch!).
And having sets with filled (almost entirely) with uncomputable objects matters! Like you can make two balls from one ball of the same size. Question is, why don’t TCS practitioners raise their eyebrows at these mathematicians?
“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.”
But can you name a single tangible result we would lose?
On the misconception about undecidability and NP-hardness, it’s also related to the unreasonable success of these concepts. If BB(k) and all other undecidable problems were actually something we can compute in k clock cycles on modern machines up to size k = 10^20 or so, we probably wouldn’t take undecidability as seriously. Also if we could solve arbitrary SAT problems up to that size, no one would worry about Cook’s theorem. It isn’t just that all benchmarks ever conducted can’t say anything about the asymptotics, its that the asymptotics somehow actually manage to say something about these benchmarks!
Comment #149 July 9th, 2024 at 11:19 pm
I think that one origin of this Zombie Misconception is the fact that when theoretical CS experts relate theoretical results to applications, they often say things that contribute to this misconception for readers who take their statements excessively literally.
For example, CS experts often loosely say things like “If I found an algorithm that could solve any NP-complete problem in polynomial time, then I could use it to quickly crack RSA-2048”. As you of course know, there are a whole bunch of implicit assumptions hidden in that statement: (a) the exponent and prefactor of the polynomial are both moderate-sized, (b) 2048-bit instances of the factoring problem are already out on the asymptotic tail of the algorithm, (c) the required memory is within today’s practical limits, etc. You inherently need all those implicit assumptions in order to get from the first half of the stated claim, which is a proposition about infinite sequences, to the second half, which is a proposition about a very different type of object, a huge but finite number of specific instances, which could in principle just be hard-coded into a massive precomputed lookup table.
Of course, loose statements like this don’t cause any confusion for experts, who have all those implicit assumptions fully internalized – but I can see how they could contribute to the Zombie Misconception for beginners.
It seems to me that pretty much any attempt to tie results from theoretical CS to any kind of applied problem runs the risk of contributing to this confusion – because applied problems have to run on actual physical computers, which have finite memory, so basically any problem in applied CS is inherently about (huge but finite collections of) problem instances, rather than full problems.
Unfortunately, I’m not quite sure how to solve this problem. Clearly the solution isn’t to explicitly spell out all those assumptions every time; that might be pedagogically useful to beginners, but it would make CS results impractically cumbersome to communicate between experts.
Comment #150 July 9th, 2024 at 11:36 pm
Jonathan Weinstein #144: Technically, there is a perfectly sound definition of “hardness” for finite problems, it’s just not a TCS definition. Instead, it is a series of definitions in the field of cryptography, the foremost of which is the idea of “computational feasibility.” In broad terms, the idea is that nobody is ever going to be able to perform 2^256 computational operations within anything remotely approaching a reasonable period of time, so if you can prove (or at least convince yourself) that they will need to perform more operations than that, then you can declare the whole thing de facto impossible for any real human to compute (a formal proof is usually regarded as not strictly necessary, because in practice, if nobody knows how to break it, then nobody is going to break it). There are also a host of more specific definitions, many of which are concerned with questions such as “What if the adversary knows or can discover X, Y, and Z, does that make it any easier for them? How much easier?”
But the important observation here is that cryptography is concerned with practical results over specific finite objects (encrypted messages). It is not answering the same question at all as computability or even complexity theory (a positive resolution to P = NP would probably have implications for at least some encryption algorithms, but those implications would be of the form “find a problem with larger constants and/or stop using NP-hard problems for encryption,” and not “oh shoot, all of cryptography is dead, we should just give up now”).
Comment #151 July 10th, 2024 at 3:37 am
🥑 #148: The request for a “single tangible result we would lose” without uncountability is a weird one, because yes, you can always perform the exercise of extracting the “tangible” part of a result while banishing uncountable sets. In the extreme case, that could literally look as stupid as waving a wand over your entire proof and saying, “OK, but now imagine this all takes place inside a countable model of ZFC, so all the supposedly uncountable sets are secretly countable, it’s just that the model doesn’t know it.” If you don’t want it to look that stupid, you’ll probably have to use computable real analysis or something else that forces you to do massively more work.
To me, this is really no different from the fact that every argument involving complex numbers can be “compiled down,” as far as its “observable implications” are concerned, to an argument that never mentions complex numbers at all. This can be done either stupidly, by replacing every complex number by an ordered pair of reals that “just so happens” to obey all the same relations as the complex numbers do, or (usually) at the cost of a lot more work, as for example with the Erdös-Selberg “elementary” proof of the Prime Number Theorem that avoids complex analysis. But do you similarly want to excise complex numbers from math on this basis? Heaven help you.
As one small example of a “real-life situation” where I’d have to work harder, consider the Solovay-Kitaev Theorem, a fundamental result in quantum computing that tells you how to approximate a desired unitary transformation by a quantum circuit over some fixed finite set of 1- and 2-qubit gates. The first obvious question any student will ask is, why only approximate the unitary rather than representing it exactly?
If I’m off your leash, I’ll answer the student in one sentence: it’s because there are uncountably many unitaries, but only countably many quantum circuits over a finite gate set. On your leash, I’ll have to think of a more complicated way to say it. Now multiply this example across every single friggin day of my scientific life.
Comment #152 July 10th, 2024 at 3:56 am
And regarding the “unreasonable success” of asymptotic concepts in real-world CS: I mean, it’s not really that unreasonable, if you regard those concepts as encoding fundamental truths about computation, with the finite-n effects being less-fundamental sources of noise and complication!
It’s almost exactly like the “unreasonable success” of Newtonian mechanics, here on a planet filled with friction and air resistance and all the other phenomena that disguise Newton’s laws. Sure, the success looks unreasonable … to an Aristotelian. It stops looking so unreasonable once you become a Newtonian.
Comment #153 July 10th, 2024 at 4:07 am
Ted #149: You’re surely correct that we in TCS contribute ourselves to the Zombie Misconception, every time we talk about the real-world implications of TCS less than maximally carefully. But like you, I don’t see an obvious solution to this. If you really do regard asymptotic behavior as “more fundamental” than finite-n effects, then it’s an intolerable imposition to have to translate every single sentence into finite-n language, rather than just giving occasional reminders.
And so, for want of a better way out, here I am writing this blog post and answering comments on it! 😀
Comment #154 July 10th, 2024 at 4:23 am
Kevin #150: I agree with almost all of what you say, except that if P=NP, then I really do predict that practical hardness-based cryptography would be, to use the technical terminology, up shit creek without a paddle. Sure, it’s conceivable that there’d be a one-way function (maybe even a trapdoor one?) that took linear time to compute but n10000 time to invert, and we could all switch to that and be fine. But such a hypothetical one-way function would either be “out there in the cold,” a random accident with no principle to undergird its existence, or else the principle would have to be an entirely novel one, which would somehow rise from the ashes of the failed P≠NP hypothesis.
Comment #155 July 10th, 2024 at 5:27 am
I don’t think that you are doing the question justice. I understand that the question, as you stated, is formally nonsense. But I also think that there is a very fair intuitive question to be made: “P != NP states that some proofs are hard to find. Let us suppose that P != NP. Could the proof of P != NP be one such hard-to-find proof?”
The strongest possible formal version of an answer to this question would be:
Meta-statement 1: If P != NP then ‘P != NP’ is independent of ZFC.
Maybe Meta-statement 1 is itself probable in ZFC? If this sounds implausible, remember the following:
Meta-statement 2: If (subexponentially-hard) one-way functions exist, then ‘P != NP’ cannot be proven using natural proofs.
This is the Natural Proofs barrier of Razborov and Rudich. It is very similar in flavor to Meta-statement 1, but it takes a stronger premise and derives a different conclusion. The conclusion is not formal, since the notion of a natural proof is semantic in the same sense that BPP is semantic. But it is a very strong conclusion anyway. It is not even clear that it is intuitively a weaker conclusion than the conclusion of Meta-statement 1, to me it just seems incomparable. Afaik, all known lower-bounds between models with similar resources are natural.
So yes, I think that it is fair to say that P != NP stands in the way of its own proof, or, at least, that the existence of cryptography stands in the way of a proof that P != NP.
As for proving meta-statement 1, I’m pretty sure that Razborov himself has tried to do that. He has succeeded in proving the following very interesting statement:
Meta-statement 3. If (subexponentially-hard) one-way functions exist, then S^2_2 cannot prove P != NP.
Where S^2_2 is a particular weak theory of bounded arithmetic. The Bachelors’ thesis of Jan Pich gives a full proof of this statement (Bounded Arithmetic and Theory of Razborov and Rudich).
Comment #156 July 10th, 2024 at 6:59 am
I might be being dumb but while I’d like to think I understand computability I still agree with #39 above that the example (using existence of God) is very misleading (and Sipsers exercise is a joke) because such a function is ill-defined — how can we talk about the range of a function, if the function hasn’t been defined.
Help me understand.
Consider:
g: N \to N as n \mapsto 3 if ‘close the door’ and 5 if ‘don’t close the door’
Is g computable ?
Comment #157 July 10th, 2024 at 7:54 am
AoN #156: If you’re telling me that g(n) is either the constant 3 function or the constant 5 function, based on some criterion that I don’t understand (but that doesn’t depend on n), then yes, of course g is computable.
Comment #158 July 10th, 2024 at 8:23 am
Bruno Loff #155: Well, of course my answer didn’t do justice to the enormity of P vs NP, including Razborov-Rudich and its other self-referential and metamathematical aspects! That’s why I wrote a whole 120-page survey article on P vs NP, covering those aspects in depth.
And if a novice asked me the “could P vs NP be NP-hard?” question in a spirit of genuine curiosity, then absolutely, I’d try to hint about Razborov-Rudich and all the other profundities in my answer, time permitting. Alas, I’ve also often been asked this question (thankfully, almost never by my actual students!) in a spirit of condescension, of “theoretical computer science seems to me like just a trivial game of word-associations, and I’ll show the supposed experts I can play it better than they can.” The person who asks in that spirit deserves only to have their conceptual howler pointed out to them.
Comment #159 July 10th, 2024 at 9:39 am
“I’ll answer the student in one sentence: it’s because there are uncountably many unitaries, but only countably many quantum circuits over a finite gate set.”
You fail to mention that there’s no way your finite gate set can even begin to approximate almost any of those.
Comment #160 July 10th, 2024 at 9:55 am
Avocado #159: If it’s over a small number of qubits (the usual setting of Solovay-Kitaev), then sure, I can approximate any of them to ε precision, using polylog(1/ε) gates. And this is essentially optimal by a counting argument—which, in the limit ε→0, shades into the fact that circuits are countable but unitaries are uncountable.
Comment #161 July 10th, 2024 at 10:05 am
It seems to me that there is a sensible notion that people are trying to express by “BB(10000) is uncomputable”, although it is not the standard notion of “uncomputable”, and I’m not sure that I could find any way to make it mathematically precise.
We know that there is no algorithm which computes BB(N) for all N. One could nevertheless imagine an algorithm which takes input N and tries to compute BB(N), sometimes returning a correct answer and sometimes failing to terminate. For example, it could run all N state Turing machines until they either terminate or go into a repeating loop which writes no new characters. (If some N state machine went into a loop which did write characters, then this algorithm wouldn’t terminate.) One could imagine an algorithm which detected more sophisticated loops. The extreme version of this is to have an algorithm which looks for proofs (in PA or some other formal system) that a machine doesn’t terminate.
I think what someone who says “BB(10000) is uncomputable” means is “no reasonable algorithm as above will halt on the input 10000”. The trouble, of course, is the word reasonable. Because there is an unreasonable algorithm — the one that manually checks whether the input is 10000 and returns BB(10000) in that case (and does something more reasonable if the input isn’t 10000).
Now, the student who hasn’t seen the issue of the unreasonable algorithm in the previous paragraph is definitely missing something. But I don’t think their ideas are useless, either.
Comment #162 July 10th, 2024 at 12:33 pm
asdf #143: This is a great point but I am not sure I would characterize this as `ZFC being false’ (I guess it is really up to anyone’s philosophical bend). The situation you describe is in fact bound to happen if ZFC is consistent. Indeed, let’s say for every non-halting TM in the ‘BB(1000) pool’ there is a proof that it does not halt. Then of course one can combine all those proofs with the ‘finite runs’ of the remaining TM’s to finish the proof of the (correctness of the) value of BB(1000). On the other hand, if adding statements like ‘TM 109876 in the BB(1000) pool halts’ leads to a contradictions for all those TM’s that do not halt then, the demonstrations of those contradictions constitute the proof that the specific machine does not halt. Thus, there is at least one TM in the BB(1000) pool (sorry if this is not the correct terminology) such that the statement ‘TM blah-blah-blah halts’ is independent of ZFC. Of course the number of steps after which it ‘halts’ is not a standard number (in the sense of nonstandard analysis) so there is no ‘physical contradiction’ to be had, so to speak. ZFC is not unique in that respect, since any rich enough theory with have this ‘flaw’.
Comment #163 July 10th, 2024 at 12:55 pm
On another moment’s thought the argument in my previous comment (in response to asdf #143) does not really show independence but that there is a TM that does not halt but the statement that it does is consistent with ZFC. It may, in fact be even provable in ZFC, in which case, this can be taken as evidence that ZFC is ‘false’. Now that would be something!
Comment #164 July 10th, 2024 at 1:37 pm
Suppose that we make the following claim: Let F be the shortest proof of theorem T (P != NP or whatever else). Let |F| be the length of F as written in Lean or Coq, with basic text compression. The claim is now that there is no program that outputs a proof of T in Lean/Coq that both (a) is significantly shorter than |F|; (b) runs reasonably quickly, So condition (a) rules out the trivial algorithm “Print F” where F is written out in full and (b) rules out the almost trivial algorithm, “Generate all strings in sequence until one of them is a proof of T”. Is there some other trivial solution that satisfies both of these? Is this a plausible formalization (up to the vaguenesses of “basic text compression”, “significantly shorter” and “reasonably quickly”) of the informal claim that there is no workable algorithm that finds a proof of T? Has anyone looked at this combination, and if so does it go anywhere?
Comment #165 July 10th, 2024 at 2:50 pm
Ernest Davis #164: So basically, you want to ask about the minimal time-bounded Kolmogorov complexity of a proof of P≠NP or whatever. That’s nice; I like it!
Certainly time-bounded Kolmogorov complexity has been extensively studied in general. Alas, as won’t surprise you, it seems almost impossible to make strong statements here about the proofs of particular conjectures like P≠NP, or even known theorems like Fermat. For one thing, as you already acknowledged by talking about Coq/Lean, standard text compression, etc., the answers for specific conjectures could be heavily dependent on our choice of programming language. E.g., consider a programming language that happens to contain a PrintAProofOfFermatsLastTheorem() command. 😀
Comment #166 July 10th, 2024 at 3:22 pm
David Speyer #161:
The threshold of “reasonableness” should be stricter than what you’re implying. I imagine that in a closed system, Landauer’s principle would force the TM running the unreasonable algorithm to make errors – due to overheating – way before it halts.
Comment #167 July 10th, 2024 at 6:31 pm
Perhaps you should also mention the Collatz conjecture as part of this discussion. Of course there is a program that prints “Collatz is true” and a problem that prints “Collatz is false”. But the generalized Collatz problem is undecidable, and a particular Collatz-like instance is exactly the sort of thing that makes BB(6) so hard for us to nail down exactly, even though BB(6) has a specific value.
The Collatz conjecture may be decidable. But the general problem is not. As Gil Kalai says, though, the general problem being hard gives some kind of intuition as to why specific cases are hard.
Comment #168 July 10th, 2024 at 11:47 pm
Scott 160: That’s false. The computable unitaries over a finite number of qubits is in fact a countable (but not computably enumerable) set! What if the student says great, now I can use Solovay-Kitaev to help me apply the unitary {{1, 0},{0, e^{i a}} where a is uncomputable, like 1/(BB(1) + BB(2) + ….).
This is the demon Cantor has placed at the heart of modern mathematics, based on a proof showing that the elements of the set are almost entirely uncomputable. Except that he did it before computability theory was developed, but what’s our excuse?
Comment #169 July 11th, 2024 at 4:15 am
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”?
Collision-resistance does not mean that no collisions exist at all. Even in theory, all cryptographic hash functions have collisions, since all of them support, by definition, inputs that are larger than their output. Collision resistance only means that it is computationally hard to compute/find collisions.
Yes, in cryptographic theory, hash functions are infinite families of functions. However, all functions of these families have finite output. And as soon as you fix a security parameter (a number specifying your wanted security level, more or less), you choose one specific hash function from this familiy.
Dropping in SHA-256 for a theoretical hash function is perfectly valid, as long as you believe that SHA-256 is a) collision resistant and b) it fits to the security parameter you need. Of course, if you don’t believe that, then you shouldn’t use SHA-256 to instantiate your cryptographic scheme/protocol/whatever.
You can of course ask why you should believe that SHA-256 is collision resistant, since there is no formal proof for this. But that is another question.
Comment #170 July 11th, 2024 at 7:33 am
Avocado #168: Sure, computable unitaries are a countable set. You’re being to sloppy in saying they’re “not computably enumerable”: how are the unitaries even specified? I can enumerate the programs that generate the computable unitaries. Of course most of them have entries for which it would take infinite time just to print their decimal expansions, although I could do so in dovetailing fashion.
You could absolutely use Solovay-Kitaev to approximate the unitary you said, insofar as you knew its entries. If you don’t know the entries that isn’t Solovay-Kitaev’s fault.
The mathematicians who thought Cantorian set theory was demonic lost in the 20th century — because while they were endlessly relitigating their ideology, everyone else just got on with developing math, using Cantor’s concepts wherever appropriate. (How many Fields Medalists, for example, would have any patience for a ban on uncountable sets?) If you want to excise Cantor, your task is much larger than arguing with me or a thousand other people — it’s to create an alternative so compelling that everyone makes the switch. Good luck with that.
And thanks for commenting, but I said what I wanted on this and won’t be replying further.
Comment #171 July 11th, 2024 at 8:18 am
David Speyer
“It seems to me that there is a sensible notion that people are trying to express by “BB(10000) is uncomputable”,”
For starter, BB(10000) is so huge that actually writing down BB(10000), by either hardcoding it or generating it, would be beyond practical reach 😛
Comment #172 July 11th, 2024 at 8:26 am
Scott #165
“E.g., consider a programming language that happens to contain a PrintAProofOfFermatsLastTheorem() command.”
Strictly speaking, a command like “print_PI()” would be part of some “library” written on top of the language, which could be considered part of the language I guess (but usually it isn’t). And then it’s up to the command’s implementation to rely on some hardcoded constant or some compact algorithm, etc.
But such commands wouldn’t be required to be part of the minimal set of language features that makes the language Turing complete.
Comment #173 July 11th, 2024 at 9:08 am
I am a bit surprised of the use of God in your exemple, as the Continuum Hypothesis (or even the infinity of prime twins) gives the same result, without any sidetracking in theological disputes. Another question is (with the hypothesis that the TM with 10 ^^15 steps is the one giving BB(6) ) : what exactly means « the exact value of BB(6) », knowing no exact notation will fit in our universe (or any conceivable larger one)?
Comment #174 July 11th, 2024 at 9:28 am
fred #172: I’m well aware of that. But almost no programming language (and none in common use) restricts itself to a minimal set of instructions needed to be Turing-complete.
Comment #175 July 11th, 2024 at 9:35 am
F3et #173: It wasn’t my example, it was Sipser’s. And I loved his audacity, in making students accept that the constant 0 and 1 functions are still computable, even if you chose between them using the most enormous or controversial question in human history.
Who says that the value of BB(6), whatever it is, can’t be succinctly expressed (or at least upper-bounded) using non-BB notations? After all, we have computable notations (like Ackermann) that make it easy to express even way bigger numbers than 10^^15…
Comment #176 July 11th, 2024 at 11:15 am
Scott #170: I propose that an alternative to Cantor’s approach is already thriving (has always been thriving), exemplified by the finite maths developed by Knuth, Petri, Dijkstra, Van Wijngaarden, Naur, and so many others. Although their methods differ in various respects, they share a common principle: the attempt to eschew actual infinities, undecidability and the like. This is not to say that all of these men rejected Cantorian maths (although some actually did). I use Cantorian maths in my lectures and work, so please don’t shoot me 🙂
Both supporters and critics of Cantorian maths are influenced by underlying ideologies.
(1) The fact that mainstream comp. sc. takes “computability to be absolute” is reminiscent of neo-Platonism. (It is not as absolute as we would like, cf. Stewart Shapiro 1982 and Ethan Brauer 2021.)
(2) Stating that my laptop is a universal TM is arguably even reminiscent of Idealism. (This is an observation from an engineer turned historian.)
The second item is like asserting that my newly manufactured die *is* a mathematically fair die. This resembles an extreme form of Platonism, if not Idealism. Some high school teachers introduce the nuance, though many others mistake theoretical concepts like the law of large numbers for the physical act of rolling a real die on a desk (and vice versa). Simply roll the die “many times,” and then you are “always allowed” to apply asymptotic mathematics without further ado. I don’t think so.
In various contexts, the distinction between maths and physics can be safely ignored (a purposeful conflation). However, in other situations, it is crucial to maintain the nuance. For instance, if a formal methods expert claims to have proven that my laptop is free of bugs, I will insist that s/he has proven this result on a mathematical model, not on the real thing. If that same person claims I cannot prove that my computer program will halt, I will argue that I am relying on an FSM abstraction of my smartphone, not a TM abstraction. (As a result, that professor will use his authority to belittle my industrial research “in the name of “science.” Quite something.)
I consider theoretical comp. sc. books to be full of Platonism (not that you per se disagree with me). Your example from Sipser is a good illustration of this.
Comment #177 July 11th, 2024 at 11:38 am
Scott #146: I 100% agree that if someone is asking questions out of desire to defend some position rather than get at the truth, then that person will not make much progress in learning. But if that person genuinely is puzzled why some idealization is made, then there exists a good *reasoned* response, other than, “Well, that’s how experts have decided to define this subject and look at all the success of this field.” The reasoned response exists, otherwise the idealization wouldn’t have been made by the experts in the first place! Now, I also understand that *sometimes* with a topic, a student needs to temporarily move forward and time needs to pass and later the student should return to their puzzlement. What can be massively confusing now might be obvious in two weeks. And also, the material might be temporarily out of the student’s reach because a conceptual foundation hasn’t been built properly. So the student needs to get a better foundation in a more basic class first. But if the student has the foundation to understand some material but at the end of the course he has basic questions about why certain idealizations or definitions have been made, then the course has failed him and he hasn’t learned.
I also completely understand that in our current educational system, a teacher usually doesn’t have the time to answer all of the questions that students might have. Teachers are required to cover far more material than is possible for most people to learn in depth. That’s why you have those myriad studies of undergraduate physics courses where after a semester of teaching, most of the students still can’t answer basic, conceptual physics questions. Of course not! The reason is their basic questions haven’t been answered in the first place, partly because of the rush to cover so much material and partly, because answering questions is hard and tedious and most teachers don’t like to do it. And students know that.
I think it’s difficult for brilliant people like yourself to understand how others struggle with concepts that aren’t connected to everyday life. It might be the case that our education system should only be for people who see the reasons for definitions and idealizations on their own and don’t need a lot of help from a teacher. My prior is that the people who are naturally brilliant are going to push the field forward and the people who struggle to conceptualize a subject probably won’t advance the frontier of knowledge anyways. But I think that brings us to this question: for most people, why those hundreds of hours spent in classrooms? The implication is that those hours are all wasted except on a few people, such as yourself, who will push a field forward. The obvious conclusion is that we have far, far, far too many people going to university. It’s an absolute waste of resources because 99% of the people aren’t learning anything. The 1 percenters such as yourself have the brain power to learn something in our system as currently constructed, because you can probably figure out most things on your own. For the rest of us, the time spent is almost a total waste because basic questions and issues of puzzlement aren’t answered. Your post, “The Zombie Misconception of Theoretical Computer Science”, elegantly proves my point.
Obligatory Father Guido Sarducci video: https://youtu.be/kO8x8eoU3L4
Comment #178 July 11th, 2024 at 11:45 am
Edgar Graham Daylight #176: Can you give me a link to show where any of those people rejected Cantorian set theory? The fact that they worked on CS and discrete math is neither here nor there — so do I! Indeed, many of the founders of CS (Church, Turing, von Neumann, …) also worked on Cantorian set theory and logic or came out of the community that did.
As for “Platonism” — I mean, it’s very hard to do math, even discrete math, without committing at least to the positive integers as things that existed and had definite properties before humans had any theories to talk about them! Even my colleagues who claim not to be Platonists become Platonists when they’re doing research. 😀
Comment #179 July 11th, 2024 at 12:07 pm
Travis Allison #177: The issues you’re raising are central and difficult ones that I’ve struggled with my entire career. I’ve spent a large portion of that career answering students’ questions, thinking of more and more ways to explain or justify the same concept until it finally clicks. And one of my greatest pleasures in life has been to see that happen, or get teaching evaluations that told me it happened.
Yes, while I’m not quite as extreme as my friend Bryan Caplan (author of The Case Against Education), I do worry that our current system pushes people to spend years of their lives “studying” “material” that most of them are never going to understand and will quickly lose the ability even to regurgitate. But then I also see how teaching could be done so much more effectively, how so many more people could understand the definition of computability or Bayes’ theorem or complex numbers or whatever than currently do, and it pains me to give up on them!
I suspect that the Internet imparts many “lessons” that don’t transfer to real-life classrooms. For example: how should we deal with someone who refuses to accept that 0.999… = 1? To a 10-year-old in a classroom I’d want to say: it’s great that you’re struggling with this! What a wonderful opportunity to talk about what it means for two numbers to be “equivalent,” and Zeno’s Paradox, and the concept of a limit, and one of the greatest triumphs in human thought!
It’s probably only on the Internet, and not in the classroom, that you regularly encounter the followup question: what if, after you’ve spent hours explaining all that, the person simply laughs and calls you an elitist conformist who lacks the common sense to see that 0.999… and 1 are obviously different? 😀
Comment #180 July 11th, 2024 at 12:10 pm
Scott #178:
Page 1 :: https://www.cs.utexas.edu/~EWD/ewd03xx/EWD372.PDF
https://www.cs.utexas.edu/~EWD/transcriptions/EWD12xx/EWD1227.html
More on Van Wijngaarden + Naur; e.g. p.133 in: https://www.lonelyscholar.com/turingtales
Oral histories with Knuth: http://www.lonelyscholar.com
Carl Petri: his PhD dissertation (1962; translated 1967)
Comment #181 July 11th, 2024 at 12:26 pm
Edgar Graham Daylight #176
“exemplified by the finite maths developed by Knuth, Petri, Dijkstra, Van Wijngaarden, Naur, and so many others. Although their methods differ in various respects, they share a common principle: the attempt to eschew actual infinities, undecidability and the like.”
About Knuth in particular, he worked on Surreal numbers (idea from Conway), and I don’t see any eschewing of infinities, but maybe I’m missing something.
https://en.wikipedia.org/wiki/Surreal_number
The book itself is entitled
“Surreal Numbers: How Two Ex-Students Turned On to Pure Mathematics and Found Total Happiness”
https://people.math.harvard.edu/~knill/teaching/mathe320_2015_fall/blog15/surreal1.pdf
Comment #182 July 11th, 2024 at 1:49 pm
F3et #173
Actually in this particular case it is possible to specify the exact number of steps in a reasonable amount of TeX. See https://www.sligocki.com/2022/06/21/bb-6-2-t15.html.
Also, there is no good reason to believe that the current known lower bound of BB(6) is the true value. It is almost certainly the case that BB(6) ⋧ 10↑↑15.
Comment #183 July 11th, 2024 at 3:12 pm
Nick Drodz #182
what’s interesting is that the notation/representation of the (current) lower bound number has to reflect how its generating algorithm actually works (I guess it’s obvious it has to be this way, otherwise we wouldn’t be able to represent it exactly?), and therefore the algorithm has to have some ‘obvious’ way to deconstruct it.
I see that “Collatz” and “Collatz-like” is mentioned again in that post, which goes back to my question as to whether all “winning” BB(N) machines are always following a Collatz-like structure, or it’s just pure luck with BB(5) and this BB(6) candidate (or it’s the case that anything that finishes always has a Collatz-like interpretation? That doesn’t sound correct to me)
Comment #184 July 11th, 2024 at 3:58 pm
Scott #175 :
Upper bound is almost surely easy, as the fast growing hierarchy gives way to denote integers much larger than the Conway arrow notation, Goodstein sequences, etc. But for exact values, there is no way to denote more than N distinct values in less than log log N symbols, so double arrow notation quickly get us out of the possibilities of any physical universe
Comment #185 July 11th, 2024 at 4:16 pm
F3et #184: I’m aware of all that.
For an upper bound on BB(6), I’m optimistic that we will have computable notations that easily express it—the main problem is just to prove that some upper bound is true!
Even for the exact value, though, we’ll just need the 6-state champion to have some behavior that lets us calculate its running time in a reasonably small closed-form formula. As Nick Drozd #182 pointed out to you, the current 6-state champion is like this.
Comment #186 July 11th, 2024 at 6:15 pm
XKCD recently published a answer to the first uncomputable integer https://xkcd.com/2956/ :
The first integer with undefined computability is ╤, wich lies on the lower number line about four stops before the end.
This really feels more a linguistic problem, where a common word “computer-able” has a very specific narrow definition that contradicts first intuition.
Comment #187 July 11th, 2024 at 7:05 pm
Scott #179. It’s wonderful to hear your joy in helping students truly understand. If we cloned you X million times, our pedagogical problems would be solved.
“I do worry that our current system pushes people to spend years of their lives “studying” “material” that most of them are never going to understand and will quickly lose the ability even to regurgitate. ” Amen.