The zombie misconception of theoretical computer science

by Tomte • 2 years ago

251 214 2 years 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• 2 years 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.”)

omnicognate2• 2 years 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-• 2 years 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:

derbOac• 2 years 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.

foldr4• 2 years 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• 2 years 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.

akira2501• 2 years 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• 2 years 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 :)

rdlw2• 2 years 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.

Smaug1233• 2 years 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".

coldtea8• 2 years 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• 2 years 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.

nkrisc• 2 years ago

So the answer does kind of "depend on your religious beliefs".

Only if you choose to misinterpret the point.

iainmerrick• 2 years ago

This is a very good (and funny) response.

If you're allowed to invoke God ironically in the question, you're allowed to take that seriously (meta-ironically?) in the rebuttal!

denotational2• 2 years ago

In classical logic, LEM is valid.

If you’re going to quibble over whether LEM is justifiable in this case, then you need to justify why you’re only concerned about LEM; why not drop ex falso too (Kolmogorov had serious issues with this axiom, and initially considered it to be incompatible with a constructive logic) and work in a paraconsistent logic?

Also, depending on the precise formulation of this proposition, it doesn’t necessarily need LEM.

cobbal2• 2 years ago

Is there a variant of "there exists a program that prints BB(8000)" that doesn't rely on some sort of axiom of choice? Maybe the intuitionists have a more useful definition of computibility if it doesn't posit that such strange machines exist.

Smaug1233• 2 years ago

I care about LEM because I'm not very happy with the computational content of LEM. I know it can be interpreted as "proceed according to $not-A$; if you find a contradiction by building an $A$, wind back the universe and proceed with the resulting proof of $A$", but this feels unsettling to me. Ex-falso has trivial computational content, and we use it all the time: it's `panic!()`.

(I agree that there are formulations which don't require LEM, but it's important to be precise, especially when writing to dismiss a common misconception among people who haven't got the concepts crisply in their minds. "Is this quantity computable?" is very close in spirit to "can I compute the value of this quantity?", and LEM is exactly the kind of axiom which shows the difference.)

calf4• 2 years ago

FYI in the textbook version, they do say to assume the question is unambiguously binary (Sipser 2nd ed. page 162). It is very astute of you to catch that!

sudoankit• 2 years ago

For those having the 3rd edition, Q. 3.22, Page 190, however in the textbook unlike the blog post, 1 is if life exists on Mars, 0 if not.

Sebb767• 2 years 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.

calf4• 2 years 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.

foldr4• 2 years ago

That definition is fine (given that we know that no Turing machine computes the halting problem). It's equivalent to f(n) = 0.

calf4• 2 years ago

Hm, but the definition is not fine if we didn't already know the status of the halting problem?

pdonis8• 2 years ago

What about this one

This is not the kind of thing Aaronson is actually asking about. He's not asking about a function f that outputs 1 if God exists or 0 if God doesn't exist. He's asking about a label f that refers to the function f1 (that just outputs 1) if God exists or the function f0 (that just outputs 0) if God doesn't exist. To me the question is not about computability at all, it's about labels.

layer8• 2 years ago

He's not asking about a function f that outputs 1 if God exists or 0 if God doesn't exist.

Because that’s not a function in the mathematical sense. The output of a mathematical function can only depend on its inputs, and the function in question is not given any inputs, hence it’s necessarily a constant function, and constant functions are trivially computable.

denton-scratch3• 2 years 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.

hifromwork3• 2 years ago

Isn't this the law of excluded middle (rejected by intuitionists and constructivists)?

mrkeen3• 2 years ago

Let n equal 3 if LEM is valid & sound, or 5 if LEM isn't valid & sound. Is n prime?

_flux• 2 years 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.

IanCal• 2 years ago

Why can't it be answered? It seems trivial to answer.

denton-scratch3• 2 years ago

The question is malformed because it contains a term that cannot be evaluated.

killerstorm• 2 years ago

(A and X) or (A and (not X))

simplifies to A in classic logic.

I guess there's an ambiguity whether "God exists" is a propositional variable.

calf4• 2 years 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• 2 years 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-salmin4• 2 years 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?

gowld7• 2 years ago

You are further demonstrating how the cloudy semantics of the question and of casual semi-mathematical English language makes the problem harder than it needs to be.

This is a huge problem in probability theory, as you allude to. Experts often forget how their preferred mathematical models drift away from lay language, and say things casually that don't really mean what they say.

furyofantares• 2 years ago

Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist.

A slightly longer way to write this that I think would cause fewer parse errors is

Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or let f:{0,1}*→{0,1} be the constant 0 function if God does not exist.

falcor84• 2 years ago

I find the time-dependent version much more interesting:

Let G:t∈ℝ⁺->{0,1} be the 1 if God exists at time t and 0 otherwise.

EDIT: And of course this starts getting even more interesting when you analyze G in a non-inertial reference frame.

pdonis8• 2 years ago

My reaction was somewhat similar, and I posted along those lines in the comments to Aaronson's post. As I said there, the question is not about a function f that could call the constant 1 function or the constant 0 function depending on whether God exists. The question is about a label f whose referent will be either the constant 1 function or the constant 0 function, we just don't know which unless we can figure out whether or not God exists. To me the question isn't actually about computability at all (the computability of both of the constant functions is trivial), it's about labels.

gowld7• 2 years ago

The question is about computability, in the sense it's asking to recognize the possibility of an unknown (trivial) computable function.

The "God stuff" is an distraction, with modal-logic ambiguities as another commenter wrote.

I just wrote a regular expression (a real one, not PCRE), and then deleted it, and dissolved my computer in acid. It is completely impossible to ever know what I wrote. Was that function computable?

Then I got another computer and wrote a program in a Turing Complete language, and deleted and dissolved that computer in acid. Was that program computable?

hAFsc• 2 years 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.

jonathrg2• 2 years 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• 2 years 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.

mistercow2• 2 years 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.

alfdsv• 2 years ago

The exact wording (as of now, I do not know if he edits) is: "Could the P versus NP question itself be NP-hard, and therefore impossible to solve?"

That clearly implies solving. Aaronson is pretty sloppy with his own definitions and yet criticizes his students.

An unambiguous presentation would be:

1) Contrary to usual language use, we define "answer P?=NP" as "print 'yes' or 'no' or 'undecidable'".

