首页 | 本学科首页   官方微博 | 高级检索  
     


Tetris and decidability
Authors:Hendrik Jan Hoogeboom  Walter A. Kosters
Affiliation:Leiden Institute of Advanced Computer Science (LIACS), Universiteit Leiden, The Netherlands
Abstract:We consider a variant of Tetris where the sequence of pieces (together with their orientation and horizontal position, which cannot be changed anymore) is generated by a finite state automaton. We show that it is undecidable, given such an automaton, and starting from an empty game board, whether one of the generated sequences leaves an empty game board. This is contrasted with more common situations where piece translations and rotations are allowed.
Keywords:Tetris   Decidability   Theory of computation
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号