4 ms·

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

by 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.

by evanb 2y ago

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.