If one starts from the single-element set {1} then applying Union , Intersection and Complement one always gets either {} or {1} . And applying Complement[s, Intersection[a, b]] to these two elements gives the same results and same equivalences as a ⊼ b applied to True and False . … And the reason for this is that with s = {1, 2} the function Union[Complement[s, a], b] corresponding to a  b only ever gets to the 3 elements {{1}, {2}, {1, 2}} .

[Excluded blocks in] dynamical systems theory Sets of sequences in which a finite collection of blocks are excluded are sometimes known as finite complement languages, or subshifts of finite type.

Special [cellular automaton] rules Rule 51: complement; rule 170: left shift; rule 204: identity; rule 240: right shift.

Note that while the complement of a recursive set is always recursive, the complement of a recursively enumerable set may not be recursively enumerable. … Complements of recursively enumerable sets are characteristically associated with Π 1 statements of the form ∀ t ϕ [t] —an example being whether a given system never halts. ( Π 1 and Σ 1 statements are such that if they can be shown to be undecidable, then respectively they must be true or false, as discussed on page 1167 .)

(In ordinary base 2 a number -n can be represented as on a typical electronic computer by complementing each digit, including leading 0's.)

Negative numbers are effectively represented by complements of digit sequences, much as in typical practical computers.

In some cases the set of allowed sequences forms a so-called finite complement language (or subshift of finite type) that can be characterized completely just by saying that some finite set of blocks are excluded.

The following generates explicit lists of n -input Boolean functions requiring successively larger numbers of Nand operations: Map[FromDigits[#, 2] &, NestWhile[Append[#, Complement[Flatten[Table[Outer[1 - Times[##] &, # 〚 i 〛 , # 〚 -i 〛 , 1], {i, Length[#]}], 2], Flatten[#, 1]]] &, {1 - Transpose[IntegerDigits[Range[2 n ] - 1, 2, n]]}, Length[Flatten[#, 1]] < 2 2 n &], {2}] The results for 2-step cellular automaton evolution in the main text were found by a recursive procedure.

Given the list of successive configurations of the register machine, the steps that correspond to successive steps of Turing machine evolution can be obtained from (Flatten[Partition[Complement[#, #-1], 1, 2]]&)[ Position[list, {_,{_,_,0}}]] The program given above works for Turing machines with any number of states, but it requires some simple extensions to handle more than two possible colors for each cell.

(Note that any possible Perron number can be obtained for example from some finite complement language.)