2) By "program" we do not mean a single program, but three separate programs that print "yes", "no", or "undecidable".

3) We claim the existence of the program, not that it will ever be possible to know which of the three programs is correct.

alexey-salmin4• 2 years ago

No, he's correct.

vague existence claim of a program that cannot be concretely written

It can be concretely written. It's either "return True" or "return False". As of today we don't know which one of the two is this. However our lack of knowledge is not relevant to the question if it's computable or not. Definition of computability doesn't rely on it.

unless it takes "P==NP" and "P!=NP" as inputs, which would be a tautology.

It doesn't take any inputs at all since none are necessary. It's a constant function. The question of computability isn't relevant for constant functions or for functions with a finite set of possible inputs -- they are computable as switch-case on all possible inputs.

The problem only appears with functions that have an infinite set of possible inputs where the switch-case approach won't work. You need an _algorithm_ to convert inputs to outputs and sometimes this algorithm just can't exists, regardless of how far we've got in proving truthfulness of various mathematical statements.

kazinator4• 2 years 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.

evanb2• 2 years 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.

kazinator4• 2 years 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.

pdonis8• 2 years ago

This is explicitly expounded upon in the original

Yes, it is, but you can have functions that output other functions, and the question of computability applies to those functions as well. Sure, the constant functions are trivially computable; but one can also ask about a function that outputs one or the other of those constant functions depending on whether God exists, or whether the halting problem is solvable, or whether the Riemann hypothesis is true, etc., etc., etc. And in a post that is supposed to be about computability, saying "Gotcha! Misconception!" when people start talking about those kinds of functions instead of the trivially computable constant functions explicitly mentioned in the question does not seem to me to be a good strategy. As I posted in response to Aaronson in the comments there, before concluding from someone's answer that they have a misconception about computability, you should first make sure they don't just have a simpler misconception about what question you were asking.

zeroonetwothree5• 2 years ago

Computable doesn’t mean it’s easy to write down the implementation.

kazinator4• 2 years ago

We can't start to talk about a function being computable until we have pinned down what it is; which usually means written it down.

