It can be sort of unintuitive how the concept of computability necessarily involves infinity.
For example: does there exist an algorithm that computes the Kolmogorov complexity, K(s), of string s for arbitrary s? It is well-known that the answer is "no" — there is no Turing machine that takes as input a string of arbitrary length and computes K(s). The proof is quite brief and involves the halting problem.
But if we ask a similar question: does there exist an algorithm that computes K(s) of string s for arbitrary string s with length < n? The answer is yes! And there exists such an algorithm for any value of n.
How is that possible? Think about it for a second, because the answer is going to disappoint you: simply create a Turing machine that consists of a giant lookup table for all 2^n possible strings that prints the value of K(s) for each one.
But wait, that's cheating! Maybe so, but any specific implementation of the algorithm has a finite description. And by definition, K(s) is also finite for all s. While it's true that I haven't provided any particular method for determining the value of K(s) for all 2^n strings in order to actually create the lookup table, that doesn't matter. Such an algorithm nevertheless exists, regardless of whether you can find it or prove that it does what you want it to.
So in a sense, finite questions about a finite number of things are sort of uninteresting from the perspective of computability, because you can always write a program that just prints the answer for all of those things (how quickly it does this is another matter). But when you extend the question to an infinite number of things, computability becomes much more interesting, because you don't know whether something finite can provide answers to questions about an infinite number of things.
This description makes it sounds like large areas of computer science are just goofy, meaningless, games.
But what's really happening is that "infinity" is standing in for "approximate, eventual, steady state behavior for sufficiently large N, larger than any specific one-off gimmick you might think of".
In the real world, though, those gimmicks are important, and the constants and low-order terms ignored in a Big-O comparison are important to real world performance.
There is constant tension between "big enough problem that the contant factors don't matter", and "small enough problem that it conforms to the (often implicit) of what 'constant' means (example: 32bit ints masquerading as integers)"
> 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).
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!
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).
In my experience, I find that constructive mathematics better aligns with peoples intuitions here rather than classical computer science.
For example, we don't (yet) have a proof that there exists (constructively) a program that that prints out the answer to the P=NP problem.
I had some commentary in my thesis about this issue with regards to computable Julia sets. Mark Braverman proved that every (quadratic) Julia set is computable. But, as he notes, his proof isn't uniformly computable. Instead he develops 5 machines that attempt to draw various sets (at whatever desired resolution) given the parameter for the Julia set desired. For each Julia set, one of these 5 machines will correctly draw the set.
When doing constructive mathematics, the constructive notion of a compact set roughly corresponds to being a computable set in the sense we need for computable Julia sets. We cannot constructively prove that every (quadratic) Julia set is compact. Instead we have to divide the complex plane of possible parameters of the Julia set into multiple regions, and within each of those regions we can prove all of the corresponding Julia sets are compact.
In classical mathematics the union of all these regions is the entire complex plane, but this result doesn't hold constructively. Analogously, in classical mathematics the union of the positive reals, and the non-positive reals is the whole real line; however, again, this result doesn't hold constructively.
The constructive mathematics approach clearly states exactly what additional information is need to actually realize the computation of a (quadratic) Julia set: that is you must state in which of these regions of the complex plane you given parameter belongs to, which in turn tells you which of these 5 machines you need to run to get actually get the image you want. This is a much more satisfying answer.
And in the P=?NP case Aaronson uses, the answer wouldn't be "P=NP" (a classical answer -- totally useless) but the actual function NP->P.
People just instinctively know that you need to know which side of the disjunction you're on, and they haven't been trained in classical logic to forget it.
> 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)?
I think this is one of the things that makes the undecidability of the halting problem hard to grok. You want to say “there are certain machines so complicated that it’s impossible for a machine to tell whether they halt or not.” But between the trivial programs “return true” and “return false”, one of them gives the correct answer for any machine and input you throw at them.
You want to object “but those programs don’t know anything about Turing machines. They don’t count!” But that’s not what decidability is about. You might want to think something like “ok, but figuring out which of those programs gives the right answer is undecidable,” but again, no, that has a defined true or false answer too. The problem can only become undecidable once it’s extended to an infinite set of machine/input combinations.
Other problems that only arise on families of objects can be similarly difficult to grok for beginners. E.g.: any given finite-dimensional vector space is isomorphic to its dual and to its double dual in many ways, but for the latter you can choose a (“natural”) isomorphism consistently over all such spaces, while for the former you can’t. “Why isn’t it naturally isomorphic? The bases are of the same length! What do we care if it depends on the basis or no? Why do we not care all those other proofs choose bases then?”
I think the problem with the wording is that it requires modal logic:
> Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? (Hint: The answer does not depend on your religious beliefs.)
The precise question is would f be computable (i.e. exists a Turing machine M st. f(x) = M(x) everywhere).
Would f be computable? Yes, because in either world there is a trivial TM, M = 1_M or M = 0_M. In contrast, the originally worded question "Is f computable" is a modally invalid question, analogous to the Sleeping Beauty or Red Envelope paradoxes. It's like, grammatically incorrect.
Another way to look at this is the dependency on God or some potentially real fact is more like a compiler directive or pragma whose parameters get filled in later but prior to use, so the question when asked correctly is just about unpacking the strict definitions of function and computable, both of which are explicitly defined in Sipser.
My reaction was somewhat similar, and I posted along those lines in the comments to Aaronson's post. As I said there, the question is not about a function f that could call the constant 1 function or the constant 0 function depending on whether God exists. The question is about a label f whose referent will be either the constant 1 function or the constant 0 function, we just don't know which unless we can figure out whether or not God exists. To me the question isn't actually about computability at all (the computability of both of the constant functions is trivial), it's about labels.
> 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?
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.
Sipser is just taking advantage of most people not understanding the difference between computation and empirical investigation. "Does God exist" is probably an unanswerable question, but that is beside the point. Answering it is not within the realm of computation at all. Computation is simply a procedure that maps inputs to outputs. In this case, whether or not God exists is one of the inputs. It's tripping people up because we can't actually know the value of the input, but the program still exists and is a trivial program. Replace it with some other binary empirical question.
Let f: {0,1}* -> {0,1} = 1 if Paris contains at least one porta potty and 0 if it does not. This one is both computatable and you can actually run it with a true input. The one about God is also computable but can only be run with a guessed input. You can't guarantee the output corresponds in any meaningful way to the universe you live in, but it is still a computable function.
Maybe it's better to just consider f: {0,1}* -> {0,1}. "God exists" and "God does not exist" are both possible bit strings on their own. Can a program exists that outputs 0 if it gets one of these inputs and 1 if it gets the other? Of course it can. It doesn't matter if the input is empirically true or not.
This always happens because mathematicians and computer scientists use shorthand descriptions that elide the details for ease of conversation. It's no different than saying that you're "multiplying by dx on both sides". "Is the traveling salesman problem NP-hard?" is talking about family of problems, not specifically an instance of it. If you fix the specific graph, then obviously it's not NP-hard since there's no N.
It's so trivially obvious when you know this that it isn't worth talking about. It is also completely unreachable for many people who don't know what these terms mean.
I have, in the past, had a misconception of this shape in a different field. In my case, it was my belief in DNA as code that is executed by things that message-pass between each other sometimes directly through the substrate and sometimes by modifying the DNA. Overall, this isn't a useless model but I needed to know when to not get addicted to it.
To biologists with mathematical backgrounds, it's obviously wrong to just take the TM execution of DNA as a model. To me, it was less so.
Decidability, computability, existence, fruit, all have different meanings in an academic context and in a everyday context, and trying to use intuitions from the everyday meanings in an academic context leads to these "stupid questions".
[big number from Wikipedia] "exists" and is "computable" in an academic sense, even though its digits cannot fit in our universe.
The wording is the confusing bit, if you're not being careful.
> Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? (Hint: The answer does not depend on your religious beliefs.) [emphasis mine]
The alternative is not part of the function. The function f does not branch based on the value of "God exists". The branch is in the metalanguage. We don't know whether f = 0 or f = 1, but whichever it is, it is computable because both possible functions are computable.
But, I would go further: if f did include the branch, and the domain of the function is 0 (God doesn't exist) and 1 (God does exist), then we still have a computable function in the sense that we can compute a result for each value of the domain.
The confusion effectively is a matter of pushing a free variable whose value is taken to be unknown into the branch condition in f.
> If you’re still tempted to quibble, then consider the following parallel question:
> Let n equal 3 if God exists, or 5 if God does not exist. Is n prime?
Sure, I'll happily quibble! You're using excluded middle to assert that n is either 3 or 5, but you haven't justified that excluded middle holds for the proposition "God exists".
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.
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!
>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".
It seems to me that topics TCS and complexity theory are to CS undergrads and CS-adjacent professionals akin to how topics in particle physics are to the layman. We've heard of the word NP-hard like how the layman has heard of entanglement, and then we've substituted working through the mathematical development with terrible pop analogies and fanciful imagination.
Sure, but there's no reason to think that everyone now has to use the very strict definition of "Computable", when it has a colloquial definition that makes perfect sense (a computer can do it).
It could be Author chose (due to their extensive training) their (very strict!) definition of computable, then wrote an entire article about their specific definition of a word, and lambasted the world for asking dumb questions using a different definition of the same word, and refusing to elaborate.
This honestly happens all the time at work, when talking to academics, or even talking to laypersons. It's hard to establish common nomenclature, and drawing a line in the sand at their nomenclature and asking people to catch up is exhausting.
It's not related to the post at hand, but the way selected text is highlighted on this blog is quite bad - only the font color is changed, not the background. Not only is it pretty unintuitive, it also makes it impossible to see if you selected any non-printable characters such as spaces or newlines.
What if we replace P={god exists} with P={there is a cardinality between integers and reals}?
I think some people think of “god exists” as unknowable, or undefinable, or ill-defined, etc. But the “riddle” requires P to be exactly true or false. Seems one of the pitfalls of mixing natural language with mathematics.
I don’t get the god thing. Why is f computable, just because we know the possible outputs? By that logic the halting problem is computable because h(f) is either 1 or 0.
This is one of the larger cognitive holes in human cognition. "If (undecidable A), then X, and if (not undecidable A) then X" is not just a math problem. I've seen it freeze entire teams of people of people in real life, in real business meetings. It is a common component of the more advanced "a guy wears a red hat if it is raining and a blue hat if it is not, you see someone wearing an orange hat, is he a cannibal?" riddles. It can inform your investment strategy. It can resolve even debates with your significant other when you say "hang on, if we go with your reason we do X and if we go with my reason we do X, let's just agree to do X each for our own reason".
It is very powerful to be able to advance past an uncertainty in some logic net and establish certainty on the other side. It's not a thing that comes up every day by any means, but it's a great tool to add to your belt.
And you can see even in this comment thread that it is not intuitive for people.
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.
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.
> 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.
Single values cannot be “NP Hard”. Hardness applies to a class of problems. So it may be NP Hard to compute “prove or disprove X” but this says nothing for any individual value of X.
Similarly the traveling salesman problem is NP Hard but there are inputs that have trivial outputs.
I realize now it doesn't make sense to ask if it's np-hard. Chess can be solved in constant time because there are finitely many board positions. But there are "generalized" versions of chess where the board and number of pieces can grow infinitely, then it makes sense to ask questions about complexity.
I guess I was thinking something along those lines. Perhaps if there's a way to "generalize" the P vs NP question, then we can hypothetically give some mildly meaningful answer about complexity.
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.
Thinking of a way for smart people to formally encode questions and hand them off to dumb computers is what led to the whole field of computing in the first place!
It seems that at least some theorists believe the P vs NP question isn't even provable using our current axioms, and that a proof would require new mathematics.
Pretty sure there's just a different notion of "Computable" going on. Author probably is choosing their (very strict!) definition of computable, whereas most folks would consider "Computable" to be "A computer could currently do it".
Regardless of whether yes, the given example
program is computable (it is), the general folks of the CS world probably understand it to be uncomputable because no computer could run that properly due to the impossible complexity in `if god`.
It does bother me a little bit when an academic writes an entire article about their specific definition of a word, then lambastes the world for asking dumb questions using a different definition of the same word, and refusing to elaborate.
Isn't saying BB(6) is computable the same as assuming that it is an integer?
I thought this was not necessarily true.
For example, one beaver might halt after some integer number of steps. This would be the potentially very large integer the author is referring to.
Another might go into an infinite loop, and clearly never halt.
My understanding of the where incomputability entered the discussion is the third possibility, that a beaver might have complex behavior that neither ever halts or ever loops.
The author touches on answering this, drawing the distinction that a specific answer might not be provable. But I'm not sure I understand.
How would the answer for a specific integer be computable if it's impossible to determine what the value for the function of is for that integer?
I find responding to informally posed questions which are not self consistent with answers of the form,
> This is the best way I can think to formalize your question. These are some ways it's different than what you asked, but here's why I think it close enough, and this is the answer in this case.
are usually better than asserting,
> There's absolutely no way to formalize your question. It's utter nonsense and I won't answer it.
Even when, to the answerer, the proposed formalization seems much different from the informal question, the questioner is often satisfied with the answer.
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
[+] [-] Xcelerate|1 year ago|reply
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.
[+] [-] gowld|1 year ago|reply
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)"
[+] [-] paulmd|1 year ago|reply
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).
[+] [-] aidenn0|1 year ago|reply
[+] [-] SAI_Peregrinus|1 year ago|reply
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!
[+] [-] jmount|1 year ago|reply
[+] [-] ffhhj|1 year ago|reply
Everything can be textualized, but making a complete interpreter for it requires understanding what intelligence really is.
[+] [-] rssoconnor|1 year ago|reply
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.
[+] [-] aeneasmackenzie|1 year ago|reply
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.
[+] [-] Xcelerate|1 year ago|reply
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)?
[+] [-] mistercow|1 year ago|reply
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|1 year ago|reply
[+] [-] calf|1 year ago|reply
> 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.
[+] [-] pdonis|1 year ago|reply
[+] [-] alexey-salmin|1 year ago|reply
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|1 year ago|reply
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.
[+] [-] bubblyworld|1 year ago|reply
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.
[+] [-] falcor84|1 year ago|reply
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.
[+] [-] nonameiguess|1 year ago|reply
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.
[+] [-] renewiltord|1 year ago|reply
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.
[+] [-] pvillano|1 year ago|reply
[big number from Wikipedia] "exists" and is "computable" in an academic sense, even though its digits cannot fit in our universe.
[+] [-] danielam|1 year ago|reply
> 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.
[+] [-] Smaug123|1 year ago|reply
> 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".
[+] [-] denotational|1 year ago|reply
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.
[+] [-] calf|1 year ago|reply
[+] [-] coldtea|1 year ago|reply
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".
[+] [-] jhanschoo|1 year ago|reply
[+] [-] jvanderbot|1 year ago|reply
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.
[+] [-] Sebb767|1 year ago|reply
[+] [-] ks2048|1 year ago|reply
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.
[+] [-] wodenokoto|1 year ago|reply
[+] [-] jerf|1 year ago|reply
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.
[+] [-] unknown|1 year ago|reply
[deleted]
[+] [-] calf|1 year ago|reply
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|1 year ago|reply
[+] [-] pdonis|1 year ago|reply
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.
[+] [-] poikroequ|1 year ago|reply
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.
[+] [-] zeroonetwothree|1 year ago|reply
Similarly the traveling salesman problem is NP Hard but there are inputs that have trivial outputs.
[+] [-] poikroequ|1 year ago|reply
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.
[+] [-] raincole|1 year ago|reply
[+] [-] mrkeen|1 year ago|reply
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|1 year ago|reply
[+] [-] jvanderbot|1 year ago|reply
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.
[+] [-] zeroonetwothree|1 year ago|reply
[+] [-] voxl|1 year ago|reply
[+] [-] Aeium|1 year ago|reply
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?
[+] [-] GrantMoyer|1 year ago|reply
> 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.
[+] [-] zeroonetwothree|1 year ago|reply
[+] [-] Xcelerate|1 year ago|reply
[+] [-] gowld|1 year ago|reply
It's ironic, since it's a mathematical study of languages.