3 ms·
If Tetris (with an infinite board) is Turing complete, then how about building an OS from Tetris? (It seems for certain problems it is NP-complete!) https://li
by dudeinjapan 6y ago
If Tetris (with an infinite board) is Turing complete, then how about building an OS from Tetris?
(It seems for certain problems it is NP-complete!)
https://liacs.leidenuniv.nl/~kosterswa/tetris/tot.pdf https://liacs.leidenuniv.nl/~kosterswa/tetris/tot.pdf
- eru 6y agoIf you already know that it's Turing complete, isn't it automatically also NP-complete? (I also read the paper: to clarify, they are referring to different problems you can build on top of Tetris, and prove some of them NP-complete and some Turing complete. (They don't mention Turing completeness directly, but they do a reduction to Post's correspondence problem.))
- dudeinjapan 6y agoRight, my comment was the other way around; I don't know whether infinite Tetris is Turing complete.
- eru 6y agoRunning a Turing machine reduces to Post's correspondence problem (which the paper shows reduces to answering some peculiar questions about Tetris).
- elcomet 6y agoTuring 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 6y agoSorry 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 6y agoYou're right, sorry about the lack of precision