The Zombie Misconception of Theoretical Computer Science

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.

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.

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.

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.

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.

This always happens because mathematicians and computer scientists use shorthand descriptions that elide the details for ease of conversation. It's no different than saying that you're "multiplying by dx on both sides". "Is the traveling salesman problem NP-hard?" is talking about family of problems, not specifically an instance of it. If you fix the specific graph, then obviously it's not NP-hard since there's no N.

It's so trivially obvious when you know this that it isn't worth talking about. It is also completely unreachable for many people who don't know what these terms mean.

I have, in the past, had a misconception of this shape in a different field. In my case, it was my belief in DNA as code that is executed by things that message-pass between each other sometimes directly through the substrate and sometimes by modifying the DNA. Overall, this isn't a useless model but I needed to know when to not get addicted to it.

To biologists with mathematical backgrounds, it's obviously wrong to just take the TM execution of DNA as a model. To me, it was less so.

So it's just unfamiliarity with the basics.

Decidability, computability, existence, fruit, all have different meanings in an academic context and in a everyday context, and trying to use intuitions from the everyday meanings in an academic context leads to these "stupid questions".

[big number from Wikipedia] "exists" and is "computable" in an academic sense, even though its digits cannot fit in our universe.

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.

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

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.

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.

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.

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.

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.

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.

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

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.

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?

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.

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.

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

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

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”

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

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.

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.