4 ms·

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

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 2y ago
This is explicitly expounded upon in the original: > The deeper lesson Sipser was trying to impart is that the concept of computability applies to functions or infinite sequences, not to individual yes-or-no questions or individual integers. Relatedly, and even more to the point: computability is about whether a computer program exists to map inputs to outputs in a specified way; it says nothing about how hard it might be to choose or find or write that program. Writing the program could even require settling God’s existence, for all the definition of computability cares.
- kazinator 2y ago
  OK, so he has a concept of a time when the program is written and so on. Decisions about how the program is written, or what is to be written, can involve non-computable metaphysical questions.
  - evanb 2y ago
    Not exactly. There's no "compile time" or whatever. The point is that the computational complexity characterizes the difficulty of mapping an input to an output. Sorting a list can be done with lots of different algorithms; the obvious ones are O(n^2). But there exist O(n log n) algorithms, so the complexity of sorting is O(n log n) irrespective of whatever implementation you might imagine. That O(n log n) is true now and for all time.
    - kazinator 2y ago
      > computational complexity characterizes the difficulty of mapping an input to an output The question revolves around computability: can the input be mapped to an output; does the calculation terminate and the output emerge.
- pdonis 2y ago
  > This is explicitly expounded upon in the original Yes, it is, but you can have functions that output other functions, and the question of computability applies to those functions as well. Sure, the constant functions are trivially computable; but one can also ask about a function that outputs one or the other of those constant functions depending on whether God exists, or whether the halting problem is solvable, or whether the Riemann hypothesis is true, etc., etc., etc. And in a post that is supposed to be about computability, saying "Gotcha! Misconception!" when people start talking about those kinds of functions instead of the trivially computable constant functions explicitly mentioned in the question does not seem to me to be a good strategy. As I posted in response to Aaronson in the comments there, before concluding from someone's answer that they have a misconception about computability, you should first make sure they don't just have a simpler misconception about what question you were asking.
zeroonetwothree 2y ago
Computable doesn’t mean it’s easy to write down the implementation.
- kazinator 2y ago
  We can't start to talk about a function being computable until we have pinned down what it is; which usually means written it down.
pdonis 2y ago
I upvoted this post because it correctly describes an issue that I saw as well: the question isn't really about computability at all, it's about a label--at least, that's the question that Sipser (and Aaronson) intended to ask. But many readers (including me when I first read the question), seeing that the topic is supposedly computability and recognizing that the computability of the constant functions mentioned in the question is trivial, are going to consider the issue of computability of how the referent of the label is assigned, which is actually a more interesting computability question. Then, when the reader does this, Sipser and Aaronson say they're confusing religious beliefs with math.

evanb 2y ago

This is explicitly expounded upon in the original: > The deeper lesson Sipser was trying to impart is that the concept of computability applies to functions or infinite sequences, not to individual yes-or-no questions or individual integers. Relatedly, and even more to the point: computability is about whether a computer program exists to map inputs to outputs in a specified way; it says nothing about how hard it might be to choose or find or write that program. Writing the program could even require settling God’s existence, for all the definition of computability cares.

kazinator 2y ago
OK, so he has a concept of a time when the program is written and so on. Decisions about how the program is written, or what is to be written, can involve non-computable metaphysical questions.
- evanb 2y ago
  Not exactly. There's no "compile time" or whatever. The point is that the computational complexity characterizes the difficulty of mapping an input to an output. Sorting a list can be done with lots of different algorithms; the obvious ones are O(n^2). But there exist O(n log n) algorithms, so the complexity of sorting is O(n log n) irrespective of whatever implementation you might imagine. That O(n log n) is true now and for all time.
  - kazinator 2y ago
    > computational complexity characterizes the difficulty of mapping an input to an output The question revolves around computability: can the input be mapped to an output; does the calculation terminate and the output emerge.
pdonis 2y ago
> This is explicitly expounded upon in the original Yes, it is, but you can have functions that output other functions, and the question of computability applies to those functions as well. Sure, the constant functions are trivially computable; but one can also ask about a function that outputs one or the other of those constant functions depending on whether God exists, or whether the halting problem is solvable, or whether the Riemann hypothesis is true, etc., etc., etc. And in a post that is supposed to be about computability, saying "Gotcha! Misconception!" when people start talking about those kinds of functions instead of the trivially computable constant functions explicitly mentioned in the question does not seem to me to be a good strategy. As I posted in response to Aaronson in the comments there, before concluding from someone's answer that they have a misconception about computability, you should first make sure they don't just have a simpler misconception about what question you were asking.

zeroonetwothree 2y ago

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

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

pdonis 2y ago

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