11 ms·

The zombie misconception of theoretical computer science

251 points by Tomte 2y ago

omnicognate 2y ago
> 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.)
- soganess 2y ago
  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.”)
  - omnicognate 2y ago
    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.)
  - 5- 2y ago
    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:
    - inexcf 2y ago
      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....
  - derbOac 2y ago
    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.
- foldr 2y ago
  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).
  - debugnik 2y ago
    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.
    - michaelmior 2y ago
      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.
    - jltsiren 2y ago
      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.
- akira2501 2y ago
  > 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.."
- H8crilA 2y ago
  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 :)
- rdlw 2y ago
  > 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.
Smaug123 2y ago
> 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".
- coldtea 2y ago
  >Let n equal 3 if God exists, or 5 if God does not exist. Is n prime? 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".
  - cwillu 2y ago
    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.
    - coldtea 2y ago
      >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.
Sebb767 2y ago
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.
calf 2y ago
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 } A function is just any proper mathematical function, a "black box", such that for each input x is given exactly one unique y. A computable function (per Sipser) has some Turing machine M such that M(x) = y everywhere. 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.
- foldr 2y ago
  That definition is fine (given that we know that no Turing machine computes the halting problem). It's equivalent to f(n) = 0.
  - calf 2y ago
    Hm, but the definition is not fine if we didn't already know the status of the halting problem?
    - foldr 2y ago
      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.
      - mrkeen 2y ago
        > It's just that we wouldn't know what value the function had. I think there should be a word for that...
        foldr 2y ago
        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.
denton-scratch 2y ago
> 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.
- _flux 2y ago
  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.
- hifromwork 2y ago
  Isn't this the law of excluded middle (rejected by intuitionists and constructivists)?
  - mrkeen 2y ago
    Let n equal 3 if LEM is valid & sound, or 5 if LEM isn't valid & sound. Is n prime?
- IanCal 2y ago
  Why can't it be answered? It seems trivial to answer.
  - denton-scratch 2y ago
    The question is malformed because it contains a term that cannot be evaluated.
    - brabel 2y ago
      Even if evaluating that would make no difference?
      - ReleaseCandidat 2y ago
calf 2y ago
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.
- bubblyworld 2y ago
  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.
- alexey-salmin 2y ago
  > 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?
hAFsc 2y ago
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.
- jonathrg 2y ago
  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.
  - landc 2y ago
    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.
    - jonathrg 2y ago
      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.
  - mistercow 2y ago
    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.
kazinator 2y ago
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 and let F(x) = if (god exists) 1 else 0 Sipser is assuming that they are different and that some person with religious beliefs processed the first version above for us, and so that we are left with a F(x) = 1 or else F(x) = 0, where our own religious beliefs no longer matter. 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.
- evanb 2y ago
  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.
  - kazinator 2y ago
    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.
    - 2y ago
dash2 2y ago
The comments on this article are like a flytrap for people with exactly the kind of misconception the article is talking about.
- xcanl 2y ago
  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?"
  - groestl 2y ago
    "Yes, the blog should consider reviewing its presentation style." from you know who.
  - dash2 2y ago
    He's popularizing interesting but complicated maths. That's always gonna attract people who think they understand it, but don't.
    - larsf100 2y ago
      [flagged]
      - dgb23 2y ago
        It's definitely math, or specifically logic. The writing style in the article leans heavily on logical statements. Perhaps an interesting aside: I always thought that mathematical logic, or at least the parts we typically learn to describe CS concepts, is pretty hardcore in terms of the abstract thinking we have to perform. Until I saw what philosophers have to learn... They are taught much richer and complex concepts that can describe how logic bleeds into written/spoken language and how you extract this logic from text. Logic is used, recognized and analyzed in pretty much _everything_ they do. In contrast, we get by with the kindergarten version of logic for most things.
poikroequ 2y ago
> 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.
- mrkeen 2y ago
  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!
  - deleted 2y ago
    [deleted]
- Delk 2y ago
  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.
- raincole 2y ago
  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.
  - pvillano 2y ago
    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
- zeroonetwothree 2y ago
  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.
wodenokoto 2y ago
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.
- alexey-salmin 2y ago
  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). [1] https://en.wikipedia.org/wiki/Computable_function https://en.wikipedia.org/wiki/Computable_function
- empath75 2y ago
  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 and does_program_halt(x): if x halts: return true else: return false The important distinction is that the first function is a constant that takes no input, and the second function is not a constant and takes a program as input. The first is computable(although we may not know right now if "return false" or "return true" is the correct function, one of the two is), the second is not. 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.
deleted 2y ago
[deleted]
mistercow 2y ago
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.
- mananaysiempre 2y ago
  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?”
GrantMoyer 2y ago
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.
- Xcelerate 2y ago
  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
- zeroonetwothree 2y ago
  Unfortunately in this case the latter version doesn’t make sense. There is no way to reformulate it.
pvillano 2y ago
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.
jerf 2y ago
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.
- deleted 2y ago
  [deleted]