pdonis8• 2 years ago

I upvoted this post because it correctly describes an issue that I saw as well: the question isn't really about computability at all, it's about a label--at least, that's the question that Sipser (and Aaronson) intended to ask. But many readers (including me when I first read the question), seeing that the topic is supposedly computability and recognizing that the computability of the constant functions mentioned in the question is trivial, are going to consider the issue of computability of how the referent of the label is assigned, which is actually a more interesting computability question. Then, when the reader does this, Sipser and Aaronson say they're confusing religious beliefs with math.

dash22• 2 years ago

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

xcanl• 2 years 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• 2 years ago

"Yes, the blog should consider reviewing its presentation style." from you know who.

dash22• 2 years ago

He's popularizing interesting but complicated maths. That's always gonna attract people who think they understand it, but don't.

kragen2• 2 years ago

the other 99.99% of academics should reconsider their presentation style; the reason their papers don't spark such arguments is that they've given up on educating the ignorant the way scott does

you might say, no, plenty of academics teach undergraduates, and undergraduates are super ignorant. but undergraduates generally don't care whether bb(123456789) is computable or not unless that's on the exam, and their incentives run strongly counter to arguing with the professor if they're unconvinced; the way they've learned to play the academic game is by producing the desired answers, because that's what gets good grades, not finding holes in professors' reasoning

so i think people like scott and sabine hossenfelder are doing profoundly important work, and the groundless controversies around them demonstrate not the error of their ways but the astounding degree to which the current academic system is failing to educate the public

empath753• 2 years ago

I'm going to try and explain this in a simple way:

If I ask you to write a program that returns false if 4 is an odd number and true if it's an even number, you would say that's trivially computable:

def is_four_even(): return 4 % 2 == 0

Of course there's an even _simpler_ function:

def is_four_even(): return true

The two are both valid ways of computing that function. Four is even, it has always been even, you don't need to check if it's even, you can just return true.

For all these complicated questions about that people are all getting wrapped up about the only difference is that we currently don't know how to write the first version of the function, and we don't know which of "return true" or "return false" is the correct version of the second form of the function, but _the second form surely exists_, which means that it is computable. Either P=NP or P!=NP, and that has been true or not true since the beginning of time, and _one_ of those two functions would have been correct to use from the beginning of time. It's computable, we just don't know which one to use right now.

As soon as someone proves the status of P?=NP, you can just pick one of the two ('return false' or 'return true') if someone asks you write the function. It also doesn't really matter if a statement is provable in theory or not. Whether or not it's possible to prove that P?=NP, it is either true or it's false and it has always been either true or false, and one of those two programs is correct.

intuitionist• 2 years ago

It also doesn't really matter if a statement is provable in theory or not. Whether or not it's possible to prove that P?=NP, it is either true or it's false and it has always been either true or false, and one of those two programs is correct.

This is a pretty philosophically extremist statement (relying on a hardcore version of Platonism) and with my handle I can’t just let it stand unchallenged. :)

I’m actually somewhat more sympathetic to excluded middle for P?=NP than for some other statements, so let’s start elsewhere. I don’t think it’s at all obvious that the continuum hypothesis is, and always has been, either true or false. We know it’s independent of ZFC, of course, and there are sensible “extra” axioms that would resolve it in opposite directions (e.g. V=L vs. MM). In order to believe that there’s a fact of the matter you need to posit a very well-populated Platonic realm, despite not needing that kind of philosophical commitment to do mathematics.

Well, maybe P?=NP is just simpler than CH. It probably is! But you can imagine a case where it isn’t; e.g. if there exists an algorithm for 3-SAT (call it Algorithm A) which can be proved to be asymptotically optimal, and which runs in O(n^10^100) time if !CH, and exponential time if CH. Then the P?=NP question would be equivalent to CH, and you should have the same beliefs about its truth value. If you’re like me, that means you’re skeptical that it has a well-defined truth value “for all time” at all.

Aeium5• 2 years ago

_the second form surely exists_

Is this true for the BB function though?

What if there is a beaver that never halts or loops, and has behavior sufficiently complex, such that it's impossible to prove it will never halt.

Then for rules of that length, the second form doesn't exist.

