3 ms·

I'm going to try and explain this in a simple way: 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, yo

I'm going to try and explain this in a simple way: 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.

intuitionist 2y ago
> 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.
- empath75 2y ago
  In that case, either of "return false" or "return true" are valid computable functions depending on the domain you're operating in (with CH or without it). 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.
Aeium 2y ago
_the second form surely exists_ 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.
- School-Cotton 2y ago
  Whether it’s possible to prove it halts or not is irrelevant. It either does halt, or not. Whether a human can prove that a function has a particular value doesn’t change whether that function is computable in the technical sense being used here.
- mananaysiempre 2y ago
  If you’re using ZFC, there is (TFA mentions the state of the art is BB(745); Yedida and Aaronson’s original work on BB(8000)[1] is quite fun to read from a programmer’s point of view). But the second form still exists (if you accept excluded middle)—you just can’t prove which one it is! 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 https://scottaaronson.blog/?p=2725 [2] https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016-01556-4/S0273-0979-2016-01556-4.pdf https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016...
- feoren 2y ago
  > What if there is a beaver that never halts or loops 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.

intuitionist 2y ago

> 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.

empath75 2y ago
In that case, either of "return false" or "return true" are valid computable functions depending on the domain you're operating in (with CH or without it). 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.

Aeium 2y ago

_the second form surely exists_ 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.

School-Cotton 2y ago
Whether it’s possible to prove it halts or not is irrelevant. It either does halt, or not. Whether a human can prove that a function has a particular value doesn’t change whether that function is computable in the technical sense being used here.
mananaysiempre 2y ago
If you’re using ZFC, there is (TFA mentions the state of the art is BB(745); Yedida and Aaronson’s original work on BB(8000)[1] is quite fun to read from a programmer’s point of view). But the second form still exists (if you accept excluded middle)—you just can’t prove which one it is! 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 https://scottaaronson.blog/?p=2725 [2] https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016-01556-4/S0273-0979-2016-01556-4.pdf https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016...
feoren 2y ago
> What if there is a beaver that never halts or loops 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.