Hao
Hao is a language based on placing sets of Wang tiles on a 1-D tape discovered by User:Orby in April 2018.
Hao
A Hao machine consists of a tile set and a tape.
Tiles
Each tile has a color for each cardinal direction (north, south, east, and west). If we map each color we wish to use to a unique non-negative integer, then we can use the Cantor pairing function
f(x, y) := ((x + y) * (x + y + 1)) / 2 + y
to assign each tile a unique non-negative integer. Thus, we define the Hao number of a tile as
f(n, f(s, f(e, w))
where n, s, e, and w are the non-negative integers we've mapped to the color on the north, south, east, and west sides of the tile, respectively. See here for a Javascript implementation to help you map back and forth.
Tape
In theory, the tape is unbounded on both sides. In practice, the tape contains a finite number of cells. Each cell of the tape is occupied by a tile from the tile set. Tiles may not be rotated or reoriented in any way. The east color of cell i must match the west color of cell i + 1. In the case of a finite tape, boundary conditions are periodic (that is, if there are n cells, then the west color of cell 0 must match the east color of cell n).
Computing a step
When a step is computed, each cell is overwritten in such a manner that the south color of the current value matches the north color of the new value (while preserving the constraint on the east and west colors of adjacent cells). If there is not a unique successor for the current state of the tape, the machine halts.
Turing completeness
A Hao machine is capable of simulating the Turing complete one dimensional cellular automaton rule 110, and therefore is itself Turing complete. Consider the tile set S = {229, 44, 3158, 54, 1538, 1539, 14876, 18144}
If we consider the north color of each tile to be equivalent to the color of the cellular automaton in that cell, then there is a unique Hao tape representation for each automaton state. If we compute successive steps in Hao, we are in fact simulating rule 110.