[HN Gopher] The zombie misconception of theoretical computer sci...
___________________________________________________________________
The zombie misconception of theoretical computer science
Author : Tomte
Score : 215 points
Date : 2024-07-09 05:07 UTC (17 hours ago)
(HTM) web link (scottaaronson.blog)
(TXT) w3m dump (scottaaronson.blog)
| omnicognate wrote:
| > 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 wrote:
| isn't it actually one program? Imagine the implementation using
| an oracle.
|
| You being a clever programmer somehow know of a very powerful
| oracle, lets call the oracle Pauli. You're program works as
| follows: func main(): response =
| write_pauli_asking_if_p_is_np() //synchronous, waits for
| response if response is true:
| print("P=NP.") else: print("P[?]NP.")
| omnicognate wrote:
| 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- wrote:
| nit:
|
| > if response is true:
|
| i've always wondered how people know when to stop (which, i
| guess, is relevant to the subject matter).
|
| e.g. why is your next step not
|
| > if (response is true) is true:
| inexcf wrote:
| I would say it's because this is pseudo code and it is a
| lot clearer that way.
|
| Depending on language
|
| >if response:
|
| could mean "response" is true,1,not empty, X....
| derbOac wrote:
| 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.
| pdonis wrote:
| _> The if-then part of it is part of the function
| definition._
|
| No, it isn't. The if-then part of the question is about
| which of two trivial functions the label "f" refers to. It
| has nothing to do with the functions themselves or their
| computability. That, from what I can gather, is supposed to
| be the point of the question, but I don't think the
| question gets that point across very well.
| foldr wrote:
| 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 wrote:
| But "we don't know which of the two it is" handwaves away
| that "answering P vs NP" means precisely coming up with the
| proof!
|
| Those constant functions aren't proofs, the proof is in
| coming up with a series of computable steps to reduce a model
| of P=NP into that constant function. That is, the proof is
| the computation itself, not just the constant value.
|
| What the author did describe is a function that we can only
| evaluate when we already have an answer for P = NP, not a
| function that computes it.
| michaelmior wrote:
| Part of the point is that computability is different from
| knowing how to write a program that actually computes the
| desired value. We can say a program exists to print whether
| P=NP (whether it is computable) without knowing how to come
| up with a concrete implementation of that program.
| jltsiren wrote:
| Proving P vs. NP and answering the question correctly are
| two different problems.
|
| Computability is defined in terms of functions that map the
| input to yes/no. A function is computable if there exists a
| representation that computes it correctly for any input and
| eventually terminates. Every yes/no question where the
| answer does not depend on the input is by definition
| computable. The corresponding function is either the one
| that maps every input to "yes" or the one that maps every
| input to "no". We may not know which one, but that's
| irrelevant.
|
| In some sense, computability is similar to probability.
| Your intuition is wrong, and following it only leads to
| further confusion. But if you unlearn it and rebuild it
| from basic principles, things become much clearer.
| nyrikki wrote:
| Nit, decision problems are one type of computable
| problems, but you have other types like function
| problems, optimization problems, etc.
|
| NP, by definition involves decision problems, but many
| NP-Hard problems are optimization problems.
|
| More specifically NP is the set of decision problems
| solvable by a NTM in poly time with the following
| conditions:
|
| 1) If the answer is "yes," at least one computation path
| accepts. 2) If the answer is "no," all computation paths
| reject
|
| Equivalently is is the set of decision problems
| verifiable by a TM in poly time.
|
| Modern programming tends to only care about #1, and
| structured programming paradigm helps with that.
|
| People not moving past NP in complexity theory is the
| real problem here. I also blame using the 'trys all
| answers at once' NTM intuition vs the max lucky guesser
| which makes it less silly.
|
| But didactic half truths do really hurt.
| Entscheidungsproblem is better for teaching people in my
| experience.
| j16sdiz wrote:
| > ... handwaves away that ..
|
| These kind of handwaveing are quite common in math. For
| example, Axiom of Choice assume there exists a choice
| function. It does not specify how.
| alexey-salmin wrote:
| > But "we don't know which of the two it is" handwaves away
| that "answering P vs NP" means precisely coming up with the
| proof!
|
| Of course it's a not a proof of "P=NP", but no one is
| asking for it.
|
| > What the author did describe is a function that we can
| only evaluate when we already have an answer for P = NP,
| not a function that computes it.
|
| Yes. This function is still computable though. The question
| of computability doesn't depend on humans being able to
| evaluate this function on a given day in history.
| jameshart wrote:
| I think the intuition people want to apply here is that 'is
| P=NP' feels like an instance of a class of questions - 'is
| P= _x_ ', and if _that_ is computable, then it implies we
| can attack P=NP by coming up with a way to compute it and
| feeding in NP.
|
| But I think the issue there is the assumption that it even
| makes sense to define a function over 'classes of
| questions'.
| Sharlin wrote:
| The whole point is simply that the notion of computability
| is not related to coming up with proofs or to any
| mechanical process for arriving at a result based on a set
| of axioms. "Computable" and "Provable in ZFC (or whatever)"
| are just two different things and pertain to different
| mathematical objects. Functions are computable (or not).
| Theorems are provable (or not).
| umanwizard wrote:
| Correct, the author did not describe a program that
| computes whether P = NP. He merely proved that such a
| program exists, by describing two programs, and showing
| that one of them must be the one that computes whether P =
| NP (we just don't know which one, but we at least know that
| _it exists_ ).
| akira2501 wrote:
| > 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 wrote:
| It is one program. If P=NP then the body of the program
| consists of "print(P=NP)". And otherwise it consists of
| "print(P!=NP)". [1]
|
| Similarly for every hash function there exists a program that
| outputs a hash collision in well under a second. Just hardcore
| any collision and print it to the screen. [2]
|
| [1] If you want to be pedantic then there's a third option that
| prints some more complicated statement about the relationship
| between standard axioms and P?=NP.
|
| [2] Please don't ruin my short argument by pointing out that
| someone can create a hash function with output size in the
| petabytes range :)
| rdlw wrote:
| > That's not a program, it's two programs
|
| Yes, and _one of them_ is "a fast program that correctly
| answers the P vs. NP question". We don't know which.
| Smaug123 wrote:
| > If you're still tempted to quibble, then consider the following
| parallel question:
|
| > Let n equal 3 if God exists, or 5 if God does not exist. Is n
| prime?
|
| Sure, I'll happily quibble! You're using excluded middle to
| assert that n is either 3 or 5, but you haven't justified that
| excluded middle holds for the proposition "God exists".
| coldtea wrote:
| > _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 wrote:
| If god creates a system of logic wherein 3 is not prime, he's
| welcome to, but creating a new system doesn't affect the old
| one in the slightest.
| coldtea wrote:
| > _but creating a new system doesn 't affect the old one in
| the slightest._
|
| The idea of "new doesn't affect old" is an idea based on
| logical and temporal consistency. God is not bound to
| those.
|
| In fact the current system of odd/even - as well as any
| other system and law, including the "excluded middle" - can
| be understood to be God's arbitrary creation. You consider
| it logically necessary and absolute just because God willed
| it so, you'd be considering a different one with any
| arbitrary change as just as logically necessary and
| absolute if/when God willed it :)
|
| People create a lesser conception of God, with specific
| boundaries and limitations, and then gloat how he is
| limited. Well, let's instead start with the more common
| conception of God as limitless and with total arbitrary
| power.
| simonh wrote:
| >The idea of "new doesn't affect old" is an idea based on
| logical and temporal consistency. God is not bound to
| those.
|
| That entirely depends on your specific god belief.
| Suppose someone believes that god is the eternal
| principle of consistency?
|
| >Well, let's instead start with the more common
| conception of God as limitless and with total arbitrary
| power.
|
| If god is capable of anything can god decide to make it
| such that there is no god? Can god decide to self-limit
| god's own powers? If god intrinsically encompasses all
| possibilities does that include the possibility of
| godlessness?
|
| You quickly get to then point where the concept ceases
| having any meaning.
| coldtea wrote:
| > _That entirely depends on your specific god belief_
|
| My sentiments exactly.
|
| The whole point of the comment was that the part saying
| "The answer does not depend on your religious beliefs"
| was wrong.
|
| > _If god is capable of anything can god decide to make
| it such that there is no god? Can god decide to self-
| limit god 's own powers? If god intrinsically encompasses
| all possibilities does that include the possibility of
| godlessness?_
|
| Yes. Trivially so. And He can even make it so godlessness
| involves the presense of God too, without there being any
| logical inconsistency even (since he's so powerful he
| shapes logic, not the other way around).
| TheOtherHobbes wrote:
| So the answer to "P=NP?" is "Let's see what mood god is
| in today"?
| zbyszek wrote:
| The answer is "God knows!"
| bee_rider wrote:
| I think if you believe in one of the omnipotent gods,
| yea, that is something you believe.
| prmph wrote:
| He could even make it so that our actions are
| simultaneously not fully deterministic and also not
| totally random, which is free will.
| dfox wrote:
| Which I believe is the reason why people believe in some
| kind of deity. Believing of some kind of deity does not
| exactly answer the question of "why we are here?" but it
| can be trivially used to argue out this apparent paradox.
| hifromwork wrote:
| >>but creating a new system doesn't affect the old one in
| the slightest.
|
| >The idea of "new doesn't affect old" is an idea based on
| logical and temporal consistency. God is not bound to
| those.
|
| I'm not a theologist, but I don't think god recreating
| the world such that 3 is not prime would affect the
| discussion if 3 is prime right now.
|
| In fact, I don't think god is even capable of making 3
| not prime. Prime numbers are defined such that 3 is
| prime, it's not possible and a logical contradiction to
| make 3 composite without changing the definition. And the
| discussion is about the current definition.
|
| >In fact the current system of odd/even - as well as any
| other system and law, including the "excluded middle" -
| can be understood to be God's arbitrary creation
|
| But it's a human creation, god didn't invent parity or
| formal logic.
| temporarely wrote:
| > God is not bound to those.
|
| God is bound to His Word and as the saying goes 'it is
| written':
|
| _" Never will you find a change in the way of ALLAH._
| [Qur'an 33:62]
|
| > Arbitrary creation
|
| _" HE created the heavens and the earth in accordance
| with the requirements of wisdom."_ [Qur'an 39:5]
|
| p.s. Computing (al-Hesaab) is also addressed. Apparently
| God and Gauss are both rather fond of harmonic systems:
|
| _" HE It Is Who made the sun radiate a brilliant light
| and the moon reflect a lustre, and ordained for it proper
| stages, that you might know harmonic measure and
| mathematics. ALLAH Has not created this system but in
| accordance with the requirements of truth. HE details the
| signs for a people who possess knowledge. "_ [Qur'an
| 10:5]
| nkrisc wrote:
| > So the answer does kind of "depend on your religious
| beliefs".
|
| Only if you choose to misinterpret the point.
| coldtea wrote:
| It's not a matter of interpretation.
|
| Except if they wanted to say "The answer, iff your
| religious beliefs are conveniently tame and constrained, so
| that your God has limited powers and is bound to respecting
| excluded middle, the laws of physics and other such
| constraints, doesn't depend on your religious beliefs".
| badmonkey101 wrote:
| That's just like your opinion man
| coldtea wrote:
| Nope. In a discourse constrained by regular logic, it's a
| logically consistent argument. Their rules, not mine!
|
| Any other movie quotes to put forward in lieu of counter-
| arguments?
| badmonkey101 wrote:
| Invoking a fictitious god with any arbitrary property
| doesn't make your argument consistent - other then,
| that's just like your opinion man
| coldtea wrote:
| > _Invoking a fictitious god with any arbitrary property
| doesn 't make your argument consistent _
|
| Logical consistency only cares about propositions and
| their relationship, it doesn't care whether an entity
| involved in one is fictitious or not.
| hifromwork wrote:
| Law of excluded middle is a formal logic thing. If you
| assume law of excluded middle, you can use it for logical
| deduction. If you don't assume law of excluded middle,
| you can't. If your axioms are A->B and A then B, and even
| god can't change that.
|
| In contrast laws of physics are a real world thing, and
| any omnipotent being can meddle with it, basically by
| definition.
| coldtea wrote:
| > _If you don 't assume law of excluded middle, you
| can't._
|
| You can't, under your logical constraints.
|
| God has no such constraints, not just in the physical but
| also in the logical realm. He can make it so that
| assuming the law of excluded middle and not assuming it
| at the same time, is compatible and consistent.
| kaba0 wrote:
| Pulling the God card is a bit like redefining `true` to
| false in some very dynamic language. Like, is there a
| point in asking/answering anything if anything goes?
| coldtea wrote:
| > _Pulling the God card is a bit like redefining `true`
| to false in some very dynamic language._
|
| Yep. Possible, and endless fun for a certain sort of
| person!
|
| > _Like, is there a point in asking /answering anything
| if anything goes?_
|
| Sure, since at any given time anything God wills goes!
| iainmerrick wrote:
| 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!
| denotational wrote:
| 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.
| cobbal wrote:
| 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.
| umanwizard wrote:
| > Is there a variant of "there exists a program that prints
| BB(8000)" that doesn't rely on some sort of axiom of
| choice?
|
| Why does it rely on the axiom of choice? It's a consequence
| of the obvious fact that for every integer n, there exists
| a program that prints n. This doesn't require choice.
| cobbal wrote:
| Maybe choice was stronger than I needed. Thinking about
| it more, I think the problem is that BB isn't even
| definable (that I can see) without LEM. There's an
| "either the machine halts or it doesn't" baked in to the
| computation of the integer.
| umanwizard wrote:
| A lot of stuff in math doesn't work the same way without
| the law of the excluded middle, but it's always assumed
| unless it's stated explicitly that we're working under
| some other logical system.
| Smaug123 wrote:
| 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.)
| denotational wrote:
| > I'm not very happy with the computational content of LEM
|
| > Ex-falso has trivial computational content, and we use it
| all the time: it's `panic!()`.
|
| I have major issues with the computational content of a
| bottom type; my interpretation of the BHK semantics would
| not admit _ex falso_ as constructive.
|
| Of course this all of this really stems from one's notion
| of semantic truth: any non-trivial semantic theory of truth
| can be argued as the "one true logic", and there's not much
| anyone can say otherwise! As I see it, it really comes down
| to how useful it turns out to be in modelling the
| particular domain of discourse.
|
| As it happens, I'm more than happy to accept classical
| logic: I believe the principle of bivalence is how the
| world works, and as a result I'm forced to admit LEM if I
| want my proof calculus to be complete.
|
| You are right that pointing out the connection to LEM is
| important and worthwhile, regardless of formulation.
| calf wrote:
| 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 wrote:
| 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.
| zeroonetwothree wrote:
| I remember the Mars question from the class I took 20 years
| ago.
| Sebb767 wrote:
| It's not related to the post at hand, but the way selected text
| is highlighted on this blog is quite bad - only the font color is
| changed, not the background. Not only is it pretty unintuitive,
| it also makes it impossible to see if you selected any non-
| printable characters such as spaces or newlines.
| calf wrote:
| What about this one: f(n) = { 0, if no Turing
| machine computes the halting problem H(n), if
| there exists a Turing machine, H, that computes the halting
| problem }
|
| A function is just any proper mathematical function, a "black
| box", such that for each input _x_ is given exactly one unique
| _y_. A computable function (per Sipser) has some Turing machine
| _M_ such that _M_ ( _x_ ) = _y_ everywhere.
|
| It would seem the definitions are also fine for the above
| contrived example. edit: I'm not sure if _n_ needs to encode a
| tuple (P, i) for some program P on input i and so forth.
| foldr wrote:
| That definition is fine (given that we know that no Turing
| machine computes the halting problem). It's equivalent to f(n)
| = 0.
| calf wrote:
| Hm, but the definition is not fine if we didn't already know
| the status of the halting problem?
| foldr wrote:
| In that scenario I think the definition itself is still
| fine, technically. It's just that we wouldn't know what
| value the function had. It would be a bit like defining
| f(n) = n + the number of hairs Julius Caesar had when he
| died. There's nothing inherently wrong with the definition.
| You just can't do much with it.
| mrkeen wrote:
| > It's just that we wouldn't know what value the function
| had.
|
| I think there should be a word for that...
| foldr wrote:
| I don't think so. It's a pretty uninteresting property of
| a function whether or not a particular person happens to
| know its value for a given input. It does not entail that
| the function is not computable, if that's what you're
| suggesting.
| karatinversion wrote:
| To tie this back to TFA, even before we knew that the
| Halting problem was uncomputable, we could have defined
| f(n) = { 1 if there is a Turing machine with at most n
| states that solves the Halting problem; 0
| otherwise }
|
| and we can easily show that f(n) is computable without
| proving that the Halting problem is undecideable. Viz., f
| is either constant 0; or equal to a function of the form
| g_k(n) = { 1 if n >= k; 0 if n < k },
|
| and both the constant 0 function, and all the g_k
| functions, are computable; thus f is computable.
| pdonis wrote:
| _> 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.
| denton-scratch wrote:
| > 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.
| hifromwork wrote:
| Isn't this the law of excluded middle (rejected by
| intuitionists and constructivists)?
| mrkeen wrote:
| Let n equal 3 if LEM is valid & sound, or 5 if LEM isn't
| valid & sound. Is n prime?
| _flux wrote:
| 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 wrote:
| Why can't it be answered? It seems trivial to answer.
| denton-scratch wrote:
| The question is malformed because it contains a term that
| cannot be evaluated.
| brabel wrote:
| Even if evaluating that would make no difference?
| ReleaseCandidat wrote:
| That's the problem with side effects: you don't know if
| they make a difference until you evaluate them. And "God"
| is about the biggest imaginable side effect.
| kaba0 wrote:
| Well, the compiler says undefined behavior and optimizes
| it away :D
| denton-scratch wrote:
| "God" has some unique properties. One of those might be
| that God neither exists nor doesn't exist. If God has
| this property of 'neitherism', then the value of n is
| undefined. Neitherism has been attributed to many
| religious entities.
|
| To answer a question, you first have to be able to parse
| the question.
| samatman wrote:
| I see the question this way: fn
| is_n_prime_whether_or_not_God_exists() if
| (is_prime(3) && is_prime(5)) { // early return
| return true; } else { return
| three_if_God_exists_five_otherwise(); }
| }
| killerstorm wrote:
| (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.
| calf wrote:
| 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 wrote:
| I think the point is that whatever predicate you fill in for
| "god", the implication is strictly speaking true in classical
| first-order logic (and probably many other logical systems
| too). The pragma analogy is a good one.
|
| Whether there exists such a predicate that conforms to your
| conception of God or not is a separate (non-mathematical)
| issue.
|
| I think it's a bit like the surprise people show when they
| learn that in classical logic a false statement implies
| everything. Mathematics has strict formal rules, and it's
| important to leave aside your preconceptions of the semantics
| of various words like "implies" and "if" when engaging in it.
| alexey-salmin wrote:
| > 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?
| furyofantares wrote:
| > 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 wrote:
| I find the time-dependent version much more interesting:
|
| Let G:t[?]R+->{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.
| pdonis wrote:
| 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.
| hAFsc wrote:
| Extremely strange reasoning from Aaronson. He goes from the
| question "How hard is it to solve P?=NP" to a vague existence
| claim of a program that cannot be concretely written, unless it
| takes "P==NP" and "P!=NP" as inputs, which would be a tautology.
|
| This claimed program does not answer the above question at all.
| His students are correct, he is wrong.
| jonathrg wrote:
| 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 wrote:
| Sounds like the same question to me, for sure the students
| intended it that way. Many hard problems feel like you need
| an internal mental SAT solver to arrive at the solution.
|
| Anyway, even if it were an invalid question, his answer still
| does not make any sense.
| jonathrg wrote:
| Those are definitely not the same question, NP-hardness has
| a precise meaning while "hard to solve" is a subjective
| judgement
|
| The answer is trying to show the absurdity of the question.
| It's like asking for the time complexity of factoring 120.
| If there is no input to the algorithm, the answer is always
| trivial.
| mistercow wrote:
| 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 wrote:
| 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.
| umanwizard wrote:
| > By "program" we do not mean a single program, but three
| separate programs that print "yes", "no", or "undecidable".
|
| You can think of it not as he is describing three separate
| programs, but giving three separate possible descriptions
| of one program and asserting that one of them is indeed the
| correct description.
| alexey-salmin wrote:
| 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.
| kazinator wrote:
| That Sipser question is just sophistry.
|
| A function F that calculation 1 if god exists, otherwise 0 is not
| computable.
|
| A function _definition_ F that binds F to the 1 function if god
| exists, or else binds the symbol F to the 0 function if god does
| not exist, if it can be processed, results in a function binding
| that contains a computable function.
|
| However, the _definition_ cannot be processed computationally,
| because of the decision that it requires. Someone arbitrarily
| resolves it based on their religious beliefs.
|
| The religious beliefs were pushed into the definition time,
| leaving whatever function is decided on computable.
|
| Problem is, in math, there is no definition time versus run time.
| There is no difference between: if (god exists)
| let F(x) = 1 else let F(x) = 0
|
| and let F(x) = if (god exists) 1 else 0
|
| Sipser is assuming that they are different and that some person
| with religious beliefs processed the first version above for us,
| and so that we are left with a F(x) = 1 or else F(x) = 0, where
| our own religious beliefs no longer matter.
|
| That only makes sense if we specify that the paradigm we are in
| is a programming language with definition times and run times,
| which seems out of place in a book about theory, let alone if it
| is just assumed as understood.
| evanb wrote:
| This is explicitly expounded upon in the original:
|
| > The deeper lesson Sipser was trying to impart is that the
| concept of computability applies to functions or infinite
| sequences, not to individual yes-or-no questions or individual
| integers. Relatedly, and even more to the point: computability
| is about whether a computer program exists to map inputs to
| outputs in a specified way; it says nothing about how hard it
| might be to choose or find or write that program. Writing the
| program could even require settling God's existence, for all
| the definition of computability cares.
| kazinator wrote:
| 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.
| pdonis wrote:
| _> 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.
| zeroonetwothree wrote:
| Computable doesn't mean it's easy to write down the
| implementation.
| pdonis wrote:
| 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.
| dash2 wrote:
| The comments on this article are like a flytrap for people with
| exactly the kind of misconception the article is talking about.
| xcanl wrote:
| 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 wrote:
| "Yes, the blog should consider reviewing its presentation
| style." from you know who.
| dash2 wrote:
| He's popularizing interesting but complicated maths. That's
| always gonna attract people who think they understand it, but
| don't.
| kragen wrote:
| 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
| ilya_m wrote:
| > the other 99.99% of academics should reconsider their
| presentation style; the reason their papers don't spark
| such arguments is that they've given up on educating the
| ignorant the way scott does
|
| I don't see how the second part of the sentence implies the
| first. The primary role of academics is generating new
| knowledge. Educating the ignorant is a public service that
| few are willing or able to do. Scott Aaronson deserves a
| lot of credit for dedicating so much energy to his blog, it
| does not mean that 99.99% of his peers are wrong in
| focusing on advancing the frontier of knowledge.
| kragen wrote:
| it's a public service that nobody else is able to do, and
| if nobody does it, the result is catastrophe: legislating
| the value of pi, creationism in schools, prohibitions on
| glassware and borax and teflon, lynchings for witchcraft,
| acid attacks on girls for attending school, the
| ransomware pandemic, boko haram, the cambodian mass
| executions for wearing glasses or speaking french
|
| i won't go so far as to claim that this imposes an
| individual moral obligation on every academic--that would
| be a variety of consquentialism with many consequences i
| shrink from--but at least it would be good to figure out
| how to demarginalize what scott is doing
| empath75 wrote:
| 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 wrote:
| > It also doesn't really matter if a statement is provable in
| theory or not. Whether or not it's possible to prove that
| P?=NP, it is either true or it's false and it has always been
| either true or false, and one of those two programs is
| correct.
|
| This is a pretty philosophically extremist statement (relying
| on a hardcore version of Platonism) and with my handle I
| can't just let it stand unchallenged. :)
|
| I'm actually somewhat more sympathetic to excluded middle for
| P?=NP than for some other statements, so let's start
| elsewhere. I don't think it's at all obvious that the
| continuum hypothesis is, and always has been, either true or
| false. We know it's independent of ZFC, of course, and there
| are sensible "extra" axioms that would resolve it in opposite
| directions (e.g. V=L vs. MM). In order to believe that
| there's a fact of the matter you need to posit a very well-
| populated Platonic realm, despite not needing that kind of
| philosophical commitment to do mathematics.
|
| Well, maybe P?=NP is just simpler than CH. It probably is!
| But you can imagine a case where it isn't; e.g. if there
| exists an algorithm for 3-SAT (call it Algorithm A) which can
| be proved to be asymptotically optimal, and which runs in
| O(n^10^100) time if !CH, and exponential time if CH. Then the
| P?=NP question would be equivalent to CH, and you should have
| the same beliefs about its truth value. If you're like me,
| that means you're skeptical that it has a well-defined truth
| value "for all time" at all.
| empath75 wrote:
| In that case, either of "return false" or "return true" are
| valid computable functions depending on the domain you're
| operating in (with CH or without it).
|
| It's the same essentially as a function that returns true
| if any two lines will eventually intersect. The correct
| answer depends on whether you're in curved space or not.
| That the correct answer depends on the domain or axioms
| doesn't make it non computable.
|
| There's just no case where a constant function isn't
| computable in the technical sense.
| Aeium wrote:
| _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.
| umanwizard wrote:
| Whether it's possible to prove it halts or not is
| irrelevant. It either does halt, or not. Whether a human
| can prove that a function has a particular value doesn't
| change whether that function is computable in the technical
| sense being used here.
| mananaysiempre wrote:
| If you're using ZFC, there is (TFA mentions the state of
| the art is BB(745); Yedida and Aaronson's original work on
| BB(8000)[1] is quite fun to read from a programmer's point
| of view). But the second form still exists (if you accept
| excluded middle)--you just can't prove which one it is!
|
| Specifically, ZFC is consistent iff ZFC+"Y&A's machine does
| halt" is consistent iff ZFC+"Y&A's machine never halts" is
| consistent (a theorem in a fairly weak ambient metalogic).
| So you _can_ take a stronger set theory that does prove the
| answer, it's just that thus far we have no reason to prefer
| theories that answer yes to theories that answer no.
|
| (You don't have to accept excluded middle, and it can on
| occasion be useful not to[2], but pragmatically you're
| going to have a lot of difficulties even with first-year
| calculus unless you do.)
|
| [1] https://scottaaronson.blog/?p=2725
|
| [2] https://www.ams.org/journals/bull/2017-54-03/S0273-0979
| -2016...
| feoren wrote:
| > What if there is a beaver that never halts or loops
|
| A Turing machine with finite states must eventually either
| halt or loop. Those are the only options, because there are
| only finitely many configurations it can be in, and each
| configuration completely determines the next.
|
| A "beaver" is defined to not loop. All "beavers" must halt,
| because otherwise they're just not considered for BB(n).
| All the challenge is in proving whether a given Turing
| machine does (or does not) halt, and therefore must not (or
| must) loop. Proving "halt" or "loop" proves the other one.
|
| Yes, the function `busy_beaver_6() = 576125642131574254..."
| must exist.
| umanwizard wrote:
| I disagree unless you state what you mean by "loop". If
| it's just "repeat a state" then any 6-state TM "loops" or
| halts after at most 6 turns... and many that "loop" will
| eventually halt.
|
| There are infinitely many configurations if you consider
| the tape.
|
| It is still true, of course, that every Turing machine
| either halts on a given input, or doesn't.
| samatman wrote:
| I don't understand what you're disagreeing with. "loop"
| has a well-understood meaning here: return to an
| identical state. Not a similar one, identical. Because if
| it does that once, being a deterministic automaton, it
| will do so an infinite number of times without halting.
| umanwizard wrote:
| In determining whether you've returned to an identical
| state, are you including the tape? Or just the machine
| states?
|
| If you are including the tape, it's not true that there
| are finitely many states. If you're not, then "looping"
| as you've defined it is not excluded from the definition
| of the busy beaver problem, and does not imply that the
| machine never halts.
| samatman wrote:
| > _If you are including the tape, it 's not true that
| there are finitely many states._
|
| An infinite Turing tape can be in an identical state,
| however. The number of states don't have to be finite. If
| a Turing machine returns to an identical state, it will
| not halt. That's what we call looping.
|
| An example of an identical state is 1 at indexes 3 and 5
| of the tape, and 0 everywhere else.
|
| Another example is the Brainfuck program `++[]`. This
| trivially returns repeatedly to a given finite state.
| umanwizard wrote:
| Yes, but the original claim was that non-halting TMs must
| loop because the number of configurations is finite. But
| that's not true.
|
| Here's an example of a bf program that never returns to
| an identical configuration, and also never halts. The
| corresponding TM would be excluded from consideration for
| the busy beaver number, despite never "looping" according
| to your definition. +[+]
|
| A similar-in-spirit TM (with tape alphabet {0, 1}, and
| only one machine state) is the one that unconditionally
| sets the current symbol to 1 and then moves to the right.
| This never encounters the same configuration twice (the
| number of 1s on the tape increases each turn) and also
| never halts.
| ilya_m wrote:
| > A Turing machine with finite states must eventually
| either halt or loop. Those are the only options, because
| there are only finitely many configurations it can be in,
| and each configuration completely determines the next.
|
| The Turing machine writes and reads from an infinite
| tape, and as such, the number of configurations (the
| machine's state + tape) is countably infinite.
| poikroequ wrote:
| > Could the P versus NP question itself be NP-hard, and therefore
| impossible to solve?
|
| Is there a way to formulate or rephrase this such that we could
| effectively ask this question? I'm thinking like some way of
| formally encoding the question (does P=NP?) that could be plugged
| into a turing machine which then computes the answer.
| mrkeen wrote:
| 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 wrote:
| 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 wrote:
| I think "effectively ask this question" is quite ambiguous
| here. The original question implying NP-hard problems are
| "impossible to solve", which already makes no sense.
| pvillano wrote:
| Pulling intent out of a invalid statement is difficult but I
| think the intent is something like
|
| > Could the P versus NP question itself be [mathy-difficult
| in a way] that makes it impossible [for humanity to know the
| answer]?
|
| Which becomes a family of interesting questions when you
| substitute exact expressions for the bracketed natural
| language
| zeroonetwothree wrote:
| Single values cannot be "NP Hard". Hardness applies to a class
| of problems. So it may be NP Hard to compute "prove or disprove
| X" but this says nothing for any individual value of X.
|
| Similarly the traveling salesman problem is NP Hard but there
| are inputs that have trivial outputs.
| wodenokoto wrote:
| I don't get the god thing. Why is f computable, just because we
| know the possible outputs? By that logic the halting problem is
| computable because h(f) is either 1 or 0.
| alexey-salmin wrote:
| 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 p, 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 p,
| 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 S) is computable.
| E.g., for each natural number n, there exists an algorithm that
| computes the finite sequence S(0), S(1), S(2), ..., S(n) -- in
| contrast to the fact that there is no algorithm that computes
| the entire S-sequence, i.e. S(n) for all n. Thus, "Print 0, 1,
| 4, 6, 13" is a trivial algorithm to compute S(0), S(1), S(2),
| S(3), S(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 S(0), S(1), S(2), ..., S(n).
|
| [1] https://en.wikipedia.org/wiki/Computable_function
| empath75 wrote:
| 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.
| umanwizard wrote:
| > 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".
| wodenokoto wrote:
| 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?
| housecarpenter wrote:
| Yes, that's right.
| minkzilla wrote:
| 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!
| wodenokoto wrote:
| I like this explanation, but how would you apply that logic
| to If (god does exist) Return
| true Else Return False
| minkzilla wrote:
| I guess I misread the first part of the article while
| skimming. I think the key is this paragraph
| computability is about whether a computer program exists to
| map inputs to outputs in a specified way; it says nothing
| about how hard it might be to choose or find or write that
| program. Writing the program could even require settling
| God's existence, for all the definition of computability
| cares.
|
| I guess in this case God's existence needs to be a compile
| time constant.
|
| I saw it elsewhere in the comments but I think
| computability as defined in Computer Science and used by
| the author is more strict a definition than you or I
| are/were thinking, and that is really the main point of the
| article. People confuse computability with "can it be
| computed". Missing values (such as knowledge of God's
| existence or null values) mean you can not computer
| something but that is a different thing.
| pdonis wrote:
| _> 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.
| mistercow wrote:
| I think this is one of the things that makes the undecidability
| of the halting problem hard to grok. You _want_ to say "there are
| certain machines so complicated that it's impossible for a
| machine to tell whether they halt or not." But between the
| trivial programs "return true" and "return false", one of them
| gives the correct answer for any machine and input you throw at
| them.
|
| You want to object "but those programs don't _know_ anything
| about Turing machines. They don't count!" But that's not what
| decidability is about. You might want to think something like
| "ok, but figuring out which of those programs gives the right
| answer is undecidable," but again, no, that has a defined true or
| false answer too. The problem can only become undecidable once
| it's extended to an infinite set of machine /input combinations.
| mananaysiempre wrote:
| 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 wrote:
| I find responding to informally posed questions which are not
| self consistent with answers of the form,
|
| > This is the best way I can think to formalize your question.
| These are some ways it's different than what you asked, but
| here's why I think it close enough, and this is the answer in
| this case.
|
| are usually better than asserting,
|
| > There's absolutely no way to formalize your question. It's
| utter nonsense and I won't answer it.
|
| Even when, to the answerer, the proposed formalization seems much
| different from the informal question, the questioner is often
| satisfied with the answer.
| Xcelerate wrote:
| Yeah... I'm normally a huge fan of his posts, but this one
| seems more like venting about the number of cranks he has to
| deal with in the comments to his blog. Not that I blame him
| haha
| zeroonetwothree wrote:
| Unfortunately in this case the latter version doesn't make
| sense. There is no way to reformulate it.
| pvillano wrote:
| 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 wrote:
| 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 wrote:
| It seems to me that topics TCS and complexity theory are to CS
| undergrads and CS-adjacent professionals akin to how topics in
| particle physics are to the layman. We've heard of the word NP-
| hard like how the layman has heard of entanglement, and then
| we've substituted working through the mathematical development
| with terrible pop analogies and fanciful imagination.
| jvanderbot wrote:
| 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 wrote:
| A fair point in general, but when reading Scott Aaronson's
| blog quoting a textbook called Introduction to the Theory of
| Computation, we should be prepared for TCS jargon.
|
| And people curious about P versus NP or Busy Beaver should
| begin by learning some basic TCS, so they can understand what
| people who study the problems professionally are saying.
| jvanderbot wrote:
| I definitely read his article as being a sort of "people
| keep asking me" as though they approach him in his daily
| life / his uncle wants to know. I suppose another reading
| of it is that he's referring mostly to comments on his
| blog, in which case this makes sense.
| namaria wrote:
| 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.
| jvanderbot wrote:
| Sure, I'm getting mixed up in "debate between experts" and
| "pedagogical difficulties with laypeople". TFA is meant to
| be discussing the former case, and I read it as the latter.
| Xcelerate wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| Similar to how all real-world computers have a finite number of
| states and are thus not Turing machines, but rather finite
| state machines.
| jvanderbot wrote:
| 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 wrote:
| Your example function just always never prints so that makes
| things easier.
| joenot443 wrote:
| Why's that?
| jvanderbot wrote:
| GP is joking about the certainty of there being / not being
| a god
| zeroonetwothree wrote:
| Computable has a standard definition in CS. It's not like the
| author made it up or something.
| jvanderbot wrote:
| 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.
| umanwizard wrote:
| The post is on a theoretical CS blog, talking about a
| question in a theoretical CS textbook. Why shouldn't we
| expect it to use theoretical CS jargon?
| bionhoward wrote:
| 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 Godel thinking to assume we can assign
| different numbers to zero and the logical not? If the Godel
| 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?) - Godel numbering zero
| (an integer) and logical not (a function) separately is a false
| difference because zero IS not (to the universe itself) --
|
| to say we can't form complete systems out of items we ourselves
| falsely separated in the first place is what the universal
| substrate, if it could speak, might call a "skill issue"
| kaba0 wrote:
| > 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 Godel 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)
| jcranmer wrote:
| 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 wrote:
| 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.
| jcranmer wrote:
| One of the key insights is that every program is
| representable as an integer, and you can map essentially
| any integer into a program. (If this seems strange, think
| of a file on a computer--traditionally a stream of bytes--
| as just a large base-256 integer.) This means we can
| iterate every possible program, as there are only a
| countably infinite number of programs.
|
| I should also note that this is required by our
| conventional definition of program (specifically, a Turing
| machine). There's definitely models of computation more
| powerful than Turing machines, but these are not believed
| to be physically realizable (the Church-Turing Thesis); in
| any case, the diagonalization form of the proof of the
| halting problem's uncomputability indicates that these more
| powerful methods are also susceptible to their own variant
| of the halting problem.
| samatman wrote:
| 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
| rssoconnor wrote:
| In my experience, I find that constructive mathematics better
| aligns with peoples intuitions here rather than classical
| computer science.
|
| For example, we don't (yet) have a proof that there exists
| (constructively) a program that that prints out the answer to the
| P=NP problem.
|
| I had some commentary in my thesis about this issue with regards
| to computable Julia sets. Mark Braverman proved that every
| (quadratic) Julia set is computable. But, as he notes, his proof
| isn't uniformly computable. Instead he develops 5 machines that
| attempt to draw various sets (at whatever desired resolution)
| given the parameter for the Julia set desired. For each Julia
| set, one of these 5 machines will correctly draw the set.
|
| When doing constructive mathematics, the constructive notion of a
| compact set roughly corresponds to being a computable set in the
| sense we need for computable Julia sets. We cannot constructively
| prove that every (quadratic) Julia set is compact. Instead we
| have to divide the complex plane of possible parameters of the
| Julia set into multiple regions, and within each of those regions
| we can prove all of the corresponding Julia sets are compact.
|
| In classical mathematics the union of all these regions is the
| entire complex plane, but this result doesn't hold
| constructively. Analogously, in classical mathematics the union
| of the positive reals, and the non-positive reals is the whole
| real line; however, again, this result doesn't hold
| constructively.
|
| The constructive mathematics approach clearly states exactly what
| additional information is need to actually realize the
| computation of a (quadratic) Julia set: that is you must state in
| which of these regions of the complex plane you given parameter
| belongs to, which in turn tells you which of these 5 machines you
| need to run to get actually get the image you want. This is a
| much more satisfying answer.
| Xcelerate wrote:
| > 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)?
| aeneasmackenzie wrote:
| 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.
| Aeium wrote:
| 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?
| umanwizard wrote:
| No, the definition of the busy beaver problem excludes any
| program that never halts, regardless of how complex its
| behavior is.
|
| > How would the answer for a specific integer be computable if
| it's impossible to determine what the value for the function of
| is for that integer?
|
| Can you say precisely what you mean by "computable"? I suspect
| you're using an intuitive definition that's different from the
| author's formal definition.
| Aeium wrote:
| 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?
| umanwizard wrote:
| > What if a similar proof is made for a Beaver?
|
| Then we will never be able to find the Nth beaver number
| for the corresponding N.
|
| That doesn't mean it is undefined or uncomputable. It
| actually has nothing to do with it. There is a computer
| program that prints out the number of hairs on my head.
| Doesn't matter that you will never know how to write that
| program.
|
| Again, uncomputable is being used in a technical sense here
| which is why I asked you what definition of "computable"
| you're using.
| elijaht wrote:
| "Probably doesn't halt" is ill defined, it either halts or
| it doesn't. In either case, computability of that number is
| completely separate from whether we can prove that number
| is BB(N) or decide whether a given beaver halts.
| Additionally, the way the busy beaver function is defined
| ensures it has a defined integer output. Computability is
| just our ability to construct a machine which would print
| out that number. We can clearly do that for any integer
| immibis wrote:
| 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.
| Aeium wrote:
| 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.
| rdlw wrote:
| > The busy beaver is not defined entirely by halting vs
| not-halting.
|
| > Looping beavers are excluded as well.
|
| Looping beavers do not halt.
|
| > there is a middle ground between non-halting and provably
| non-halting
|
| Yes, there are turing machines that encode mathematical
| theorems which are independent of ZFC, meaning they cannot
| be proven to halt or not to halt. The state-of-the-art is
| BB(748), which is known to be independent [0].
|
| There are also much smaller known turing machines which
| encode classically difficult math problems, like the
| Goldbach conjecture [1]. This means that the value of
| BB(27) cannot be proven until the Goldbach conjecture is
| proven or disproven, as until that is done, we will always
| have something like "BB(27) is N unless the Goldbach
| conjecture is false".
|
| However, our inability to prove these things does not
| change the fact that they have specific values. To stick
| with the BB(27) example, say that it seems we've narrowed
| it down to some huge number A, _or_ a number dependent on
| the first number for which Goldbach does not hold. Call
| that second number B. We may be unable to find the value of
| B (doing so would disprove Goldbach), but it is still a
| specific number. There still exists a concrete value for
| BB(27)--it 's A if Goldbach is true, and it's B is Goldbach
| is false.
|
| [0] https://www.ingo-blechschmidt.eu/assets/bachelor-
| thesis-unde...
|
| [1] https://gist.github.com/anonymous/a64213f391339236c2fe3
| 1f874... This 27-state machine halts when it finds a
| counterexample to the Goldbach conjecture.
| immibis wrote:
| Busy beavers are the machines in some size class which run
| the longest, then halt. They may be alternatively defined
| as the ones which produce the most output, then halt.
| Machines which obviously loop are excluded, and so are
| machines that non-obviously loop - for example ones that
| loop until they prove the Riemann hypothesis are excluded
| if the Riemann hypothesis is false and the proof system is
| consistent.
| jcranmer wrote:
| 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.
| elijaht wrote:
| 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 wrote:
| Sipser is just taking advantage of most people not understanding
| the difference between computation and empirical investigation.
| "Does God exist" is probably an unanswerable question, but that
| is beside the point. Answering it is not within the realm of
| computation at all. Computation is simply a procedure that maps
| inputs to outputs. In this case, whether or not God exists is one
| of the inputs. It's tripping people up because we can't actually
| know the value of the input, but the program still exists and is
| a trivial program. Replace it with some other binary empirical
| question.
|
| Let f: {0,1}* -> {0,1} = 1 if Paris contains at least one porta
| potty and 0 if it does not. This one is both computatable and you
| can actually run it with a true input. The one about God is also
| computable but can only be run with a guessed input. You can't
| guarantee the output corresponds in any meaningful way to the
| universe you live in, but it is still a computable function.
|
| Maybe it's better to just consider f: {0,1}* -> {0,1}. "God
| exists" and "God does not exist" are both possible bit strings on
| their own. Can a program exists that outputs 0 if it gets one of
| these inputs and 1 if it gets the other? Of course it can. It
| doesn't matter if the input is empirically true or not.
| pdonis wrote:
| 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 wrote:
| 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.
| renewiltord wrote:
| 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.
___________________________________________________________________
(page generated 2024-07-09 23:01 UTC)