Hao

From Esolang
Jump to navigation Jump to search

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

Rule 110 simulation (the north color of each cell is the color of the automaton and each row is a successive time step)

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}

Rule 110 tile set
Rule 110 tile set

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.