jhanschoo 2y ago
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.
- jvanderbot 2y ago
  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.
  - leereeves 2y ago
    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.
    - jvanderbot 2y ago
      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.
      - 2y ago
Xcelerate 2y ago
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.
- SAI_Peregrinus 2y ago
  There's also a simple algorithm to compute K(s) for any particular s (and thus for any finite set of such inputs). Enumerate every possible Turing machine by increasing length until one that outputs s is found. Since you've tried all shorter machines, and they didn't output s, you've found the shortest machine that outputs s and thus its length is K(s). Other machines of the same or greater length may exist which output s, but since K(s) is just about the minimal length this doesn't change anything. For all strings with length <n, you just repeat the brute-force for every one of the 2^n strings. It's a finite process!
  - 2y ago
jvanderbot 2y ago
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.
- voxl 2y ago
  Your example function just always never prints so that makes things easier.
  - joenot443 2y ago
    Why's that?
    - jvanderbot 2y ago
      GP is joking about the certainty of there being / not being a god
- zeroonetwothree 2y ago
  Computable has a standard definition in CS. It’s not like the author made it up or something.
  - jvanderbot 2y ago
    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.
bionhoward 2y ago
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”
- kaba0 2y ago
  > 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)
rssoconnor 2y ago
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.
- Xcelerate 2y ago
  > 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)?
  - rssoconnor 2y ago
    > For the question "which of the 5 is correct?" There is a discontinuity as the parameter 'c' crosses a location that lies on the boundary of the Mandelbrot set, where the corresponding Juila set goes from a thick ring of disconnected points (Cantor-set like) to suddenly connected and the ring is completely filled in. One candidate machine will draw a filled in Julia set, and another candidate machine will draw the ring. For each Turing Machine one can construct a complex value c, that is just barely outside the Mandlebrot set if the machine halts, but is on the inside (specifically on the boundary) of the Mandelbrot set if the Machine does not halt. Thus being able to correctly draw the Julia set all of these points amounts to solving the halting problem. Though any individual point may or may not be solvable. Of course there is at least one Turing Machine that searches for an inconsistency in ZFC. If ZFC is consistent then this machine never halts, but ZFC cannot prove this fact.
Aeium 2y ago
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?
- School-Cotton 2y ago
  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.
  - Aeium 2y ago
    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?
    - School-Cotton 2y ago
      > 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.
nonameiguess 2y ago
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.
- pdonis 2y ago
  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.
ks2048 2y ago
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.
- ilya_m 2y ago
  > 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.)
renewiltord 2y ago
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.
danielam 2y ago
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.
gowld 2y ago
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.

251 points by Tomte 2y ago

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

soganess 2y ago
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.”)
- omnicognate 2y ago
  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.)
- 5- 2y ago
  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:
  - inexcf 2y ago
    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....
- derbOac 2y ago
  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.
foldr 2y ago
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).
- debugnik 2y ago
  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.
  - michaelmior 2y ago
    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.
  - jltsiren 2y ago
    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.
akira2501 2y ago
> 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.."
H8crilA 2y ago
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 :)
rdlw 2y ago
> 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.

Smaug123 2y ago

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

coldtea 2y ago
>Let n equal 3 if God exists, or 5 if God does not exist. Is n prime? 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".
- cwillu 2y ago
  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.
  - coldtea 2y ago
    >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.

Sebb767 2y ago

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.

calf 2y ago

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 } A function is just any proper mathematical function, a "black box", such that for each input x is given exactly one unique y. A computable function (per Sipser) has some Turing machine M such that M(x) = y everywhere. 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.

foldr 2y ago
That definition is fine (given that we know that no Turing machine computes the halting problem). It's equivalent to f(n) = 0.
- calf 2y ago
  Hm, but the definition is not fine if we didn't already know the status of the halting problem?
  - foldr 2y ago
    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.
    - mrkeen 2y ago
      > It's just that we wouldn't know what value the function had. I think there should be a word for that...
      - foldr 2y ago
        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.

denton-scratch 2y ago

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

_flux 2y ago
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.
hifromwork 2y ago
Isn't this the law of excluded middle (rejected by intuitionists and constructivists)?
- mrkeen 2y ago
  Let n equal 3 if LEM is valid & sound, or 5 if LEM isn't valid & sound. Is n prime?
IanCal 2y ago
Why can't it be answered? It seems trivial to answer.
- denton-scratch 2y ago
  The question is malformed because it contains a term that cannot be evaluated.
  - brabel 2y ago
    Even if evaluating that would make no difference?
    - ReleaseCandidat 2y ago

calf 2y ago

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.

bubblyworld 2y ago
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.
alexey-salmin 2y ago
> 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?

hAFsc 2y ago

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.

jonathrg 2y ago
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.
- landc 2y ago
  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.
  - jonathrg 2y ago
    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.
- mistercow 2y ago
  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.

