Hacker News Reader

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.

View on HN

I understood that, but question whether it's meaningful to say that is therefore more complex. Complexity theory just doesn't apply? (Or does it?)

Well, 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?

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

Reply on news.ycombinator.com