4 ms·
I think you are misunderstanding the article. The point is that when the game is considered as a computation, the problem of figuring out who is going to win is
by theoh 7y ago
I think you are misunderstanding the article. The point is that when the game is considered as a computation, the problem of figuring out who is going to win is not computable. Like every discussion of the halting problem, this is about whether or not a program exists that can calculate how some other specific program will behave.
- Sahhaese 7y agoI understood that, but question whether it's meaningful to say that is therefore more complex. Complexity theory just doesn't apply? (Or does it?)
- theoh 7y agoWell, it's at least as complex as a Turing machine. That's a statement of complexity. Maybe you are asking whether it is possible for the winning strategy of a very simple deterministic game to be non-computable. In other words, maybe there's a possible way of defining computability which is orthogonal to complexity. The CS definitions of both terms are closely connected to Turing machines, though. Can you imagine a simple deterministic game that couldn't be "solved" by an algorithm?
- babyloneleven 7y agoThe set of all problems that can be solved by a Turing machine if there's an answer (possibly hanging if there's no answer) sits at the top of the complexity hierarchy (it's equivalent to the recursively enumerable languages) The usual complexity classes of decision problems, such as P and NP, are subsets of what a Turing machine can solve, and so are weaker complexity classes.