4 ms·

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

by calf 2y ago

I think the problem with the wording is that it requires modal logic: > Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. Is f computable? (Hint: The answer does not depend on your religious beliefs.) The precise question is would f be computable (i.e. exists a Turing machine M st. f(x) = M(x) everywhere). Would f be computable? Yes, because in either world there is a trivial TM, M = 1_M or M = 0_M. In contrast, the originally worded question "Is f computable" is a modally invalid question, analogous to the Sleeping Beauty or Red Envelope paradoxes. It's like, grammatically incorrect. Another way to look at this is the dependency on God or some potentially real fact is more like a compiler directive or pragma whose parameters get filled in later but prior to use, so the question when asked correctly is just about unpacking the strict definitions of function and computable, both of which are explicitly defined in Sipser.

bubblyworld 2y ago
I think the point is that whatever predicate you fill in for "god", the implication is strictly speaking true in classical first-order logic (and probably many other logical systems too). The pragma analogy is a good one. Whether there exists such a predicate that conforms to your conception of God or not is a separate (non-mathematical) issue. I think it's a bit like the surprise people show when they learn that in classical logic a false statement implies everything. Mathematics has strict formal rules, and it's important to leave aside your preconceptions of the semantics of various words like "implies" and "if" when engaging in it.
alexey-salmin 2y ago
> In contrast, the originally worded question "Is f computable" is a modally invalid question, analogous to the Sleeping Beauty or Red Envelope paradoxes. It's like, grammatically incorrect. I don't think these paradoxes are relevant here. They only highlight a fact that application of the pure mathematical notion of probability to the actual reality is sometimes a non-trivial process. It's not a surprise, if you think of it the fact that the probability theory works _at all_ when applied to reality is extremely puzzling and has been a subject of various scientific and philosophical inquiries (see "probability interpretations"). Now the resolution you propose ("would" f be) doesn't seem to resolve anything. The purpose of "god" question is to force the reader to abstract away from a particular P-NP problem and understand that the whole concept of computability is useless for constant functions. So what you suggest is helpful only if you could also apply it to the original P-NP question, which I don't see so far. How the modalities approach come into play here, for a well-defined mathematical question?
- deleted 2y ago
  [deleted]
- gowld 2y ago
  You are further demonstrating how the cloudy semantics of the question and of casual semi-mathematical English language makes the problem harder than it needs to be. This is a huge problem in probability theory, as you allude to. Experts often forget how their preferred mathematical models drift away from lay language, and say things casually that don't really mean what they say.
furyofantares 2y ago
> Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. A slightly longer way to write this that I think would cause fewer parse errors is > Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or let f:{0,1}*→{0,1} be the constant 0 function if God does not exist.
falcor84 2y ago
I find the time-dependent version much more interesting: Let G:t∈ℝ⁺->{0,1} be the 1 if God exists at time t and 0 otherwise. EDIT: And of course this starts getting even more interesting when you analyze G in a non-inertial reference frame.
pdonis 2y ago
My reaction was somewhat similar, and I posted along those lines in the comments to Aaronson's post. As I said there, the question is not about a function f that could call the constant 1 function or the constant 0 function depending on whether God exists. The question is about a label f whose referent will be either the constant 1 function or the constant 0 function, we just don't know which unless we can figure out whether or not God exists. To me the question isn't actually about computability at all (the computability of both of the constant functions is trivial), it's about labels.
- gowld 2y ago
  The question is about computability, in the sense it's asking to recognize the possibility of an unknown (trivial) computable function. The "God stuff" is an distraction, with modal-logic ambiguities as another commenter wrote. I just wrote a regular expression (a real one, not PCRE), and then deleted it, and dissolved my computer in acid. It is completely impossible to ever know what I wrote. Was that function computable? Then I got another computer and wrote a program in a Turing Complete language, and deleted and dissolved that computer in acid. Was that program computable?

by calf 2y ago

bubblyworld 2y ago

I think the point is that whatever predicate you fill in for "god", the implication is strictly speaking true in classical first-order logic (and probably many other logical systems too). The pragma analogy is a good one. Whether there exists such a predicate that conforms to your conception of God or not is a separate (non-mathematical) issue. I think it's a bit like the surprise people show when they learn that in classical logic a false statement implies everything. Mathematics has strict formal rules, and it's important to leave aside your preconceptions of the semantics of various words like "implies" and "if" when engaging in it.

alexey-salmin 2y ago

> In contrast, the originally worded question "Is f computable" is a modally invalid question, analogous to the Sleeping Beauty or Red Envelope paradoxes. It's like, grammatically incorrect. I don't think these paradoxes are relevant here. They only highlight a fact that application of the pure mathematical notion of probability to the actual reality is sometimes a non-trivial process. It's not a surprise, if you think of it the fact that the probability theory works _at all_ when applied to reality is extremely puzzling and has been a subject of various scientific and philosophical inquiries (see "probability interpretations"). Now the resolution you propose ("would" f be) doesn't seem to resolve anything. The purpose of "god" question is to force the reader to abstract away from a particular P-NP problem and understand that the whole concept of computability is useless for constant functions. So what you suggest is helpful only if you could also apply it to the original P-NP question, which I don't see so far. How the modalities approach come into play here, for a well-defined mathematical question?

deleted 2y ago
[deleted]
gowld 2y ago
You are further demonstrating how the cloudy semantics of the question and of casual semi-mathematical English language makes the problem harder than it needs to be. This is a huge problem in probability theory, as you allude to. Experts often forget how their preferred mathematical models drift away from lay language, and say things casually that don't really mean what they say.

furyofantares 2y ago

> Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or the constant 0 function if God does not exist. A slightly longer way to write this that I think would cause fewer parse errors is > Let f:{0,1}*→{0,1} be the constant 1 function if God exists, or let f:{0,1}*→{0,1} be the constant 0 function if God does not exist.

falcor84 2y ago

I find the time-dependent version much more interesting: Let G:t∈ℝ⁺->{0,1} be the 1 if God exists at time t and 0 otherwise. EDIT: And of course this starts getting even more interesting when you analyze G in a non-inertial reference frame.

pdonis 2y ago

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

gowld 2y ago
The question is about computability, in the sense it's asking to recognize the possibility of an unknown (trivial) computable function. The "God stuff" is an distraction, with modal-logic ambiguities as another commenter wrote. I just wrote a regular expression (a real one, not PCRE), and then deleted it, and dissolved my computer in acid. It is completely impossible to ever know what I wrote. Was that function computable? Then I got another computer and wrote a program in a Turing Complete language, and deleted and dissolved that computer in acid. Was that program computable?