On: Tetris-OS: An operating system that only plays Tet...

[elcomet]

Turing completeness refers to a language, while NP-completeness refers to an optimization problem.

So for it to be turing complete you first need to define a language based on tetris. For NP-completeness, it might just be solving the game.

[klyrs → elcomet]

Sorry to nitpick your nitpicking, but NP-completeness refers to decision problems (does there exist a solution with parameter k); optimization problems are often NP-Hard (find the minimum parameter k for which the decision problem has a solution).

[elcomet → klyrs]

You're right, sorry about the lack of precision