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?
Sure, I'll happily quibble! You're using excluded middle to assert that n is either 3 or 5, but you haven't justified that excluded middle holds for the proposition "God exists".
The comments on this article are like a flytrap for people with exactly the kind of misconception the article is talking about.
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.
_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.
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.
I disagree unless you state what you mean by "loop". If it's just "repeat a state" then any 6-state TM "loops" or halts after at most 6 turns... and many that "loop" will eventually halt.
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.
I don't understand what you're disagreeing with. "loop" has a well-understood meaning here: return to an identical state. Not a similar one, identical. Because if it does that once, being a deterministic automaton, it will do so an infinite number of times without halting.
In determining whether you've returned to an identical state, are you including the tape? Or just the machine states?
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.
If you are including the tape, it's not true that there are finitely many states.
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.
Yes, but the original claim was that non-halting TMs must loop because the number of configurations is finite. But that's not true.
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.
+[+]
You're right: my argument is flawed. I had thought TFA relied on that argument, but the machine that writes 1 and moves right forever is a counterexample.
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?
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.
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.
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.
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
[2] https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016...
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.
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.
There exists a program that answers the following question: "If 99.99% of academics are rarely misunderstood, but one single blog consistently sparks discussions, should that blog reconsider its presentation style?"
the other 99.99% of academics should reconsider their presentation style; the reason their papers don't spark such arguments is that they've given up on educating the ignorant the way scott does
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
the other 99.99% of academics should reconsider their presentation style; the reason their papers don't spark such arguments is that they've given up on educating the ignorant the way scott does
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.
it's a public service that nobody else is able to do, and if nobody does it, the result is catastrophe: legislating the value of pi, creationism in schools, prohibitions on glassware and borax and teflon, lynchings for witchcraft, acid attacks on girls for attending school, the ransomware pandemic, boko haram, the cambodian mass executions for wearing glasses or speaking french
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
"Yes, the blog should consider reviewing its presentation style." from you know who.
He's popularizing interesting but complicated maths. That's always gonna attract people who think they understand it, but don't.
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.”
That's not a program, it's two programs. Likewise for the theological "function" at the start. If it were to determine whether God exists it would need inputs on which to base that determination. Instead, two functions are presented along with a theological rule to choose between the two. The properties of the functions have nothing to do with the theological question.
I get that that's the point of the article, and that the quoted homework question correctly refers to two functions. I just felt that it wasn't particularly clearly spelled out and that the article seemed to blur the distinction between the functions and the choices between functions, which would probably further confuse those suffering from the misconception he describes (while heaping scorn upon them).
Edit: And this seems to really muddy the waters:
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.
Regardless of Sipser's motivations the question doesn't say anything about the difference between individual values and functions/sequences. What it reveals is the difference between a well defined mathematical function and a choice one might make or imagine between various such functions (the criteria for which may or may not be well defined).
I could replace the question about God with one about whether some other function (which we haven't yet determined the computability of) is computable and it would still be the case that "the function we have defined is computable". (Scare quotes because that's actually a category error and the correct observation is that "both functions we have defined are computable". Hmm, well given the computability of the third function is well defined, though unknown, I suppose in this case we actually have defined a single unknown function, but the point about the difference between the choice and the functions stands.)
He’s saying that because those two programs exist, there exists a program that correctly answers the P vs NP question. We don’t know which of the two it is. But equally, 50 years ago we would not have known whether to choose the program “Fermat’s last theorem is false” or “Fermat’s last theorem is true”. Still, the second program has always existed and has always printed the correct answer (at least if you sub in the theorem in pre-Fermat times).
But "we don't know which of the two it is" handwaves away that "answering P vs NP" means precisely coming up with the proof!
Those constant functions aren't proofs, the proof is in coming up with a series of computable steps to reduce a model of P=NP into that constant function. That is, the proof is the computation itself, not just the constant value.
What the author did describe is a function that we can only evaluate when we already have an answer for P = NP, not a function that computes it.
Proving P vs. NP and answering the question correctly are two different problems.
Computability is defined in terms of functions that map the input to yes/no. A function is computable if there exists a representation that computes it correctly for any input and eventually terminates. Every yes/no question where the answer does not depend on the input is by definition computable. The corresponding function is either the one that maps every input to "yes" or the one that maps every input to "no". We may not know which one, but that's irrelevant.
In some sense, computability is similar to probability. Your intuition is wrong, and following it only leads to further confusion. But if you unlearn it and rebuild it from basic principles, things become much clearer.
Nit, decision problems are one type of computable problems, but you have other types like function problems, optimization problems, etc.
NP, by definition involves decision problems, but many NP-Hard problems are optimization problems.
More specifically NP is the set of decision problems solvable by a NTM in poly time with the following conditions:
1) If the answer is "yes," at least one computation path accepts. 2) If the answer is "no," all computation paths reject
Equivalently is is the set of decision problems verifiable by a TM in poly time.
Modern programming tends to only care about #1, and structured programming paradigm helps with that.
People not moving past NP in complexity theory is the real problem here. I also blame using the 'trys all answers at once' NTM intuition vs the max lucky guesser which makes it less silly.
But didactic half truths do really hurt. Entscheidungsproblem is better for teaching people in my experience.
Correct, the author did not describe a program that computes whether P = NP. He merely proved that such a program exists, by describing two programs, and showing that one of them must be the one that computes whether P = NP (we just don't know which one, but we at least know that it exists).
Part of the point is that computability is different from knowing how to write a program that actually computes the desired value. We can say a program exists to print whether P=NP (whether it is computable) without knowing how to come up with a concrete implementation of that program.
I think the intuition people want to apply here is that ‘is P=NP’ feels like an instance of a class of questions - ‘is P=x’, and if that is computable, then it implies we can attack P=NP by coming up with a way to compute it and feeding in NP.
But I think the issue there is the assumption that it even makes sense to define a function over ‘classes of questions’.
... handwaves away that ..
These kind of handwaveing are quite common in math. For example, Axiom of Choice assume there exists a choice function. It does not specify how.
But "we don't know which of the two it is" handwaves away that "answering P vs NP" means precisely coming up with the proof!
Of course it's a not a proof of "P=NP", but no one is asking for it.
What the author did describe is a function that we can only evaluate when we already have an answer for P = NP, not a function that computes it.
Yes. This function is still computable though. The question of computability doesn't depend on humans being able to evaluate this function on a given day in history.
The whole point is simply that the notion of computability is not related to coming up with proofs or to any mechanical process for arriving at a result based on a set of axioms. "Computable" and "Provable in ZFC (or whatever)" are just two different things and pertain to different mathematical objects. Functions are computable (or not). Theorems are provable (or not).
isn't it actually one program? Imagine the implementation using an oracle.
You being a clever programmer somehow know of a very powerful oracle, lets call the oracle Pauli. You're program works as follows:
func main():
response = write_pauli_asking_if_p_is_np() //synchronous, waits for response
if response is true:
print(“P=NP.”)
else:
print(“P≠NP.”)To me there's no other way to interpret it, really, except as one function. The if-then part of it is part of the function definition.
The example is genuinely confusing to me because of the igtheism problem: the idea that the question of whether God exists is a poorly posed one, because God is undefinable. It's like dividing by zero or a type error or something. This was Bertrand Russell's perspective, for example.
Maybe the intent of the example is "here is a function whose inputs are unknown" but for me it was more like "here is a function whose outputs depend on an undefinable input."
The second example didn't seem much better for the same reason. Knowing that the output is prime regardless of the input — a logical conclusion from the "meta evaluation" of the function — doesn't seem to me to be the same as asking whether the function is computable.
To me it's like having the function depend on a contingency sort of like "if the color blue tastes like cheese, then..." It doesn't make sense.
If the example was meant to incorporate an unknown state (as opposed to an undefinable one), it would have been better off with a random unseen event or something, like a person flipping a coin in a different room. Or a particle decay in a box, but then that leads to quantum issues maybe which leads to the same sort of problem possibly.
> The if-then part of it is part of the function definition.
No, it isn't. The if-then part of the question is about which of two trivial functions the label "f" refers to. It has nothing to do with the functions themselves or their computability. That, from what I can gather, is supposed to be the point of the question, but I don't think the question gets that point across very well.
nit:
if response is true:
i've always wondered how people know when to stop (which, i guess, is relevant to the subject matter).
e.g. why is your next step not
if (response is true) is true:
I would say it's because this is pseudo code and it is a lot clearer that way.
Depending on language
if response:
could mean "response" is true,1,not empty, X....
I don't think that's what he was referring to. Apart from not being "fast", it's not a program in the sense being discussed here, given the article is about computability. It's an oracle turing machine rather than a plain turing machine, and oracle turing machines can trivially side step computability questions by having the oracle evaluate the noncomputable function.
(This is of course not relevant to the oracle you suggest as that doesn't evaluate a noncomputable function, but it's relevant to what sort of "program" Aaronson is talking about here.)
That's not a program, it's two programs
Yes, and one of them is "a fast program that correctly answers the P vs. NP question". We don't know which.
I could replace the question about God with one about whether some other function
Saint Anselm's Ontological Theory of Computation. "First.. imagine the most perfect function that could possibly exist.."
It is one program. If P=NP then the body of the program consists of "print(P=NP)". And otherwise it consists of "print(P!=NP)". [1]
Similarly for every hash function there exists a program that outputs a hash collision in well under a second. Just hardcore any collision and print it to the screen. [2]
[1] If you want to be pedantic then there's a third option that prints some more complicated statement about the relationship between standard axioms and P?=NP.
[2] Please don't ruin my short argument by pointing out that someone can create a hash function with output size in the petabytes range :)
I don’t get the god thing. Why is f computable, just because we know the possible outputs? By that logic the halting problem is computable because h(f) is either 1 or 0.
AN interesting and non rigorous way to think of it is can the compiler optimize away the non compute-able part. So this:
if (God does exist)
return isPrime(3)
else
return isPrime(5)
I like this explanation, but how would you apply that logic to
If (god does exist)
Return true
Else
Return FalseI guess I misread the first part of the article while skimming. I think the key is this paragraph
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.
I saw it elsewhere in the comments but I think computability as defined in Computer Science and used by the author is more strict a definition than you or I are/were thinking, and that is really the main point of the article. People confuse computability with "can it be computed". Missing values (such as knowledge of God's existence or null values) mean you can not computer something but that is a different thing.
It would be something like this:
if (God does exist)
return isComputable(() => true)
else
return isComputable(() => false)
You do know that the code above will always return "true", without having to know whether god exists.
h(f) is either 1 or 0
Depending on f. The God-existence function doesn't depend on its input.
You can also say, for example, let f: R->R be defined by f(x) = 1 if I'm a man, and f(x) = 2 if I'm a woman (or non-binary or anything else). Is the derivative of f zero? You don't know what the value is, but you can answer this question with "yes".
So it’s just:
In universe 1, the function looks like `return True` and in universe 2, it is `return False`?
And it’s computable because nothing is really computed?
Yes, that's right.
> Why is f computable
Because f is either the constant 1 function or the constant 0 function, and both are computable. The fact that we don't know for sure which of those two functions the label "f" refers to doesn't matter if all we are asking is whether the function the label "f" refers to is computable. We know it is because both of the possible referents are computable.
Double Entendre one of my favorite poetic devices.
The halting problem for any given program is either true or false, so a program that prints true or a program that prints false is a valid function that produces an answer for that function. You don't know _which_ one is the correct function, but it exists. The thing that's not computable is a function that produces an answer given any arbitrary program as input.
It's the difference between:
does_program_x_halt():
return true
does_program_halt(x):
if x halts:
return true
else:
return false
I think an important clarification to make is whether or not we currently know how to write a function isn't relevant to whether it's computable or not.
Any given program P either terminates or not. So yes, for any fixed P the function that h_p() that returns 0 or 1 is computable. Same is true for a function h_N(P) that accepts only a finite set of possible inputs -- it's a switch case.
However a generic function h(P) that can accept any program P is not computable and the switch-case approach won't work.
Long story short, the question of computability only considers whether an algorithm exists or not, not whether humans know it or not -- that is irrelevant to the question.
Consider the following example from wikipedia [1]:
The following examples illustrate that a function may be computable though it is not known which algorithm computes it.
The function f such that f(n) = 1 if there is a sequence of at least n consecutive fives in the decimal expansion of π, and f(n) = 0 otherwise, is computable. (The function f is either the constant 1 function, which is computable, or else there is a k such that f(n) = 1 if n < k and f(n) = 0 if n ≥ k. Every such function is computable. It is not known whether there are arbitrarily long runs of fives in the decimal expansion of π, so we don't know which of those functions is f. Nevertheless, we know that the function f must be computable.)
Each finite segment of an uncomputable sequence of natural numbers (such as the Busy Beaver function Σ) is computable. E.g., for each natural number n, there exists an algorithm that computes the finite sequence Σ(0), Σ(1), Σ(2), ..., Σ(n) — in contrast to the fact that there is no algorithm that computes the entire Σ-sequence, i.e. Σ(n) for all n. Thus, "Print 0, 1, 4, 6, 13" is a trivial algorithm to compute Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); similarly, for any given value of n, such a trivial algorithm exists (even though it may never be known or produced by anyone) to compute Σ(0), Σ(1), Σ(2), ..., Σ(n).
Let n equal 3 if God exists, or 5 if God does not exist. Is n prime?
[Not yet finished the article]
Author says the answer is True. I say the question is malformed, and cannot be answered.
Why can't it be answered? It seems trivial to answer.
The question is malformed because it contains a term that cannot be evaluated.
Even if evaluating that would make no difference?
That's the problem with side effects: you don't know if they make a difference until you evaluate them. And "God" is about the biggest imaginable side effect.
Well, the compiler says undefined behavior and optimizes it away :D
"God" has some unique properties. One of those might be that God neither exists nor doesn't exist. If God has this property of 'neitherism', then the value of n is undefined. Neitherism has been attributed to many religious entities.
To answer a question, you first have to be able to parse the question.
I see the question this way:
fn is_n_prime_whether_or_not_God_exists()
if (is_prime(3) && is_prime(5)) { // early return
return true;
} else {
return three_if_God_exists_five_otherwise();
}
}Isn't this the law of excluded middle (rejected by intuitionists and constructivists)?
Let n equal 3 if LEM is valid & sound, or 5 if LEM isn't valid & sound. Is n prime?
(A and X) or (A and (not X))
simplifies to A in classic logic.
I guess there's an ambiguity whether "God exists" is a propositional variable.
I guess you could reformulate the intent of the problem as:
Let P be an arbitrary program and let n be equal to 3 if P terminates, or 5 if not.
Is it still malformed? Is so, then how about
Let n be equal to 3 Goldbach's conjecture is true, or 5 if not.
It can be sort of unintuitive how the concept of computability necessarily involves infinity.
For example: does there exist an algorithm that computes the Kolmogorov complexity, K(s), of string s for arbitrary s? It is well-known that the answer is "no" — there is no Turing machine that takes as input a string of arbitrary length and computes K(s). The proof is quite brief and involves the halting problem.
But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length < n? The answer is yes! And there exists such an algorithm for any value of n.
How is that possible? Think about it for a second, because the answer is going to disappoint you: simply create a Turing machine that consists of a giant lookup table for all 2^n possible strings that prints the value of K(s) for each one.
But wait, that's cheating! Maybe so, but any specific implementation of the algorithm has a finite description. And by definition, K(s) is also finite for all s. While it's true that I haven't provided any particular method for determining the value of K(s) for all 2^n strings in order to actually create the lookup table, that doesn't matter. Such an algorithm nevertheless exists, regardless of whether you can find it or prove that it does what you want it to.
So in a sense, finite questions about a finite number of things are sort of uninteresting from the perspective of computability, because you can always write a program that just prints the answer for all of those things (how quickly it does this is another matter). But when you extend the question to an infinite number of things, computability becomes much more interesting, because you don't know whether something finite can provide answers to questions about an infinite number of things.
This description makes it sounds like large areas of computer science are just goofy, meaningless, games.
But what's really happening is that "infinity" is standing in for "approximate, eventual, steady state behavior for sufficiently large N, larger than any specific one-off gimmick you might think of".
In the real world, though, those gimmicks are important, and the constants and low-order terms ignored in a Big-O comparison are important to real world performance.
There is constant tension between "big enough problem that the contant factors don't matter", and "small enough problem that it conforms to the (often implicit) of what 'constant' means (example: 32bit ints masquerading as integers)"
This description makes it sounds like large areas of computer science are just goofy, meaningless, games.
Oh no, not at all. My point is that the concept of infinity is in a sense necessary for the mathematics involved in developing algorithms to solve problems. We are performing induction to "predict" the behavior of an infinite number of Turing machines without actually running them. We can't just iterate through all possible programs, so we have to use patterns that apply in a consistent way to all possible problem instances to narrow down the search space.
approximate, eventual, steady state behavior for sufficiently large N, larger than any specific one-off gimmick you might think of
I know this is how computational complexity theory is considered from the perspective of many software engineers, but my point is a bit more fundamental. Computational complexity theory ultimately isn't concerned about any one particular problem and how to solve it quickly for practical applications—the goal is to understand what is and isn't possible with computation overall and with what resources (time, space). Why solve one problem when you can solve all of them?
But to do that requires really understanding the mathematical structures behind computation itself. If you're a formalist, instead of thinking of infinity as "the limit of large n", you think of it as a concept in a formal system that involves manipulating symbols according to a set of axioms and inference rules. You can use whatever intuitive human-scale analogies you prefer when thinking about large cardinal axioms or the continuum hypothesis, but at the end of the day, all that matters in terms of computability and computational complexity is how exploring the space of proofs derivable from these formal systems leads to a better understanding about the behavior of Turing machines (and thus the nature and fundamental limits of computation).
s/software engineer/constructivist/
Human-scale analogies are not tools for understanding formal systems. Formal systems are analogies for understanding human-scale systems :-)
Please excuse me if I prefer my Theory of Computation to be a theory of computation.
This description makes it sounds like large areas of computer science are just goofy, meaningless, games.
Well, only computability theory, not complexity theory, which you mention in the rest of your post.
Reminds me of the possible excess power of P/Poly versus P. Also does anybody remember the general name for circuit complexity classes where the circuit itself has to be written out by a simple Turing machine (I thought there was one but it isn't on the tip of my tong).
Yeah, the word is "uniform", e.g. a uniform family of circuits is one where there is a Turing machine where, for each n, it outputs the circuit for inputs of size n.
Similar to how all real-world computers have a finite number of states and are thus not Turing machines, but rather finite state machines.
Argh don't say that, someone might question funding CS theory grant proposals.
But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length < n? The answer is yes! And there exists such an algorithm for any value of n.
of course - n is by definition a finite number!
and in fact at infinity, all finite numbers are quite small, actually. A mile might as well be a millimeter, from your chair at the end of the universe.
And your scenario is basically just "hilbert's infinite hotel, on a computer" - we can of course add another program simply by moving all the existing programs 1 spot over... and it remains the exact same size of table needed to compute it!
I would actually generalize this and just say that most people have poor intuition of how infinities (alephs, etc) and transfinite mathematics work in general. it's not a common subject, it's not a subject with everyday relevance, and it's deeply steeped in the emergent properties of mathematics and category/set theory. Like not only are infinities bigger than any finite number, but some infinities can nevertheless be bigger than other infinities etc - these are not things that are immediately obvious to the 3rd-grade concept of "infinity" that most people stop at.
the much more interesting question would be if there exists an n < infinity such that the algorithm can be computed, and of course the answer is no (darn, there goes my turing prize).
a program that just prints the answer for all of those things
Everything can be textualized, but making a complete interpreter for it requires understanding what intelligence really is.
Isn't saying BB(6) is computable the same as assuming that it is an integer?
I thought this was not necessarily true.
For example, one beaver might halt after some integer number of steps. This would be the potentially very large integer the author is referring to. Another might go into an infinite loop, and clearly never halt.
My understanding of the where incomputability entered the discussion is the third possibility, that a beaver might have complex behavior that neither ever halts or ever loops.
The author touches on answering this, drawing the distinction that a specific answer might not be provable. But I'm not sure I understand.
How would the answer for a specific integer be computable if it's impossible to determine what the value for the function of is for that integer?
No, the definition of the busy beaver problem excludes any program that never halts, regardless of how complex its behavior is.
How would the answer for a specific integer be computable if it's impossible to determine what the value for the function of is for that integer?
Can you say precisely what you mean by “computable”? I suspect you’re using an intuitive definition that’s different from the author’s formal definition.
So, one thing that we know from Godel is that there are true statements that cannot be proven.
What if a similar proof is made for a Beaver? That a specific beaver is constructed such that
1: It probably never halts 2: Proving that it never halts is a paradox
Something like that. If assignment of BB number for BB of that size depends on that proof, then the BB value doesn't exist.
And what else would it depend on? How could a smaller number be selected when larger potential numbers cannot be ruled out?
What if a similar proof is made for a Beaver?
Then we will never be able to find the Nth beaver number for the corresponding N.
That doesn’t mean it is undefined or uncomputable. It actually has nothing to do with it. There is a computer program that prints out the number of hairs on my head. Doesn’t matter that you will never know how to write that program.
Again, uncomputable is being used in a technical sense here which is why I asked you what definition of “computable” you’re using.
“Probably doesn’t halt” is ill defined, it either halts or it doesn’t. In either case, computability of that number is completely separate from whether we can prove that number is BB(N) or decide whether a given beaver halts. Additionally, the way the busy beaver function is defined ensures it has a defined integer output. Computability is just our ability to construct a machine which would print out that number. We can clearly do that for any integer
Every Turing machine execution either halts, or does not halt. There are no intermediate possibilities. Some non-halting is easier to prove than others, but it's all still non-halting.
Yes, this is clearly true. Pardon the hasty first reading and deleted comment please.
It doesn't address what I am claiming though.
The busy beaver is not defined entirely by halting vs not-halting.
Looping beavers are excluded as well.
The middle ground I am claiming is that there is a middle ground between non-halting and provably non-halting.
I'm claiming there could be a non-halting Beaver that is impossible to prove, which would mean there is no answer for the BB function.
The busy beaver is not defined entirely by halting vs not-halting.
Looping beavers are excluded as well.
Looping beavers do not halt.
there is a middle ground between non-halting and provably non-halting
Yes, there are turing machines that encode mathematical theorems which are independent of ZFC, meaning they cannot be proven to halt or not to halt. The state-of-the-art is BB(748), which is known to be independent [0].
There are also much smaller known turing machines which encode classically difficult math problems, like the Goldbach conjecture [1]. This means that the value of BB(27) cannot be proven until the Goldbach conjecture is proven or disproven, as until that is done, we will always have something like "BB(27) is N unless the Goldbach conjecture is false".
However, our inability to prove these things does not change the fact that they have specific values. To stick with the BB(27) example, say that it seems we've narrowed it down to some huge number A, or a number dependent on the first number for which Goldbach does not hold. Call that second number B. We may be unable to find the value of B (doing so would disprove Goldbach), but it is still a specific number. There still exists a concrete value for BB(27)--it's A if Goldbach is true, and it's B is Goldbach is false.
[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
[1] https://gist.github.com/anonymous/a64213f391339236c2fe31f874... This 27-state machine halts when it finds a counterexample to the Goldbach conjecture.
Busy beavers are the machines in some size class which run the longest, then halt. They may be alternatively defined as the ones which produce the most output, then halt. Machines which obviously loop are excluded, and so are machines that non-obviously loop - for example ones that loop until they prove the Riemann hypothesis are excluded if the Riemann hypothesis is false and the proof system is consistent.
To be frank, this is an issue where there's an abuse of terminology going on, although the people asking the question probably don't realize there's an abuse of terminology.
"Is X computable?" is asking if there is a program that is capable of printing X out. For any integer, the answer to this question is trivially yes.
But when people are asking "Is BB(6) computable?", that's not really what they're intending to ask. What they're trying to ask is "is it possible for us to figure out what the value of BB(6) is?" In a more precise sense, the question is "Can we prove {BB(6) = x} is a true statement for some value of x?"
To some degree, I think Scott is being somewhat specious here. The question may be somewhat malformed as written, but it's also pretty clear to an expert what the question meant to ask, and--especially when you're targeting a more lay audience--insisting on giving the trivial answer to the clearly unintended question isn't likely to help the situation much.
For the purpose of the busy beaver problem, your second and third cases are equivalent- it’s a beaver that does not halt. Therefore neither of them are BB(6). BB(6) is tautologically an integer
What about this one:
f(n) = { 0, if no Turing machine computes the halting problem
H(n), if there exists a Turing machine, H, that computes the halting problem
}
It would seem the definitions are also fine for the above contrived example. edit: I'm not sure if n needs to encode a tuple (P, i) for some program P on input i and so forth.
That definition is fine (given that we know that no Turing machine computes the halting problem). It's equivalent to f(n) = 0.
Hm, but the definition is not fine if we didn't already know the status of the halting problem?
In that scenario I think the definition itself is still fine, technically. It's just that we wouldn't know what value the function had. It would be a bit like defining f(n) = n + the number of hairs Julius Caesar had when he died. There's nothing inherently wrong with the definition. You just can't do much with it.
It's just that we wouldn't know what value the function had.
I think there should be a word for that...
I don't think so. It's a pretty uninteresting property of a function whether or not a particular person happens to know its value for a given input. It does not entail that the function is not computable, if that's what you're suggesting.
To tie this back to TFA, even before we knew that the Halting problem was uncomputable, we could have defined
f(n) = { 1 if there is a Turing machine with at most n states that solves the Halting problem;
0 otherwise }
g_k(n) = { 1 if n >= k;
0 if n < k },
> What about this one
This is not the kind of thing Aaronson is actually asking about. He's not asking about a function f that outputs 1 if God exists or 0 if God doesn't exist. He's asking about a label f that refers to the function f1 (that just outputs 1) if God exists or the function f0 (that just outputs 0) if God doesn't exist. To me the question is not about computability at all, it's about labels.
He's not asking about a function f that outputs 1 if God exists or 0 if God doesn't exist.
Because that’s not a function in the mathematical sense. The output of a mathematical function can only depend on its inputs, and the function in question is not given any inputs, hence it’s necessarily a constant function, and constant functions are trivially computable.
> the function in question is not given any inputs
As the problem was posed, the function does take an input; it's defined as a function from {0, 1} to {0, 1}. However, as I pointed out in another comment upthread, the function makes no use of its input so it could just as well be defined with no inputs. (Indeed, even if you read the question as asking about a function f that outputs 1 if God exists or 0 if God doesn't exist, it doesn't seem like whether or not God exists is supposed to be an input.)
That Sipser question is just sophistry.
A function F that calculation 1 if god exists, otherwise 0 is not computable.
A function definition F that binds F to the 1 function if god exists, or else binds the symbol F to the 0 function if god does not exist, if it can be processed, results in a function binding that contains a computable function.
However, the definition cannot be processed computationally, because of the decision that it requires. Someone arbitrarily resolves it based on their religious beliefs.
The religious beliefs were pushed into the definition time, leaving whatever function is decided on computable.
Problem is, in math, there is no definition time versus run time. There is no difference between:
if (god exists)
let F(x) = 1
else
let F(x) = 0
let F(x) = if (god exists) 1 else 0
That only makes sense if we specify that the paradigm we are in is a programming language with definition times and run times, which seems out of place in a book about theory, let alone if it is just assumed as understood.
This is explicitly expounded upon in the original:
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.
OK, so he has a concept of a time when the program is written and so on. Decisions about how the program is written, or what is to be written, can involve non-computable metaphysical questions.
Not exactly. There's no "compile time" or whatever. The point is that the computational complexity characterizes the difficulty of mapping an input to an output. Sorting a list can be done with lots of different algorithms; the obvious ones are O(n^2). But there exist O(n log n) algorithms, so the complexity of sorting is O(n log n) irrespective of whatever implementation you might imagine. That O(n log n) is true now and for all time.
computational complexity characterizes the difficulty of mapping an input to an output
The question revolves around computability: can the input be mapped to an output; does the calculation terminate and the output emerge.
> This is explicitly expounded upon in the original
Yes, it is, but you can have functions that output other functions, and the question of computability applies to those functions as well. Sure, the constant functions are trivially computable; but one can also ask about a function that outputs one or the other of those constant functions depending on whether God exists, or whether the halting problem is solvable, or whether the Riemann hypothesis is true, etc., etc., etc. And in a post that is supposed to be about computability, saying "Gotcha! Misconception!" when people start talking about those kinds of functions instead of the trivially computable constant functions explicitly mentioned in the question does not seem to me to be a good strategy. As I posted in response to Aaronson in the comments there, before concluding 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 what question you were asking.
Computable doesn’t mean it’s easy to write down the implementation.
We can't start to talk about a function being computable until we have pinned down what it is; which usually means written it down.
I upvoted this post because it correctly describes an issue that I saw as well: the question isn't really about computability at all, it's about a label--at least, that's the question that Sipser (and Aaronson) intended to ask. But many readers (including me when I first read the question), seeing that the topic is supposedly computability and recognizing that the computability of the constant functions mentioned in the question is trivial, are going to consider the issue of computability of how the referent of the label is assigned, which is actually a more interesting computability question. Then, when the reader does this, Sipser and Aaronson say they're confusing religious beliefs with math.
Extremely strange reasoning from Aaronson. He goes from the question "How hard is it to solve P?=NP" to a vague existence claim of a program that cannot be concretely written, unless it takes "P==NP" and "P!=NP" as inputs, which would be a tautology.
This claimed program does not answer the above question at all. His students are correct, he is wrong.
You have misunderstood the article. The question being discussed was not "How hard is it to solve P?=NP", it was "Is P?=NP itself NP-hard", which is just an invalid question.
Sounds like the same question to me, for sure the students intended it that way. Many hard problems feel like you need an internal mental SAT solver to arrive at the solution.
Anyway, even if it were an invalid question, his answer still does not make any sense.
Those are definitely not the same question, NP-hardness has a precise meaning while "hard to solve" is a subjective judgement
The answer is trying to show the absurdity of the question. It's like asking for the time complexity of factoring 120. If there is no input to the algorithm, the answer is always trivial.
The exact wording (as of now, I do not know if he edits) is: "Could the P versus NP question itself be NP-hard, and therefore impossible to solve?"
That clearly implies solving. Aaronson is pretty sloppy with his own definitions and yet criticizes his students.
An unambiguous presentation would be:
1) Contrary to usual language use, we define "answer P?=NP" as "print 'yes' or 'no' or 'undecidable'".
2) By "program" we do not mean a single program, but three separate programs that print "yes", "no", or "undecidable".
3) We claim the existence of the program, not that it will ever be possible to know which of the three programs is correct.
By "program" we do not mean a single program, but three separate programs that print "yes", "no", or "undecidable".
You can think of it not as he is describing three separate programs, but giving three separate possible descriptions of one program and asserting that one of them is indeed the correct description.
Nitpicking, but I’d say that it’s a valid question with a trivial answer. A problem is just a set of question/answer pairs. “P?=NP” is just a decision problem with a single instance, and all decision problems with finite instances are decidable in constant time.
Consider this rephrasing of the question: “Let X be an NP-complete problem. Can X be solved in polynomial time?” This is a problem with an infinite number of instances, all of which reduce to “P?=NP”, so we know that this problem can be decided in constant time.
No, he's correct.
vague existence claim of a program that cannot be concretely written
It can be concretely written. It's either "return True" or "return False". As of today we don't know which one of the two is this. However our lack of knowledge is not relevant to the question if it's computable or not. Definition of computability doesn't rely on it.
unless it takes "P==NP" and "P!=NP" as inputs, which would be a tautology.
It doesn't take any inputs at all since none are necessary. It's a constant function. The question of computability isn't relevant for constant functions or for functions with a finite set of possible inputs -- they are computable as switch-case on all possible inputs.
The problem only appears with functions that have an infinite set of possible inputs where the switch-case approach won't work. You need an _algorithm_ to convert inputs to outputs and sometimes this algorithm just can't exists, regardless of how far we've got in proving truthfulness of various mathematical statements.
I think the problem with the wording is that it requires modal logic:
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 precise question is would f be computable (i.e. exists a Turing machine M st. f(x) = M(x) everywhere).
Would f be computable? Yes, because in either world there is a trivial TM, M = 1_M or M = 0_M. In contrast, the originally worded question "Is f computable" is a modally invalid question, analogous to the Sleeping Beauty or Red Envelope paradoxes. It's like, grammatically incorrect.
Another way to look at this is the dependency on God or some potentially real fact is more like a compiler directive or pragma whose parameters get filled in later but prior to use, so the question when asked correctly is just about unpacking the strict definitions of function and computable, both of which are explicitly defined in Sipser.
My reaction was somewhat similar, and I posted along those lines in the comments to Aaronson's post. As I said there, the question is not about a function f that could call the constant 1 function or the constant 0 function depending on whether God exists. The question is about a label f whose referent will be either the constant 1 function or the constant 0 function, we just don't know which unless we can figure out whether or not God exists. To me the question isn't actually about computability at all (the computability of both of the constant functions is trivial), it's about labels.
The question is about computability, in the sense it's asking to recognize the possibility of an unknown (trivial) computable function.
The "God stuff" is an distraction, with modal-logic ambiguities as another commenter wrote.
I just wrote a regular expression (a real one, not PCRE), and then deleted it, and dissolved my computer in acid. It is completely impossible to ever know what I wrote. Was that function computable?
Then I got another computer and wrote a program in a Turing Complete language, and deleted and dissolved that computer in acid. Was that program computable?
In contrast, the originally worded question "Is f computable" is a modally invalid question, analogous to the Sleeping Beauty or Red Envelope paradoxes. It's like, grammatically incorrect.
I don't think these paradoxes are relevant here. They only highlight a fact that application of the pure mathematical notion of probability to the actual reality is sometimes a non-trivial process. It's not a surprise, if you think of it the fact that the probability theory works _at all_ when applied to reality is extremely puzzling and has been a subject of various scientific and philosophical inquiries (see "probability interpretations").
Now the resolution you propose ("would" f be) doesn't seem to resolve anything. The purpose of "god" question is to force the reader to abstract away from a particular P-NP problem and understand that the whole concept of computability is useless for constant functions. So what you suggest is helpful only if you could also apply it to the original P-NP question, which I don't see so far. How the modalities approach come into play here, for a well-defined mathematical question?
You are further demonstrating how the cloudy semantics of the question and of casual semi-mathematical English language makes the problem harder than it needs to be.
This is a huge problem in probability theory, as you allude to. Experts often forget how their preferred mathematical models drift away from lay language, and say things casually that don't really mean what they say.
Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist.
A slightly longer way to write this that I think would cause fewer parse errors is
Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or let f:{0,1}*→{0,1} be the constant 0 function if God does not exist.
I find the time-dependent version much more interesting:
Let G:t∈ℝ⁺->{0,1} be the 1 if God exists at time t and 0 otherwise.
EDIT: And of course this starts getting even more interesting when you analyze G in a non-inertial reference frame.
I think the point is that whatever predicate you fill in for "god", the implication is strictly speaking true in classical first-order logic (and probably many other logical systems too). The pragma analogy is a good one.
Whether there exists such a predicate that conforms to your conception of God or not is a separate (non-mathematical) issue.
I think it's a bit like the surprise people show when they learn that in classical logic a false statement implies everything. Mathematics has strict formal rules, and it's important to leave aside your preconceptions of the semantics of various words like "implies" and "if" when engaging in it.
Could the P versus NP question itself be NP-hard, and therefore impossible to solve?
Is there a way to formulate or rephrase this such that we could effectively ask this question? I'm thinking like some way of formally encoding the question (does P=NP?) that could be plugged into a turing machine which then computes the answer.
I think "effectively ask this question" is quite ambiguous here. The original question implying NP-hard problems are "impossible to solve", which already makes no sense.
Pulling intent out of a invalid statement is difficult but I think the intent is something like
Could the P versus NP question itself be [mathy-difficult in a way] that makes it impossible [for humanity to know the answer]?
Which becomes a family of interesting questions when you substitute exact expressions for the bracketed natural language
Single values cannot be “NP Hard”. Hardness applies to a class of problems. So it may be NP Hard to compute “prove or disprove X” but this says nothing for any individual value of X.
Similarly the traveling salesman problem is NP Hard but there are inputs that have trivial outputs.
I realize now it doesn't make sense to ask if it's np-hard. Chess can be solved in constant time because there are finitely many board positions. But there are "generalized" versions of chess where the board and number of pieces can grow infinitely, then it makes sense to ask questions about complexity.
I guess I was thinking something along those lines. Perhaps if there's a way to "generalize" the P vs NP question, then we can hypothetically give some mildly meaningful answer about complexity.
Probably not!
Thinking of a way for smart people to formally encode questions and hand them off to dumb computers is what led to the whole field of computing in the first place!
It seems that at least some theorists believe the P vs NP question isn't even provable using our current axioms, and that a proof would require new mathematics.
Pretty sure there's just a different notion of "Computable" going on. Author probably is choosing their (very strict!) definition of computable, whereas most folks would consider "Computable" to be "A computer could currently do it".
Regardless of whether yes, the given example program is computable (it is), the general folks of the CS world probably understand it to be uncomputable because no computer could run that properly due to the impossible complexity in `if god`.
It does bother me a little bit when an academic writes an entire article about their specific definition of a word, then lambastes the world for asking dumb questions using a different definition of the same word, and refusing to elaborate.
Computable has a standard definition in CS. It’s not like the author made it up or something.
Yeah, if you're talking to CS folks who have encountered that definition as part of a theory class, then sure, good chances they could be scolded for asking the wrong questions using that word.
But that's a small bit of CS undergrads, and a very small part of the internet / wider world, who have a more colloquial definition of it. Not sure it's entirely worth scolding them, is all I'm saying.
The post is on a theoretical CS blog, talking about a question in a theoretical CS textbook. Why shouldn’t we expect it to use theoretical CS jargon?
Your example function just always never prints so that makes things easier.
Why's that?
GP is joking about the certainty of there being / not being a god
In my experience, I find that constructive mathematics better aligns with peoples intuitions here rather than classical computer science.
For example, we don't (yet) have a proof that there exists (constructively) a program that that prints out the answer to the P=NP problem.
I had some commentary in my thesis about this issue with regards to computable Julia sets. Mark Braverman proved that every (quadratic) Julia set is computable. But, as he notes, his proof isn't uniformly computable. Instead he develops 5 machines that attempt to draw various sets (at whatever desired resolution) given the parameter for the Julia set desired. For each Julia set, one of these 5 machines will correctly draw the set.
When doing constructive mathematics, the constructive notion of a compact set roughly corresponds to being a computable set in the sense we need for computable Julia sets. We cannot constructively prove that every (quadratic) Julia set is compact. Instead we have to divide the complex plane of possible parameters of the Julia set into multiple regions, and within each of those regions we can prove all of the corresponding Julia sets are compact.
In classical mathematics the union of all these regions is the entire complex plane, but this result doesn't hold constructively. Analogously, in classical mathematics the union of the positive reals, and the non-positive reals is the whole real line; however, again, this result doesn't hold constructively.
The constructive mathematics approach clearly states exactly what additional information is need to actually realize the computation of a (quadratic) Julia set: that is you must state in which of these regions of the complex plane you given parameter belongs to, which in turn tells you which of these 5 machines you need to run to get actually get the image you want. This is a much more satisfying answer.
And in the P=?NP case Aaronson uses, the answer wouldn't be "P=NP" (a classical answer -- totally useless) but the actual function NP->P.
People just instinctively know that you need to know which side of the disjunction you're on, and they haven't been trained in classical logic to forget it.
If NP somehow was proved to be P, with a likely value being something like O(n^(10^10^10)) or much larger, would the actual constructive reduction be at all useful?
We already have such a machine. If P=NP then there is some Turing machine that produces, for instance, a 3-SAT certificate in polynomial time.
We may enumerate the turing machines and call ours the M-th one. Given a boolean expression P, increment a counter N and run the first N turing machines on P for N steps, check each of the outputs of these against the certificate checker.
If M runs in time O(|P|^n) and the certificate checker is O(|C|^m) and then our hybrid machine runs in something like O((M+|P|^n)^2m).
All we're missing is a proof.
My point is that N is most probably bigger than the entire Universe, if it turns out to be finite.
For each Julia set, one of these 5 machines will correctly draw the set.
That's really interesting. Does this essentially correspond to a proof of being able to compute the correct set with probability no less than 1/5?
For the question "which of the 5 is correct?", is it presumed that there exists a proof that hasn't been found yet or that this is undecidable (e.g., within ZFC)?
It seems to me that topics TCS and complexity theory are to CS undergrads and CS-adjacent professionals akin to how topics in particle physics are to the layman. We've heard of the word NP-hard like how the layman has heard of entanglement, and then we've substituted working through the mathematical development with terrible pop analogies and fanciful imagination.
Sure, but there's no reason to think that everyone now has to use the very strict definition of "Computable", when it has a colloquial definition that makes perfect sense (a computer can do it).
It could be Author chose (due to their extensive training) their (very strict!) definition of computable, then wrote an entire article about their specific definition of a word, and lambasted the world for asking dumb questions using a different definition of the same word, and refusing to elaborate.
This honestly happens all the time at work, when talking to academics, or even talking to laypersons. It's hard to establish common nomenclature, and drawing a line in the sand at their nomenclature and asking people to catch up is exhausting.
Hard disagree. If you want to have a meaningful dialogue with competent specialists, the burden of learning the jargon is on you.
Philosophers spend a lot of time in term definitions and it's the only way to avoid the conversation devolving into talking past each other.
Rigor might be exhausting, the same way that exercising is. No one is forcing you to do it, but you can only reap the benefits by making the effort yourself.
Sure, I'm getting mixed up in "debate between experts" and "pedagogical difficulties with laypeople". TFA is meant to be discussing the former case, and I read it as the latter.
A fair point in general, but when reading Scott Aaronson's blog quoting a textbook called Introduction to the Theory of Computation, we should be prepared for TCS jargon.
And people curious about P versus NP or Busy Beaver should begin by learning some basic TCS, so they can understand what people who study the problems professionally are saying.
I definitely read his article as being a sort of "people keep asking me" as though they approach him in his daily life / his uncle wants to know. I suppose another reading of it is that he's referring mostly to comments on his blog, in which case this makes sense.
every time i read about theoretical cs I’m left with multiple questions:
How can we justify not steelmanning a ternary approach to halting? Can someone show me one proof which doesn’t rely on “muh do the opposite” (how do we know the halts program can’t detect this and crash with Err(ParadoxError)?) or the circular logic appeal to Rice’s theorem which itself depends on halts being undecidable? I’ve yet to find one. Collatz Conjecture? Only with unbounded memory and time, which is un-physical. That’s something we learned from Ray Solomonoff: the difference between doable and impossible is often a time limit.
According to the concept of equivalence, aren’t p and np both equivalent and not, in infinite ways (a “filibuster proof,” just make the argument for and against their equivalence based on their mutual relationship to each counting number), and fundamentally designed to be not equal by virtue of us naming them differently?
Finally, what the heck was Gödel thinking to assume we can assign different numbers to zero and the logical not? If the Gödel numbers are off, or even if not, how can an incompleteness theorem be complete? And if the incompleteness theorem is itself incomplete, why should we take it super seriously?
Just seems like we take the validity of these fundamentals for granted, and “most computer scientists believe X” is not exactly a strong argument for anyone to believe X, because it’s an appeal to mass belief.
Lest anyone think I’m a snooty smarty pants, I’d like to say i think I’m an idiot. Every day i beat myself up for being an idiot. Go ahead and feel free to downvote for this, or call me a crackpot, but a bunch of bedrock ideas of theoretical cs really are weird and suspect
- decision problems with Boolean outputs are inherently nerfed compared to ternary ones with options to refuse to answer or to stop programs from outside - p vs np suffers the same problem, since “equals” or “not equals” ignores the infinitely huge elephant of “equivalence” (not equal how?) - Gödel numbering zero (an integer) and logical not (a function) separately is a false difference because zero IS not (to the universe itself) —
to say we can’t form complete systems out of items we ourselves falsely separated in the first place is what the universal substrate, if it could speak, might call a “skill issue”
The joys of responding to someone who is so confused about terminology that you have trouble even figuring out what they meant to so...
How can we justify not steelmanning a ternary approach to halting?
I'm not certain I understand what you mean here. In actual practice, the usual approach to undecidable problems--which come up all the time in compilers and formal methods, mind you--is to build a trichotomy of "yes", "no", and "don't know" (sometimes expressed "timeout"). What undecidability says is we can't squeeze the "don't know" category down to nothing, but in many circumstances, that's just fine.
Can someone show me one proof which doesn’t rely on “muh do the opposite” (how do we know the halts program can’t detect this and crash with Err(ParadoxError)?) or the circular logic appeal to Rice’s theorem which itself depends on halts being undecidable?
Depending on how you define "muh do the opposite", this may be impossible. The essential crux of the theorem is that once your system reaches a certain level of power, it admits the possibilities of quines, which enables a level of self-reference that leads to paradoxes.
The best attempt I can give, that only indirectly reaches into self-reference is this:
Let f(x) be a program that returns the size of the smallest size program needed to output x (this is called Kolmogrov complexity). Let h(p) be a program that returns whether or not the input program p will halt. If h(p) exists, then f(x) necessarily exists:
for p = 1 to infinity:
if h(p) is true:
if p computes x: return sizeof(p)
for x = 1 to infinity:
if f(x) > y:
return x
I don't understand your proof. It would make more sense to me if I add the additional idea that there is some p* where p* = h , where p* is part of p = 1 to infinity. So you have tried to define the halting program, but this led to a contradiction.
One of the key insights is that every program is representable as an integer, and you can map essentially any integer into a program. (If this seems strange, think of a file on a computer--traditionally a stream of bytes--as just a large base-256 integer.) This means we can iterate every possible program, as there are only a countably infinite number of programs.
I should also note that this is required by our conventional definition of program (specifically, a Turing machine). There's definitely models of computation more powerful than Turing machines, but these are not believed to be physically realizable (the Church-Turing Thesis); in any case, the diagonalization form of the proof of the halting problem's uncomputability indicates that these more powerful methods are also susceptible to their own variant of the halting problem.
Paul Graham just published an article about the difference between obstinacy and persistence, which might help you out here.
How can we justify not steelmanning a ternary approach to halting? Can someone show me one proof which doesn’t rely on “muh do the opposite
I don’t even understand what you are getting at. But humbling ourselves and learning new things, especially such influential thoughts that mathematical giants such as Gödel and Turing gifted us with (and were since refined by hundreds of very smart people) should be the first step. All these thoughts were refined over a century, or half. It’s not some proposition that sounds cool and might later be proven wrong.
A Turing machine is fantastically simple and the halting problem is well-defined over it — it has n states, and one of them is labeled as HALT. Does it ever get to this state? There is no ternary option here.
(Note: Turing didn’t even consider them halting, but used an equivalent problem)
I find responding to informally posed questions which are not self consistent with answers of the form,
This is the best way I can think to formalize your question. These are some ways it's different than what you asked, but here's why I think it close enough, and this is the answer in this case.
are usually better than asserting,
There's absolutely no way to formalize your question. It's utter nonsense and I won't answer it.
Even when, to the answerer, the proposed formalization seems much different from the informal question, the questioner is often satisfied with the answer.
Unfortunately in this case the latter version doesn’t make sense. There is no way to reformulate it.
Yeah... I'm normally a huge fan of his posts, but this one seems more like venting about the number of cranks he has to deal with in the comments to his blog. Not that I blame him haha
Sipser is just taking advantage of most people not understanding the difference between computation and empirical investigation. "Does God exist" is probably an unanswerable question, but that is beside the point. Answering it is not within the realm of computation at all. Computation is simply a procedure that maps inputs to outputs. In this case, whether or not God exists is one of the inputs. It's tripping people up because we can't actually know the value of the input, but the program still exists and is a trivial program. Replace it with some other binary empirical question.
Let f: {0,1}* -> {0,1} = 1 if Paris contains at least one porta potty and 0 if it does not. This one is both computatable and you can actually run it with a true input. The one about God is also computable but can only be run with a guessed input. You can't guarantee the output corresponds in any meaningful way to the universe you live in, but it is still a computable function.
Maybe it's better to just consider f: {0,1}* -> {0,1}. "God exists" and "God does not exist" are both possible bit strings on their own. Can a program exists that outputs 0 if it gets one of these inputs and 1 if it gets the other? Of course it can. It doesn't matter if the input is empirically true or not.
Actually, the functions referred to in the question don't make any use of their inputs at all. They could just as well have been defined as functions from the empty set to {0, 1}. The "f" in the question is not a function, it's a label, such that the referent of f if God exists is the function f1, that always outputs 1, and the referent of f if God does not exist is the function f0, that always outputs 0. The question is actually not about computability at all, it's about labels.
I think this is one of the things that makes the undecidability of the halting problem hard to grok. You want to say “there are certain machines so complicated that it’s impossible for a machine to tell whether they halt or not.” But between the trivial programs “return true” and “return false”, one of them gives the correct answer for any machine and input you throw at them.
You want to object “but those programs don’t know anything about Turing machines. They don’t count!” But that’s not what decidability is about. You might want to think something like “ok, but figuring out which of those programs gives the right answer is undecidable,” but again, no, that has a defined true or false answer too. The problem can only become undecidable once it’s extended to an infinite set of machine/input combinations.
Other problems that only arise on families of objects can be similarly difficult to grok for beginners. E.g.: any given finite-dimensional vector space is isomorphic to its dual and to its double dual in many ways, but for the latter you can choose a (“natural”) isomorphism consistently over all such spaces, while for the former you can’t. “Why isn’t it naturally isomorphic? The bases are of the same length! What do we care if it depends on the basis or no? Why do we not care all those other proofs choose bases then?”
What if we replace P={god exists} with P={there is a cardinality between integers and reals}?
I think some people think of “god exists” as unknowable, or undefinable, or ill-defined, etc. But the “riddle” requires P to be exactly true or false. Seems one of the pitfalls of mixing natural language with mathematics.
But the “riddle” requires P to be exactly true or false.
Your choice of P (whether the continuum hypothesis holds) is still ill-defined! This is because the answer depends on the system of axioms one subscribes to. Or, if you feel like playing God, you may pick an answer (CH holds / does not hold) and find axioms that support it. (Which can be as simple as ZF + CH holds/does not hold.)
This always happens because mathematicians and computer scientists use shorthand descriptions that elide the details for ease of conversation. It's no different than saying that you're "multiplying by dx on both sides". "Is the traveling salesman problem NP-hard?" is talking about family of problems, not specifically an instance of it. If you fix the specific graph, then obviously it's not NP-hard since there's no N.
It's so trivially obvious when you know this that it isn't worth talking about. It is also completely unreachable for many people who don't know what these terms mean.
I have, in the past, had a misconception of this shape in a different field. In my case, it was my belief in DNA as code that is executed by things that message-pass between each other sometimes directly through the substrate and sometimes by modifying the DNA. Overall, this isn't a useless model but I needed to know when to not get addicted to it.
To biologists with mathematical backgrounds, it's obviously wrong to just take the TM execution of DNA as a model. To me, it was less so.
So it's just unfamiliarity with the basics.
Decidability, computability, existence, fruit, all have different meanings in an academic context and in a everyday context, and trying to use intuitions from the everyday meanings in an academic context leads to these "stupid questions".
[big number from Wikipedia] "exists" and is "computable" in an academic sense, even though its digits cannot fit in our universe.
This is one of the larger cognitive holes in human cognition. "If (undecidable A), then X, and if (not undecidable A) then X" is not just a math problem. I've seen it freeze entire teams of people of people in real life, in real business meetings. It is a common component of the more advanced "a guy wears a red hat if it is raining and a blue hat if it is not, you see someone wearing an orange hat, is he a cannibal?" riddles. It can inform your investment strategy. It can resolve even debates with your significant other when you say "hang on, if we go with your reason we do X and if we go with my reason we do X, let's just agree to do X each for our own reason".
It is very powerful to be able to advance past an uncertainty in some logic net and establish certainty on the other side. It's not a thing that comes up every day by any means, but it's a great tool to add to your belt.
And you can see even in this comment thread that it is not intuitive for people.
I think that Computational Complexity has the worst language (for defining and communicating ideas) of any mathematical discipline.
It's ironic, since it's a mathematical study of languages.
The wording is the confusing bit, if you're not being careful.
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.) [emphasis mine]
The alternative is not part of the function. The function f does not branch based on the value of "God exists". The branch is in the metalanguage. We don't know whether f = 0 or f = 1, but whichever it is, it is computable because both possible functions are computable.
But, I would go further: if f did include the branch, and the domain of the function is 0 (God doesn't exist) and 1 (God does exist), then we still have a computable function in the sense that we can compute a result for each value of the domain.
The confusion effectively is a matter of pushing a free variable whose value is taken to be unknown into the branch condition in f.
It's not related to the post at hand, but the way selected text is highlighted on this blog is quite bad - only the font color is changed, not the background. Not only is it pretty unintuitive, it also makes it impossible to see if you selected any non-printable characters such as spaces or newlines.
Also whether n is prime is up to the will of God, if God exists.
A God is not necessarily bound to the "laws of physics" or even basic logical necessities (a God that does comes from a specific line of theological reasoning, not the general case).
He could even make 6 odd if He so wished - altering all math and logical consistency and the whole universe, or just make just 77 even and every other number odd, making so every mathematician finds the new arrangement perfectly consistent and consider it to always have been the valid one!
So the answer does kind of "depend on your religious beliefs".
If god creates a system of logic wherein 3 is not prime, he's welcome to, but creating a new system doesn't affect the old one in the slightest.
The idea of "new doesn't affect old" is an idea based on logical and temporal consistency. God is not bound to those.
In fact the current system of odd/even - as well as any other system and law, including the "excluded middle" - can be understood to be God's arbitrary creation. You consider it logically necessary and absolute just because God willed it so, you'd be considering a different one with any arbitrary change as just as logically necessary and absolute if/when God willed it :)
People create a lesser conception of God, with specific boundaries and limitations, and then gloat how he is limited. Well, let's instead start with the more common conception of God as limitless and with total arbitrary power.
That entirely depends on your specific god belief. Suppose someone believes that god is the eternal principle of consistency?
If god is capable of anything can god decide to make it such that there is no god? Can god decide to self-limit god's own powers? If god intrinsically encompasses all possibilities does that include the possibility of godlessness?
You quickly get to then point where the concept ceases having any meaning.
My sentiments exactly.
The whole point of the comment was that the part saying "The answer does not depend on your religious beliefs" was wrong.
Yes. Trivially so. And He can even make it so godlessness involves the presense of God too, without there being any logical inconsistency even (since he's so powerful he shapes logic, not the other way around).
So the answer to "P=NP?" is "Let's see what mood god is in today"?
The answer is "God knows!"
I think if you believe in one of the omnipotent gods, yea, that is something you believe.
He could even make it so that our actions are simultaneously not fully deterministic and also not totally random, which is free will.
Which I believe is the reason why people believe in some kind of deity. Believing of some kind of deity does not exactly answer the question of “why we are here?” but it can be trivially used to argue out this apparent paradox.
God is bound to His Word and as the saying goes 'it is written':
"Never will you find a change in the way of ALLAH. [Qur'an 33:62]
"HE created the heavens and the earth in accordance with the requirements of wisdom." [Qur'an 39:5]
p.s. Computing (al-Hesaab) is also addressed. Apparently God and Gauss are both rather fond of harmonic systems:
"HE It Is Who made the sun radiate a brilliant light and the moon reflect a lustre, and ordained for it proper stages, that you might know harmonic measure and mathematics. ALLAH Has not created this system but in accordance with the requirements of truth. HE details the signs for a people who possess knowledge. " [Qur'an 10:5]
I'm not a theologist, but I don't think god recreating the world such that 3 is not prime would affect the discussion if 3 is prime right now.
In fact, I don't think god is even capable of making 3 not prime. Prime numbers are defined such that 3 is prime, it's not possible and a logical contradiction to make 3 composite without changing the definition. And the discussion is about the current definition.
But it's a human creation, god didn't invent parity or formal logic.
Only if you choose to misinterpret the point.
It's not a matter of interpretation.
Except if they wanted to say "The answer, iff your religious beliefs are conveniently tame and constrained, so that your God has limited powers and is bound to respecting excluded middle, the laws of physics and other such constraints, doesn't depend on your religious beliefs".
That's just like your opinion man
Nope. In a discourse constrained by regular logic, it's a logically consistent argument. Their rules, not mine!
Any other movie quotes to put forward in lieu of counter-arguments?
Invoking a fictitious god with any arbitrary property doesn't make your argument consistent - other then, that's just like your opinion man
Logical consistency only cares about propositions and their relationship, it doesn't care whether an entity involved in one is fictitious or not.
Pulling the God card is a bit like redefining `true` to false in some very dynamic language. Like, is there a point in asking/answering anything if anything goes?
Yep. Possible, and endless fun for a certain sort of person!
Sure, since at any given time anything God wills goes!
Law of excluded middle is a formal logic thing. If you assume law of excluded middle, you can use it for logical deduction. If you don't assume law of excluded middle, you can't. If your axioms are A->B and A then B, and even god can't change that.
In contrast laws of physics are a real world thing, and any omnipotent being can meddle with it, basically by definition.
You can't, under your logical constraints.
God has no such constraints, not just in the physical but also in the logical realm. He can make it so that assuming the law of excluded middle and not assuming it at the same time, is compatible and consistent.
This is a very good (and funny) response.
If you're allowed to invoke God ironically in the question, you're allowed to take that seriously (meta-ironically?) in the rebuttal!
In classical logic, LEM is valid.
If you’re going to quibble over whether LEM is justifiable in this case, then you need to justify why you’re only concerned about LEM; why not drop ex falso too (Kolmogorov had serious issues with this axiom, and initially considered it to be incompatible with a constructive logic) and work in a paraconsistent logic?
Also, depending on the precise formulation of this proposition, it doesn’t necessarily need LEM.
Is there a variant of "there exists a program that prints BB(8000)" that doesn't rely on some sort of axiom of choice? Maybe the intuitionists have a more useful definition of computibility if it doesn't posit that such strange machines exist.
Why does it rely on the axiom of choice? It’s a consequence of the obvious fact that for every integer n, there exists a program that prints n. This doesn’t require choice.
Maybe choice was stronger than I needed. Thinking about it more, I think the problem is that BB isn't even definable (that I can see) without LEM. There's an "either the machine halts or it doesn't" baked in to the computation of the integer.
A lot of stuff in math doesn't work the same way without the law of the excluded middle, but it's always assumed unless it's stated explicitly that we're working under some other logical system.
I care about LEM because I'm not very happy with the computational content of LEM. I know it can be interpreted as "proceed according to $not-A$; if you find a contradiction by building an $A$, wind back the universe and proceed with the resulting proof of $A$", but this feels unsettling to me. Ex-falso has trivial computational content, and we use it all the time: it's `panic!()`.
(I agree that there are formulations which don't require LEM, but it's important to be precise, especially when writing to dismiss a common misconception among people who haven't got the concepts crisply in their minds. "Is this quantity computable?" is very close in spirit to "can I compute the value of this quantity?", and LEM is exactly the kind of axiom which shows the difference.)
I have major issues with the computational content of a bottom type; my interpretation of the BHK semantics would not admit ex falso as constructive.
Of course this all of this really stems from one’s notion of semantic truth: any non-trivial semantic theory of truth can be argued as the “one true logic”, and there’s not much anyone can say otherwise! As I see it, it really comes down to how useful it turns out to be in modelling the particular domain of discourse.
As it happens, I’m more than happy to accept classical logic: I believe the principle of bivalence is how the world works, and as a result I’m forced to admit LEM if I want my proof calculus to be complete.
You are right that pointing out the connection to LEM is important and worthwhile, regardless of formulation.
FYI in the textbook version, they do say to assume the question is unambiguously binary (Sipser 2nd ed. page 162). It is very astute of you to catch that!
For those having the 3rd edition, Q. 3.22, Page 190, however in the textbook unlike the blog post, 1 is if life exists on Mars, 0 if not.
I remember the Mars question from the class I took 20 years ago.