Turing Completeness and Sid Meier's Civilization
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916371332333568 |
|---|---|
| author | de Wynter, Adrian |
| author_facet | de Wynter, Adrian |
| contents | We prove that three strategy video games from the Sid Meier's Civilization series: Sid Meier's Civilization: Beyond Earth, Sid Meier's Civilization V, and Sid Meier's Civilization VI, are Turing complete. We achieve this by building three universal Turing machines-one for each game-using only the elements present in the games, and using their internal rules and mechanics as the transition function. The existence of such machines imply that under the assumptions made, the games are undecidable. We show constructions of these machines within a running game session, and we provide a sample execution of an algorithm-the three-state Busy Beaver-with one of our machines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_14647 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Turing Completeness and Sid Meier's Civilization de Wynter, Adrian Computational Complexity Artificial Intelligence We prove that three strategy video games from the Sid Meier's Civilization series: Sid Meier's Civilization: Beyond Earth, Sid Meier's Civilization V, and Sid Meier's Civilization VI, are Turing complete. We achieve this by building three universal Turing machines-one for each game-using only the elements present in the games, and using their internal rules and mechanics as the transition function. The existence of such machines imply that under the assumptions made, the games are undecidable. We show constructions of these machines within a running game session, and we provide a sample execution of an algorithm-the three-state Busy Beaver-with one of our machines. |
| title | Turing Completeness and Sid Meier's Civilization |
| topic | Computational Complexity Artificial Intelligence |
| url | https://arxiv.org/abs/2104.14647 |