The comments on this article are like a flytrap for people with exactly the kind of misconception the article is talking about.
If I ask you to write a program that returns false if 4 is an odd number and true if it's an even number, you would say that's trivially computable:
def is_four_even(): return 4 % 2 == 0
Of course there's an even _simpler_ function:
def is_four_even(): return true
The two are both valid ways of computing that function. Four is even, it has always been even, you don't need to check if it's even, you can just return true.
For all these complicated questions about that people are all getting wrapped up about the only difference is that we currently don't know how to write the first version of the function, and we don't know which of "return true" or "return false" is the correct version of the second form of the function, but _the second form surely exists_, which means that it is computable. Either P=NP or P!=NP, and that has been true or not true since the beginning of time, and _one_ of those two functions would have been correct to use from the beginning of time. It's computable, we just don't know which one to use right now.
As soon as someone proves the status of P?=NP, you can just pick one of the two ('return false' or 'return true') if someone asks you write the function. It also doesn't really matter if a statement is provable in theory or not. Whether or not it's possible to prove that P?=NP, it is either true or it's false and it has always been either true or false, and one of those two programs is correct.
This is a pretty philosophically extremist statement (relying on a hardcore version of Platonism) and with my handle I can’t just let it stand unchallenged. :)
I’m actually somewhat more sympathetic to excluded middle for P?=NP than for some other statements, so let’s start elsewhere. I don’t think it’s at all obvious that the continuum hypothesis is, and always has been, either true or false. We know it’s independent of ZFC, of course, and there are sensible “extra” axioms that would resolve it in opposite directions (e.g. V=L vs. MM). In order to believe that there’s a fact of the matter you need to posit a very well-populated Platonic realm, despite not needing that kind of philosophical commitment to do mathematics.
Well, maybe P?=NP is just simpler than CH. It probably is! But you can imagine a case where it isn’t; e.g. if there exists an algorithm for 3-SAT (call it Algorithm A) which can be proved to be asymptotically optimal, and which runs in O(n^10^100) time if !CH, and exponential time if CH. Then the P?=NP question would be equivalent to CH, and you should have the same beliefs about its truth value. If you’re like me, that means you’re skeptical that it has a well-defined truth value “for all time” at all.
It's the same essentially as a function that returns true if any two lines will eventually intersect. The correct answer depends on whether you're in curved space or not. That the correct answer depends on the domain or axioms doesn't make it non computable.
There's just no case where a constant function isn't computable in the technical sense.
Is this true for the BB function though?
What if there is a beaver that never halts or loops, and has behavior sufficiently complex, such that it's impossible to prove it will never halt.
Then for rules of that length, the second form doesn't exist.
A Turing machine with finite states must eventually either halt or loop. Those are the only options, because there are only finitely many configurations it can be in, and each configuration completely determines the next.
A "beaver" is defined to not loop. All "beavers" must halt, because otherwise they're just not considered for BB(n). All the challenge is in proving whether a given Turing machine does (or does not) halt, and therefore must not (or must) loop. Proving "halt" or "loop" proves the other one.
Yes, the function `busy_beaver_6() = 576125642131574254..." must exist.
There are infinitely many configurations if you consider the tape.
It is still true, of course, that every Turing machine either halts on a given input, or doesn't.
Yet something about that still seems extremely "loopy". Is there something that must stop increasing after a while? Kolmogorov complexity? Or is that begging the question, since that's basically measuring the smallest TM that can produce that output?
If you are including the tape, it's not true that there are finitely many states. If you're not, then "looping" as you've defined it is not excluded from the definition of the busy beaver problem, and does not imply that the machine never halts.
An infinite Turing tape can be in an identical state, however. The number of states don't have to be finite. If a Turing machine returns to an identical state, it will not halt. That's what we call looping.
An example of an identical state is 1 at indexes 3 and 5 of the tape, and 0 everywhere else.
Another example is the Brainfuck program `++[]`. This trivially returns repeatedly to a given finite state.
Here's an example of a bf program that never returns to an identical configuration, and also never halts. The corresponding TM would be excluded from consideration for the busy beaver number, despite never "looping" according to your definition.
+[+]
The Turing machine writes and reads from an infinite tape, and as such, the number of configurations (the machine's state + tape) is countably infinite.
Specifically, ZFC is consistent iff ZFC+“Y&A’s machine does halt” is consistent iff ZFC+“Y&A’s machine never halts” is consistent (a theorem in a fairly weak ambient metalogic). So you can take a stronger set theory that does prove the answer, it’s just that thus far we have no reason to prefer theories that answer yes to theories that answer no.
(You don’t have to accept excluded middle, and it can on occasion be useful not to[2], but pragmatically you’re going to have a lot of difficulties even with first-year calculus unless you do.)
[1] https://scottaaronson.blog/?p=2725
[2] https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016...
you might say, no, plenty of academics teach undergraduates, and undergraduates are super ignorant. but undergraduates generally don't care whether bb(123456789) is computable or not unless that's on the exam, and their incentives run strongly counter to arguing with the professor if they're unconvinced; the way they've learned to play the academic game is by producing the desired answers, because that's what gets good grades, not finding holes in professors' reasoning
so i think people like scott and sabine hossenfelder are doing profoundly important work, and the groundless controversies around them demonstrate not the error of their ways but the astounding degree to which the current academic system is failing to educate the public
I don't see how the second part of the sentence implies the first. The primary role of academics is generating new knowledge. Educating the ignorant is a public service that few are willing or able to do. Scott Aaronson deserves a lot of credit for dedicating so much energy to his blog, it does not mean that 99.99% of his peers are wrong in focusing on advancing the frontier of knowledge.
i won't go so far as to claim that this imposes an individual moral obligation on every academic—that would be a variety of consquentialism with many consequences i shrink from—but at least it would be good to figure out how to demarginalize what scott is doing