poikroequ2• 2 years 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.

mrkeen3• 2 years 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!

Delk• 2 years 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• 2 years 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.

pvillano2• 2 years 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

zeroonetwothree5• 2 years 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.

poikroequ2• 2 years ago

I realize now it doesn't make sense to ask if it's np-hard. Chess can be solved in constant time because there are finitely many board positions. But there are "generalized" versions of chess where the board and number of pieces can grow infinitely, then it makes sense to ask questions about complexity.

I guess I was thinking something along those lines. Perhaps if there's a way to "generalize" the P vs NP question, then we can hypothetically give some mildly meaningful answer about complexity.

wodenokoto3• 2 years 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-salmin4• 2 years 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

empath753• 2 years 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.

umanwizard13• 2 years ago

h(f) is either 1 or 0

Depending on f. The God-existence function doesn't depend on its input.

You can also say, for example, let f: R->R be defined by f(x) = 1 if I'm a man, and f(x) = 2 if I'm a woman (or non-binary or anything else). Is the derivative of f zero? You don't know what the value is, but you can answer this question with "yes".

wodenokoto3• 2 years ago

So it’s just:

In universe 1, the function looks like `return True` and in universe 2, it is `return False`?

And it’s computable because nothing is really computed?

minkzilla2• 2 years ago

AN interesting and non rigorous way to think of it is can the compiler optimize away the non compute-able part. So this:

    if (God does exist)
      return isPrime(3)

    else 
      return isPrime(5)

The compiler can take this and in the first pass say, isPrime(3) is just return true, isPrime(5) is return true. Then we have an an if else with the same return for both cases, this is the same as return true!

wodenokoto3• 2 years ago

I like this explanation, but how would you apply that logic to

    If (god does exist)
        Return true
    Else
        Return False

pdonis8• 2 years ago

Why is f computable

Because f is either the constant 1 function or the constant 0 function, and both are computable. The fact that we don't know for sure which of those two functions the label "f" refers to doesn't matter if all we are asking is whether the function the label "f" refers to is computable. We know it is because both of the possible referents are computable.

bhewes• 2 years ago

Double Entendre one of my favorite poetic devices.

mistercow2• 2 years 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.

mananaysiempre2• 2 years 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• 2 years 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.

Xcelerate4• 2 years 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

zeroonetwothree5• 2 years ago

Unfortunately in this case the latter version doesn’t make sense. There is no way to reformulate it.

pvillano2• 2 years 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• 2 years 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.

jhanschoo• 2 years 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.

jvanderbot6• 2 years 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• 2 years 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.

namaria• 2 years ago

Hard disagree. If you want to have a meaningful dialogue with competent specialists, the burden of learning the jargon is on you.

Philosophers spend a lot of time in term definitions and it's the only way to avoid the conversation devolving into talking past each other.

Rigor might be exhausting, the same way that exercising is. No one is forcing you to do it, but you can only reap the benefits by making the effort yourself.

Xcelerate4• 2 years 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.

jmount• 2 years ago

