From the blog post: 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...
From the blog post:
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.
And perhaps the same is true of random sequences? I'm reminded of: https://xkcd.com/221/
From the blog post:
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.
And perhaps the same is true of random sequences? I'm reminded of: https://xkcd.com/221/