Universal Turing Machines Built Within Sid Meier's Civilization
Full-screen, in-game constructions of the Universal Turing Machines (UTMs) described in the paper "Turing Completeness and Sid Meier's Civilization".
All products, company names, brand names, trademarks, and images are properties of their respective owners. The images are used here under Fair Use for the educational purpose of illustrating mathematical theorems.
Contents
A \((10, 3)\)-UTM running within Sid Meier's Civilization: Beyond Earth, and built with the game's components and rules.
The UTM's tape (hexes in between the two black lines) is located to the left of the image, and runs from the top middle of the screen to the bottom left.
The tape contains Roads (symbols in \(Γ = \{\text{Road}, \text{Pillaged Road}\}\), denoted by an uppercase R in the image) on every hex, except one pillaged Road, denoted by P.
The UTM's head (the tape Worker and the Rover; leftmost triangle) is positioned in the middle of the screen, reading the symbol \(\text{Road}\).
The read is implicit, but can also be seen from the “Build Actions” menu (bottom left), which does not allow the player to build a \(\text{Road}\) on a hex that already contains this feature.
The UTM is in state \(q_2\), since the total Culture yield in this turn is \(C_t = 7\) (top right on the image, inside the box).
The state-tracking City (Tiangong) is located to the right, and has two Terrascapes (lush hexes on the right, outlined with hexagons) within its boundaries. Each Terrascape contributes \(3\) Culture, and the base Culture yield is \(C^∗ = 1\), so \(q_2 = (C_t − C_∗)/3 = 2\).
A \((10, 3)\)-UTM within Sid Meier's Civilization V, using only the game's components and rules, and in a running game session. In this case, the area reserved for state tracking is every hex owned by the City (Amsterdam).
The UTM's tape is the two parallel black lines to the right. It contains Roads and Railroads (symbols in \(Γ = \{\text{Road}, \text{Railroad}\}\); denoted in the image by uppercase R and RR, respectively).
The UTM's head (the tape Worker; rightmost triangle) is positioned in the middle of the screen, reading the symbol \(\text{Railroad}\).
It is in the state \(q_0\) since the City (left) has no Railroads built. The leftmost triangle is the state Worker.
A \((48, 2)\)-UTM within Sid Meier's Civilization VI, in a running game session. An idealized, more readable diagram can be found below.
Top image: the UTM in-game, with three Cities (Gwangju, Gyeongju, and Jeonju) acting as the states and two (Chuncheon and Pyongyang) as the tape. In this particular example, \(19\) Monasteries are being worked, so the UTM is in either the state \(q_{19b}\) or \(q_{19n}\). Depending as to whether the head must move right or left, Chuncheon will produce a new Citizen and expand the tape.
The tape at this moment contains two cells (hexes), with the head (triangle in the top, middle) located in Chuncheon. A closer look to the tape can be found in the image at the bottom left.
The states are tracked by the Monasteries (squares) in Gwangju, Gyeongju, and Jeonju. Idle and surplus Citizens work the Farms (circles) in the last two Cities. A close-up of the current state in Gwangju can be seen in the bottom-right image.
The state can be computed by noting that the base yield of Faith is \(6.4\), and each Monastery yields \(2\) Faith, for a total per-turn yield of \(43.4\) (middle number on the top right). In a running session, the game provides a breakdown of the Faith yields per-resource.
Bottom right image: Diagram of one of the three Cities (Gwangju) holding the state, with \(8\) Monasteries and \(11\) Farms. From the image, all \(7\) Monasteries belonging to the City, as well as \(6\) Farms, contain Workers. The top-right Monastery belongs to another City (Gyeongju) and cannot be managed on this screen. Some other improvements are also being worked, but do not contribute to the UTM.
Bottom left image: A sample of the tape being read. The head is positioned in the center hex, in between the City and a mountain (Worker not pictured). This image shows the placement of the Citizens, and it can be seen that the current symbol is \(\text{Is Being Worked}\). The hex adjacent to the head contains the \(\text{Not Being Worked}\) symbol, as no Citizen is currently assigned to work it.
Diagram of a \((48, 2)\)-UTM built with Sid Meier's Civilization VI components and rules. This is meant to accompany the in-game construction above and illustrate the principle behind the UTM.
The bottom two Cities (Gyeongju and Seoul) act as the state of the machine, and each of the Cities on the top strip contain two cells (hexes) from the tape.
The head position is tracked by the Worker, currently positioned in Yangsan. Refer to the figure above for a working in-game construction