Reminds me of the possible excess power of P/Poly versus P. Also does anybody remember the general name for circuit complexity classes where the circuit itself has to be written out by a simple Turing machine (I thought there was one but it isn't on the tip of my tong).

bo1024• 2 years ago

Yeah, the word is "uniform", e.g. a uniform family of circuits is one where there is a Turing machine where, for each n, it outputs the circuit for inputs of size n.

aidenn0• 2 years ago

Similar to how all real-world computers have a finite number of states and are thus not Turing machines, but rather finite state machines.

forgot-im-old• 2 years ago

Argh don't say that, someone might question funding CS theory grant proposals.

paulmd• 2 years ago

But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length < n? The answer is yes! And there exists such an algorithm for any value of n.

of course - n is by definition a finite number!

and in fact at infinity, all finite numbers are quite small, actually. A mile might as well be a millimeter, from your chair at the end of the universe.

And your scenario is basically just "hilbert's infinite hotel, on a computer" - we can of course add another program simply by moving all the existing programs 1 spot over... and it remains the exact same size of table needed to compute it!

I would actually generalize this and just say that most people have poor intuition of how infinities (alephs, etc) and transfinite mathematics work in general. it's not a common subject, it's not a subject with everyday relevance, and it's deeply steeped in the emergent properties of mathematics and category/set theory. Like not only are infinities bigger than any finite number, but some infinities can nevertheless be bigger than other infinities etc - these are not things that are immediately obvious to the 3rd-grade concept of "infinity" that most people stop at.

the much more interesting question would be if there exists an n < infinity such that the algorithm can be computed, and of course the answer is no (darn, there goes my turing prize).

ffhhj• 2 years ago

a program that just prints the answer for all of those things

Everything can be textualized, but making a complete interpreter for it requires understanding what intelligence really is.

gowld7• 2 years ago

This description makes it sounds like large areas of computer science are just goofy, meaningless, games.

But what's really happening is that "infinity" is standing in for "approximate, eventual, steady state behavior for sufficiently large N, larger than any specific one-off gimmick you might think of".

In the real world, though, those gimmicks are important, and the constants and low-order terms ignored in a Big-O comparison are important to real world performance.

There is constant tension between "big enough problem that the contant factors don't matter", and "small enough problem that it conforms to the (often implicit) of what 'constant' means (example: 32bit ints masquerading as integers)"

cubefox• 2 years ago

This description makes it sounds like large areas of computer science are just goofy, meaningless, games.

Well, only computability theory, not complexity theory, which you mention in the rest of your post.

Xcelerate4• 2 years ago

This description makes it sounds like large areas of computer science are just goofy, meaningless, games.

Oh no, not at all. My point is that the concept of infinity is in a sense necessary for the mathematics involved in developing algorithms to solve problems. We are performing induction to "predict" the behavior of an infinite number of Turing machines without actually running them. We can't just iterate through all possible programs, so we have to use patterns that apply in a consistent way to all possible problem instances to narrow down the search space.

approximate, eventual, steady state behavior for sufficiently large N, larger than any specific one-off gimmick you might think of

I know this is how computational complexity theory is considered from the perspective of many software engineers, but my point is a bit more fundamental. Computational complexity theory ultimately isn't concerned about any one particular problem and how to solve it quickly for practical applications—the goal is to understand what is and isn't possible with computation overall and with what resources (time, space). Why solve one problem when you can solve all of them?

But to do that requires really understanding the mathematical structures behind computation itself. If you're a formalist, instead of thinking of infinity as "the limit of large n", you think of it as a concept in a formal system that involves manipulating symbols according to a set of axioms and inference rules. You can use whatever intuitive human-scale analogies you prefer when thinking about large cardinal axioms or the continuum hypothesis, but at the end of the day, all that matters in terms of computability and computational complexity is how exploring the space of proofs derivable from these formal systems leads to a better understanding about the behavior of Turing machines (and thus the nature and fundamental limits of computation).

SAI_Peregrinus• 2 years 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!

hyeoniuwu• 2 years ago

This is incorrect. The problem is that you won't be able to tell if certain small Turing machines halt to give s, or loop forever. (So, if you are dovetailing through every possible Turing machine, the first one to output s may not be the minimal one. If you are not dovetailing, your search procedure will not halt, as you'll become stuck enumerating a Turing machine which does not halt.)

(Besides, that there is an "algorithm to compute K(s) for any particular s" directly contradicts the non-computability of K(s).)

jvanderbot6• 2 years 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• 2 years ago

Your example function just always never prints so that makes things easier.

joenot443• 2 years ago

Why's that?

zeroonetwothree5• 2 years ago

Computable has a standard definition in CS. It’s not like the author made it up or something.

jvanderbot6• 2 years 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• 2 years 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”

kaba03• 2 years 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)

jcranmer3• 2 years ago

The joys of responding to someone who is so confused about terminology that you have trouble even figuring out what they meant to so...

How can we justify not steelmanning a ternary approach to halting?

I'm not certain I understand what you mean here. In actual practice, the usual approach to undecidable problems--which come up all the time in compilers and formal methods, mind you--is to build a trichotomy of "yes", "no", and "don't know" (sometimes expressed "timeout"). What undecidability says is we can't squeeze the "don't know" category down to nothing, but in many circumstances, that's just fine.