kazinator 2y ago

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 and let F(x) = if (god exists) 1 else 0 Sipser is assuming that they are different and that some person with religious beliefs processed the first version above for us, and so that we are left with a F(x) = 1 or else F(x) = 0, where our own religious beliefs no longer matter. 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.

evanb 2y ago
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.
- kazinator 2y ago
  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.
  - 2y ago

dash2 2y ago

The comments on this article are like a flytrap for people with exactly the kind of misconception the article is talking about.

xcanl 2y ago
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?"
- groestl 2y ago
  "Yes, the blog should consider reviewing its presentation style." from you know who.
- dash2 2y ago
  He's popularizing interesting but complicated maths. That's always gonna attract people who think they understand it, but don't.
  - larsf100 2y ago
    [flagged]
    - dgb23 2y ago
      It's definitely math, or specifically logic. The writing style in the article leans heavily on logical statements. Perhaps an interesting aside: I always thought that mathematical logic, or at least the parts we typically learn to describe CS concepts, is pretty hardcore in terms of the abstract thinking we have to perform. Until I saw what philosophers have to learn... They are taught much richer and complex concepts that can describe how logic bleeds into written/spoken language and how you extract this logic from text. Logic is used, recognized and analyzed in pretty much _everything_ they do. In contrast, we get by with the kindergarten version of logic for most things.

poikroequ 2y ago

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

mrkeen 2y ago
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!
- deleted 2y ago
  [deleted]
Delk 2y ago
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.
raincole 2y ago
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.
- pvillano 2y ago
  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
zeroonetwothree 2y ago
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.

wodenokoto 2y ago

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.

alexey-salmin 2y ago
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). [1] https://en.wikipedia.org/wiki/Computable_function https://en.wikipedia.org/wiki/Computable_function
empath75 2y ago
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 and does_program_halt(x): if x halts: return true else: return false The important distinction is that the first function is a constant that takes no input, and the second function is not a constant and takes a program as input. The first is computable(although we may not know right now if "return false" or "return true" is the correct function, one of the two is), the second is not. 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.

deleted 2y ago

[deleted]

mistercow 2y ago

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.

mananaysiempre 2y ago
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?”

GrantMoyer 2y ago

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.

Xcelerate 2y ago
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
zeroonetwothree 2y ago
Unfortunately in this case the latter version doesn’t make sense. There is no way to reformulate it.

pvillano 2y ago

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.

jerf 2y ago

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.

deleted 2y ago
[deleted]

jhanschoo 2y ago

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.

jvanderbot 2y ago
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.
- leereeves 2y ago
  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.
  - jvanderbot 2y ago
    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.
    - 2y ago

Xcelerate 2y ago

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.

SAI_Peregrinus 2y ago
There's also a simple algorithm to compute K(s) for any particular s (and thus for any finite set of such inputs). Enumerate every possible Turing machine by increasing length until one that outputs s is found. Since you've tried all shorter machines, and they didn't output s, you've found the shortest machine that outputs s and thus its length is K(s). Other machines of the same or greater length may exist which output s, but since K(s) is just about the minimal length this doesn't change anything. For all strings with length <n, you just repeat the brute-force for every one of the 2^n strings. It's a finite process!
- 2y ago

jvanderbot 2y ago

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.

voxl 2y ago
Your example function just always never prints so that makes things easier.
- joenot443 2y ago
  Why's that?
  - jvanderbot 2y ago
    GP is joking about the certainty of there being / not being a god
zeroonetwothree 2y ago
Computable has a standard definition in CS. It’s not like the author made it up or something.
- jvanderbot 2y ago
  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.

bionhoward 2y ago

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”

kaba0 2y ago
> 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)

rssoconnor 2y ago

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.

Xcelerate 2y ago
> 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)?
- rssoconnor 2y ago
  > For the question "which of the 5 is correct?" There is a discontinuity as the parameter 'c' crosses a location that lies on the boundary of the Mandelbrot set, where the corresponding Juila set goes from a thick ring of disconnected points (Cantor-set like) to suddenly connected and the ring is completely filled in. One candidate machine will draw a filled in Julia set, and another candidate machine will draw the ring. For each Turing Machine one can construct a complex value c, that is just barely outside the Mandlebrot set if the machine halts, but is on the inside (specifically on the boundary) of the Mandelbrot set if the Machine does not halt. Thus being able to correctly draw the Julia set all of these points amounts to solving the halting problem. Though any individual point may or may not be solvable. Of course there is at least one Turing Machine that searches for an inconsistency in ZFC. If ZFC is consistent then this machine never halts, but ZFC cannot prove this fact.

Aeium 2y ago

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?

School-Cotton 2y ago
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.
- Aeium 2y ago
  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?
  - School-Cotton 2y ago
    > 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.

nonameiguess 2y ago

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.

pdonis 2y ago
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.

ks2048 2y ago

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.

ilya_m 2y ago
> 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.)

renewiltord 2y ago

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.

danielam 2y ago

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.

gowld 2y ago

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.