Portal de Periódicos da CAPES

Turing Completeness and Sid Meier’s Civilization

2022; Institute of Electrical and Electronics Engineers; Volume: 15; Issue: 2 Linguagem: Inglês

10.1109/tg.2022.3166874

2475-1510

Adrian de Wynter,

Cellular Automata and Applications

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. We use these machines to prove the undecidability of these games under the unlimited turns, infinite map assumptions; and conclude by providing a sample execution of an algorithm--the three-state Busy Beaver--with one of our machines.