Can someone show me one proof which doesn’t rely on “muh do the opposite” (how do we know the halts program can’t detect this and crash with Err(ParadoxError)?) or the circular logic appeal to Rice’s theorem which itself depends on halts being undecidable?

Depending on how you define "muh do the opposite", this may be impossible. The essential crux of the theorem is that once your system reaches a certain level of power, it admits the possibilities of quines, which enables a level of self-reference that leads to paradoxes.

The best attempt I can give, that only indirectly reaches into self-reference is this:

Let f(x) be a program that returns the size of the smallest size program needed to output x (this is called Kolmogrov complexity). Let h(p) be a program that returns whether or not the input program p will halt. If h(p) exists, then f(x) necessarily exists:

  for p = 1 to infinity:
    if h(p) is true:
      if p computes x: return sizeof(p)

If f(x) exists, we can write g(y) (informally, output the smallest integer that has at least a given Kolmogrov complexity) as follows:

  for x = 1 to infinity:
    if f(x) > y:
      return x

However, we have a paradox now. If g exists, it has a size, which of course bounds the maximum complexity of its output. But we've just asserted that the output has to have a minimum complexity--and if we choose the bounds right, there's no possible overlap. Consequently, something in the construction must be wrong. Yet I've given the code for every program but the halting program... which means the halting program itself can't exist.

lo0dot0• 2 years ago

I don't understand your proof. It would make more sense to me if I add the additional idea that there is some p* where p* = h , where p* is part of p = 1 to infinity. So you have tried to define the halting program, but this led to a contradiction.

samatman4• 2 years ago

Paul Graham just published an article about the difference between obstinacy and persistence, which might help you out here.

https://news.ycombinator.com/item?id=40907155

rssoconnor2• 2 years 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.

Xcelerate4• 2 years 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)?

rssoconnor2• 2 years 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.

aeneasmackenzie• 2 years ago

And in the P=?NP case Aaronson uses, the answer wouldn't be "P=NP" (a classical answer -- totally useless) but the actual function NP->P.

People just instinctively know that you need to know which side of the disjunction you're on, and they haven't been trained in classical logic to forget it.

gowld7• 2 years ago

If NP somehow was proved to be P, with a likely value being something like O(n^(10^10^10)) or much larger, would the actual constructive reduction be at all useful?

Aeium5• 2 years 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?

umanwizard13• 2 years 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.

Aeium5• 2 years 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?

immibis2• 2 years ago

Every Turing machine execution either halts, or does not halt. There are no intermediate possibilities. Some non-halting is easier to prove than others, but it's all still non-halting.

Aeium5• 2 years ago

Yes, this is clearly true. Pardon the hasty first reading and deleted comment please.

It doesn't address what I am claiming though.

The busy beaver is not defined entirely by halting vs not-halting.

Looping beavers are excluded as well.

The middle ground I am claiming is that there is a middle ground between non-halting and provably non-halting.

I'm claiming there could be a non-halting Beaver that is impossible to prove, which would mean there is no answer for the BB function.

jcranmer3• 2 years ago

To be frank, this is an issue where there's an abuse of terminology going on, although the people asking the question probably don't realize there's an abuse of terminology.

"Is X computable?" is asking if there is a program that is capable of printing X out. For any integer, the answer to this question is trivially yes.

But when people are asking "Is BB(6) computable?", that's not really what they're intending to ask. What they're trying to ask is "is it possible for us to figure out what the value of BB(6) is?" In a more precise sense, the question is "Can we prove {BB(6) = x} is a true statement for some value of x?"

To some degree, I think Scott is being somewhat specious here. The question may be somewhat malformed as written, but it's also pretty clear to an expert what the question meant to ask, and--especially when you're targeting a more lay audience--insisting on giving the trivial answer to the clearly unintended question isn't likely to help the situation much.

elijaht2• 2 years ago

For the purpose of the busy beaver problem, your second and third cases are equivalent- it’s a beaver that does not halt. Therefore neither of them are BB(6). BB(6) is tautologically an integer

nonameiguess• 2 years 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.

pdonis8• 2 years 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• 2 years 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_m3• 2 years 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• 2 years 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• 2 years 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.

gowld7• 2 years 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.

The zombie misconception of theoretical computer science

Related Stories