The Power Relation Between Machines

The Power Relation between Machines:

Fig. 4.2. The binary relation Power is shown. The dotted edges are some of the edges implied by transitivity. Undotted and dotted means the same in this diagram. Therefore, Power actually contains: (i) the pairs corresponding to the solid edges, (ii) the pairs indicated by the dotted edges, (iii) and those pairs indicated by those dotted transitive edges not shown.
An example that nicely demonstrates the versatility of preorders is the one that defines the “power” of computing machines. Let
MT = {dfa, nfa, dpda, npda, lba, dtm, ndtm}
represent the set of machine types studied in this book. These acronyms stand for deterministic finite automata, nondeterministic finite automata, deterministic push-down automata, nondeterministic pushdown automata, linear bounded automata, deterministic Turing machines, and nondeterministic Turing machines, respectively. A binary relation called Power that situates various machine types into a dominance relation is shown in Figure 4.2. Each ordered pair in the relation
shows up as an arrow (→). We draw an arrow from machine type m1 to m2 if for every task that a machine of type m1 can perform, we can find a machine of type m2 to do the same task. Spelled out as a set, the relation Power is

Power={df a, df a, nfa, nfa,
dpda, dpda, npda, npda,
lba, lba,
dtm, dtm, ndtm, ndtm,
df a, nf a, nfa, dfa, dtm, ndtm,
ndtm, dtm, dfa, dpda, nfa, dpda,
df a, lba, nfa, lba,
dpda, npda, npda, dtm, npda, ndtm,
dpda, lba, npda, lba,
lba, dtm, lba, ndtm,
df a, npda, nfa, npda,
dpda, dtm, dpda, ndtm,
df a, dtm, df a, ndtm,
nfa, dtm, nfa, ndtm
}.
We will now study this dominance relation step by step. Any machine is as powerful as itself; hence, Power is reflexive, as shown by the ‘self-loops.’ Power is transitive relation because for every m1,m2,m3 ∈ MT, if m1,m2 ∈Power and m2,m3 ∈Power, then certainly m1,m3 ∈Power. (We do not show the transitive edges in the drawing). Power is not antisymmetric because even though dfa and nfa dominate each other, they have distinct existence in the set of machine types MT. Power is a preorder, and in our minds captures exactly how the space of machines must be subdivided. It is not a partial order.
The equivalence relation over machine types
Applying Theorem 4.1 to Power, we obtain the equivalence relation ≡MT over machine types: Power∩ Power−1 ={df a, df a, nfa, nfa, dpda, dpda, npda, npda, dtm, dtm, ndtm, ndtm, lba, lba, df a, nf a, nfa, dfa, dtm, ndtm, ndtm, dtm }.

Figure 4.3 illustrates ≡MT. We can see that ≡MT subdivides MT into five equivalence classes: {df a, nf a}, {dpda}, {npda}, {lba}, and {dtm, ndtm}. Let us now look at this equivalence relation formally. As pointed out earlier, an equivalence relation partitions the underlying set into equivalence classes. The set of equivalence classes is denoted by elements(R)/R below. The mathematical definition below elaborates on equivalence relations and equivalence classes:
elements(R)/R = { ρ | ρ ⊆ elements(R)
∧ ρ × ρ ⊆ R
∧¬∃Y : ρ ⊂ Y ∧ Y ⊆ elements(R)
∧ Y × Y ⊆ R }
This definition says the following:
• Each equivalence class Ei is a subset of the elements of the underlying set
• For each Ei, Ei × Ei is a subset of the equivalence relation.
• Each such set Ei is maximal (no bigger Y containing each Ei exists)
Coming to our specific example, there are four equivalence classes over Power∩ Power−1: {df a, nf a}, {dpda}, {npda}, and {dtm, ndtm}. As can be seen from Figure 4.3, they are four maximal universal relations. Given an equivalence relation R, the equivalence class of an element x ∈ elements(R) is denoted by [x].