## Tractable inducers

Haskell commentary on the implementation of Tractable and Practicable Inducers/Tractable inducers

Although the *literal derived alignment inducer*, $I_{z,\mathrm{a,l}}^{‘}$, is finitely computable, it is intractable. Section ‘Tractable alignment-bounding’ P568 discusses the various intractabilities and the classes of limits and constraints on the structures of more tractable *inducers*.

### Sections

Intractable search set elements

Intractable_literal_substrate_model_inclusion

### Intractable substrate volume

First, the *substrate volume* is intractable P588. The application of the *transformer* $I_{ * \mathrm{T}}$, in the *literal derived alignment inducer*, $I_{z,\mathrm{a,l}}^{‘}$, to a *substrate histogram*, $A$, and a *substrate transform*, $T \in \mathcal{T}_{U_A,V_A}$, is $I_{ * \mathrm{T}}^{ * }((T,A)) = A * T$. The *volume*, $|V_A^{\mathrm{C}}|$, grows exponentially with *underlying dimension* $n = |V_A|$, and so the *space* complexity of the *transformer*, $I_{ * \mathrm{T}}$, is exponential with respect to *underlying dimension*, $n$. To address this (i) the *inducer models* of the *literal derived alignment inducer* are expanded from *substrate transforms*, $\mathcal{T}_{U_A,V_A}$, to *substrate fuds*, $\mathcal{F}_{U_A,V_A}$, and (ii) the *substrate fuds* are then limited by intersecting with one of the class of *limited-underlying* subsets of the *functional definition sets* $\mathcal{F}_{\mathrm{u}} \subset \mathcal{F}$. A set of *limited-underlying fuds*, $\mathcal{F}_{\mathrm{u}}$, is defined such that a *fud* $F \in \mathcal{F}_{\mathrm{u}}$ is such that its *transforms*, $F \subset \mathcal{T}$, are each tractably computable. For example the *underlying volume* of the *transforms* may be limited by a *maximum underlying volume* limit $\mathrm{xmax} \in \mathbf{N}_{\geq 4}$. The set of *inducer models* is $\mathcal{F}_{U_A,V_A} \cap \mathcal{F}_{\mathrm{u}}$.

Note that, if the *size*, $z = \mathrm{size}(A)$, is less than the *volume*, $v = |A^{\mathrm{C}}|$, the *independent* is necessarily *non-integral*, $z < v \implies A^{\mathrm{X}} \notin \mathcal{A}_{\mathrm{i}}$. For this reason, any *volume* limits, for example, $\mathrm{xmax} \in \mathbf{N}_{\geq 4}$, should be chosen such that they are less than or equal to the *size*, $\mathrm{xmax} \leq z$.

### Intractable derived volume

Next, the *derived volume* is intractable P591. Both the computation *time* and computation *space* of the *alignmenter* applied to the *transformed sample histogram*, $I_{\mathrm{a}}^{ * }(A * T) \approx \mathrm{algn}(A * T)$, in the *literal derived alignment inducer*, $I_{z,\mathrm{a,l}}^{‘}$, vary with the *derived volume*, $w = |W^{\mathrm{C}}|$, where $W = \mathrm{der}(T)$. The *derived volume*, $w$, grows exponentially with *derived dimension* $m = |W|$ and so the *time* and *space* complexities are exponential, and therefore intractable, with respect to *derived dimension*, $m$. This is also the case where the implementation uses a *fuder*, $I_{\mathrm{ * F}}$, in a *limited-underlying derived alignment fud inducer*, because the application of a *fud* $F \in \mathcal{F}_{U_A,V_A} \cap \mathcal{F}_{\mathrm{u}}$ must still compute $(A * F)^{\mathrm{X}}$ in an *independenter*, $I_{\mathrm{X}}$, in order to compute *derived alignment*, $\mathrm{algn}(A * F)$.
So a further compromise is made by intersecting the *substrate fuds* with one of the class of *limited-derived* subsets of the *functional definition sets* $\mathcal{F}_{\mathrm{d}} \subset \mathcal{F}$. A set of *limited-derived fuds*, $\mathcal{F}_{\mathrm{d}}$, is defined such that a *fud* $F \in \mathcal{F}_{\mathrm{d}}$ is such that the *independent derived* of the *fud* is tractable. For example the *derived volume* of the *fud* may be limited by a *maximum derived volume* limit of $\mathrm{wmax} \in \mathbf{N}_{\geq 4}$.

Although the *limited-variables substrate fuds*, $\mathcal{F}_{U_A,V_A} \cap \mathcal{F}_{\mathrm{u}} \cap \mathcal{F}_{\mathrm{d}}$, has coverage of the entire *substrate* even when the *substrate volume*, $v$, is greater than the *underlying volume limit*, for example $v > \mathrm{xmax}$, the *derived volume* is still strictly limited, $w \leq \mathrm{wmax}$. In section ‘Summation aligned decomposition inducers’ P582 it is conjectured that a *summation aligned decomposition* $D \in \mathcal{D}_{\Sigma}(A)$ is such that the *content alignment* equals the *summation alignment*,
\[
\begin{eqnarray}
\mathrm{algn}(A * D^{\mathrm{T}}) - \mathrm{algn}(A^{\mathrm{X}} * D^{\mathrm{T}}) &=& \mathrm{alignmentSum}(A,D)
\end{eqnarray}
\]
where
\[
\begin{eqnarray}
\mathrm{alignmentSum}(A,D) &=& \sum \mathrm{algn}(A * C * T) : (C,T) \in \mathrm{cont}(D)
\end{eqnarray}
\]
and $\mathrm{cont} = \mathrm{elements} \circ \mathrm{contingents}$. Thus, insofar as the *content alignment* approximates to the *derived alignment*, summing the *derived alignments* of the *contingent fuds* avoids the computation of the *nullable transform*, $D^{\mathrm{T}}$, which may have intractable *derived volume*, for example $w > \mathrm{wmax}$, where $w =|W^{\mathrm{C}}|$ and $W = \mathrm{der}(D^{\mathrm{T}})$. Just as above where the set of *inducer models* is increased from *substrate transforms*, $\mathcal{T}_{U_A,V_A}$, to *substrate fuds*, $\mathcal{F}_{U_A,V_A}$, the *inducer models* is again expanded to the *substrate fud decompositions* $\mathcal{D}_{\mathrm{F},U_A,V_A}$. The set of *inducer models* is then the *limited-variables substrate fud decompositions*, $\mathcal{D}_{\mathrm{F},U_A,V_A} \cap \mathrm{trees}(\mathcal{S} \times (\mathcal{F}_{\mathrm{u}} \cap \mathcal{F}_{\mathrm{d}}))$. Given a *limited-variables substrate fud decomposition* $D \in \mathcal{D}_{\mathrm{F},U_A,V_A} \cap \mathrm{trees}(\mathcal{S} \times (\mathcal{F}_{\mathrm{u}} \cap \mathcal{F}_{\mathrm{d}}))$, the *inducer* computes the tractable sum of the *contingent derived alignments*, $\sum \mathrm{algn}(A * C * F^{\mathrm{T}}) : (C,F) \in \mathrm{cont}(D)$.

### Intractable search set elements

Third, the computation of the *search set models* is intractable for two reasons, (i) *fud flattening*, and (ii) *layer variables* cardinality P599. The computation of the finite *substrate fud set*, $\mathcal{F}_{U_A,V_A}$, requires the exclusion of duplicate nested *partitions*. This is done by checking for the uniqueness of the *flattened partitions*. This check is intractable so the *substrate fud set*, $\mathcal{F}_{U_A,V_A}$, is replaced by the intersection of (i) the *infinite-layer substrate fud set* $\mathcal{F}_{\infty,U_A,V_A}$, which dispenses with the check, and (ii) one of the class of the sets of *limited-layer fuds*, $\mathcal{F}_{\mathrm{h}}$. The *limited-layer substrate fuds*, $\mathcal{F}_{\infty,U_A,V_A} \cap \mathcal{F}_{\mathrm{h}}$, places a limit on the number of *layers*, for example, a *maximum layer* limit of $\mathrm{lmax} \in \mathbf{N}_{>0}$.

The *layer variables* cardinality intractability is because of exponential *time* complexity of the computation of the *layers* of the *fuds*. This is addressed by defining one of the class of the sets of *limited-breadth fuds*, $\mathcal{F}_{\mathrm{b}}$. For example a *maximum layer breadth* limit of $\mathrm{bmax} \in \mathbf{N}_{>0}$. Together the classes of limits are intersected together to form the class of *limited-models* $\mathcal{F}_{\mathrm{q}} = \mathcal{F}_{\mathrm{u}} \cap \mathcal{F}_{\mathrm{d}} \cap \mathcal{F}_{\mathrm{h}} \cap \mathcal{F}_{\mathrm{b}}$. The set of *inducer models* is then the *limited-models infinite-layer fud decompositions*, $\mathcal{D}_{\mathrm{F},\infty,U_A,V_A} \cap \mathrm{trees}(\mathcal{S} \times \mathcal{F}_{\mathrm{q}})$.

### Intractable literal substrate model inclusion

Last, the computation of the *literal substrate model inclusion* is intractable P606.
Consider the remaining two constraints, (i) *formal-abstract equality*, $A^{\mathrm{X}} * T = (A * T)^{\mathrm{X}}$, and (ii) *ideal transform*, $A = A * T * T^{\dagger A}$. As described in section ‘Intractable literal substrate model inclusion’ P606, both of these inclusion tests of the *model* are intractable with respect to *substrate volume*. Now consider how *inducers* can be made tractable while adhering to these constraints as closely as possible.

First, the *formal-abstract equality* is weakened to the *independent-formal* constraint, $A^{\mathrm{X}} * T = (A^{\mathrm{X}} * T)^{\mathrm{X}}$, in the *derived alignment substrate ideal independent-formal transform inducer*, $I_{z,\mathrm{a,fx,j}}^{‘}$. This constraint is still intractable, so it is replaced by constraining the *transforms* to be *non-overlapping*,
\[
\begin{eqnarray}
\neg \mathrm{overlap}(T) &\implies& A^{\mathrm{X}} * T = (A^{\mathrm{X}} * T)^{\mathrm{X}}
\end{eqnarray}
\]
in the *derived alignment substrate ideal non-overlapping transform inducer*, $I_{z,\mathrm{a,n,j}}^{‘}$. If the *ideality* inclusion test is dropped and the *inducer model* set of *substrate transforms*, $\mathcal{T}_{U_A,V_A}$, is replaced by the *limited-models infinite-layer substrate fuds*, $\mathcal{F}_{\infty,U_A,V_A} \cap \mathcal{F}_{\mathrm{q}}$, then the tractable *limited-models derived alignment substrate non-overlapping infinite-layer fud inducer* $I_{z,\mathrm{a,F,\infty,n,q}}^{‘} \in \mathrm{inducers}(z)$, given *substrate histogram* $A \in \mathcal{A}_{z}$, can be defined
\[
\begin{eqnarray}
&&I_{z,\mathrm{a,F,\infty,n,q}}^{‘ * }(A) = \\
&&\hspace{5em}\{(F,I_{\approx\mathbf{R}}^{ * }(\mathrm{algn}(A * F^{\mathrm{T}}))) : F \in \mathcal{F}_{\infty,U_A,V_A} \cap \mathcal{F}_{\mathrm{n}} \cap \mathcal{F}_{\mathrm{q}}\}
\end{eqnarray}
\]
where $\mathcal{F}_{\mathrm{n}}$ is the set of *non-overlapping fuds*.
Although this *inducer* is tractable, the *non-overlapping* constraint is weaker than the *formal-abstract equality* constraint and the *ideality* constraint has been dropped altogether.
The *entropy* of the doubly-*independent* *formal independent histogram*, $\mathrm{entropy}((A^{\mathrm{X}} * T)^{\mathrm{X}})$, is expected to be greater than the *entropy* of the *abstract histogram*, $\mathrm{entropy}((A * T)^{\mathrm{X}})$, whereas if the *formal-abstract equality* constraint holds then the *entropies* would be equal. The *abstract-non-formal entropy substrate ideal independent-formal transform inducer*, $I_{z,\mathrm{e,fx,j}}^{‘} \in \mathrm{inducers}(z)$, maximises the *entropy* difference between the *abstract* and the *formal independent*. The *inducer* is defined
\[
\begin{eqnarray}
&&I_{z,\mathrm{e,fx,j}}^{‘ * }(A) = \\
&&\hspace{2em}\{(T,I_{\approx\ln\mathbf{Q}}^{ * }(\mathrm{entropy}((A * T)^{\mathrm{X}}) - \mathrm{entropy}((A^{\mathrm{X}} * T)^{\mathrm{X}}))) : \\
&&\hspace{5em}T \in \mathcal{T}_{U_A,V_A},~A^{\mathrm{X}} * T = (A^{\mathrm{X}} * T)^{\mathrm{X}},~A = A * T * T^{\dagger A}\}
\end{eqnarray}
\]
*Derived alignment* approximates to the *sized* *entropy* difference between the *abstract histogram* and the *derived histogram*,
\[
\begin{eqnarray}
\mathrm{algn}(A * T) & \approx & z \times (\mathrm{entropy}((A * T)^{\mathrm{X}}) - \mathrm{entropy}(A * T))
\end{eqnarray}
\]
so the *abstract-non-formal entropy inducer*, $I_{z,\mathrm{e,fx,j}}^{‘}$, weakly maximises the *derived alignment*.

The *abstract-non-formal entropy inducer* is defined in terms of the *entropies* of *histograms* in the *derived variables*, $\mathrm{entropy}((A * T)^{\mathrm{X}})$ and $\mathrm{entropy}((A^{\mathrm{X}} * T)^{\mathrm{X}})$, and so ignores the *entropies* of the *underlying components*, $\{(C,\mathrm{entropy}(A * C)) : (\cdot,C) \in T^{-1}\}$. The discussion considers the *actualisations*, which alter the relative *independence* of the *derived* and *underlying*, and then proposes an *inducer* that maximises the *midisation pseudo-alignment*, $\mathrm{algn}(A) - \mathrm{algn}(A * T * T^{\dagger A}) - \mathrm{algn}((A * T)^{\mathrm{X}} * T^{\odot A})$. However, the *ideality* constraint restricts the *midisation pseudo-alignment* to be equal to the negative *surrealisation alignment*, so the *ideality* constraint is dropped. The *midisation pseudo-alignment substrate independent-formal transform inducer* $I_{z,\mathrm{m,fx}} \in \mathrm{inducers}(z)$, given *substrate histogram* $A \in \mathcal{A}_{z}$, is defined
\[
\begin{eqnarray}
&&I_{z,\mathrm{m,fx}}^{ * }(A) = \\
&&\hspace{2em}\{(T,I_{\approx\mathbf{R}}^{ * }(\mathrm{algn}(A) - \mathrm{algn}(A * T * T^{\dagger A}) - \mathrm{algn}((A * T)^{\mathrm{X}} * T^{\odot A}))) : \\
&&\hspace{5em}T \in \mathcal{T}_{U_A,V_A},~A^{\mathrm{X}} * T = (A^{\mathrm{X}} * T)^{\mathrm{X}}\}
\end{eqnarray}
\]
The computation of *midisation* is intractable, so a further approximation is required. Maximisation of *midisation* tends to move *component alignments* from *off-diagonal states* to *on-diagonal states*, balancing the high *derived alignment* of longer *diagonals* with the high *on-diagonal component alignments* of shorter *diagonals*. Thus the *midisation pseudo-alignment* varies with the *derived alignment valency density*. The *derived alignment valency-density substrate independent-formal transform inducer* $I_{z,\mathrm{ad,fx}}^{‘} \in \mathrm{inducers}(z)$, given *substrate histogram* $A \in \mathcal{A}_{z}$, is defined
\[
\begin{eqnarray}
&&I_{z,\mathrm{ad,fx}}^{‘ * }(A) = \\
&&\hspace{2em}\{(T,I_{\approx\mathbf{R}}^{ * }(\mathrm{algn}(A * T)/w_T^{1/m_T})) : T \in \mathcal{T}_{U_A,V_A},~A^{\mathrm{X}} * T = (A^{\mathrm{X}} * T)^{\mathrm{X}}\}
\end{eqnarray}
\]
where *derived variables* $W_T = \mathrm{der}(T)$, *derived volume* $w_T = |W_T^{\mathrm{C}}|$, *derived dimension* $m_T = |W_T|$ and $I_{\approx\mathbf{R}}^{ * }$ computes an approximation to a real number. The geometric average of the *derived valencies* is $w_T^{1/m_T}$.

If the *independent formal* constraint is replaced by constraining the *transforms* to be *non-overlapping*, and the *inducer model* set of *substrate transforms*, $\mathcal{T}_{U_A,V_A}$, is replaced by the *limited-models infinite-layer substrate fuds*, $\mathcal{F}_{\infty,U_A,V_A} \cap \mathcal{F}_{\mathrm{q}}$, then the tractable *limited-models derived alignment valency-density substrate non-overlapping infinite-layer fud inducer* $I_{z,\mathrm{ad,F,\infty,n,q}}^{‘} \in \mathrm{inducers}(z)$, given *substrate histogram* $A \in \mathcal{A}_{z}$, can be defined as
\[
\begin{eqnarray}
&&I_{z,\mathrm{ad,F,\infty,n,q}}^{‘ * }(A) = \\
&&\hspace{5em}\{(F,I_{\approx\mathbf{R}}^{ * }(\mathrm{algn}(A * F^{\mathrm{T}})/w_F^{1/m_F})) : F \in \mathcal{F}_{\infty,U_A,V_A} \cap \mathcal{F}_{\mathrm{n}} \cap \mathcal{F}_{\mathrm{q}}\}
\end{eqnarray}
\]
This *derived alignment valency-density fud inducer*, $I_{z,\mathrm{ad,F,\infty,n,q}}^{‘}$, addresses the *formal-abstract equality* constraint, $A^{\mathrm{X}} * T = (A * T)^{\mathrm{X}}$, but ignores the *ideal transform* constraint, $A = A * T * T^{\dagger A}$. As described above, intractable *derived volume* can be addressed by expanding the *inducer models* to the *substrate fud decompositions*, $\mathcal{D}_{\mathrm{F},U_A,V_A}$, and summing the *derived alignments* of the *contingent fuds*,
\[
\begin{eqnarray}
\sum \mathrm{algn}(A * C * F^{\mathrm{T}}) : (C,F) \in \mathrm{cont}(D)
\end{eqnarray}
\]
Using a similar method, sections ‘Decomposition alignment’ P491 and ‘Tractable decomposition inducers’ P621 show how maximising the sum of the *contingent alignment valency-densities*,
\[
\begin{eqnarray}
\sum \mathrm{algn}(A * C * F^{\mathrm{T}})/w_F^{1/m_F} : (C,F) \in \mathrm{cont}(D)
\end{eqnarray}
\]
of *limited-models non-overlapping infinite-layer fud decompositions*, $\mathcal{D}_{\mathrm{F},\infty,U_A,V_A} \cap \mathrm{trees}(\mathcal{S} \times (\mathcal{F}_{\mathrm{n}} \cap \mathcal{F}_{\mathrm{q}}))$, removes *alignments* along the *decomposition* path and tends to *independent leaf components*. When *fully decomposed* the *nullable transform* of the *decomposition* is *ideal*, $A * D^{\mathrm{T}} * D^{\mathrm{T}\dagger A} = A$. The tractable *limited-models summed alignment valency-density substrate aligned non-overlapping infinite-layer fud decomposition inducer*, given *non-independent substrate histogram* $A \in \mathcal{A}_{z} \setminus \{A^{\mathrm{X}}\}$, is defined
\[
\begin{eqnarray}
&&I_{z,\mathrm{Sd,D,F},\infty,\mathrm{n,q}}^{‘ * }(A) = \\
&&\hspace{2em}\{(D,I_{\approx\mathbf{R}}^{ * }(\sum \mathrm{algn}(A * C * F^{\mathrm{T}})/w_F^{1/m_F} : (C,F) \in \mathrm{cont}(D))) : \\
&&\hspace{5em}D \in \mathcal{D}_{\mathrm{F},\infty,U_A,V_A} \cap \mathrm{trees}(\mathcal{S} \times (\mathcal{F}_{\mathrm{n}} \cap \mathcal{F}_{\mathrm{q}})),\\
&&\hspace{10em}\forall (C,F) \in \mathrm{cont}(D)~(\mathrm{algn}(A * C * F^{\mathrm{T}})>0)\}
\end{eqnarray}
\]

Here the *model* has been extended from *transforms*, $M \in \mathcal{T}_{U,V}$, to *functional definition set decompositions*, $M \in \mathcal{D}_{\mathrm{F},\infty,U,V}$. At the same time the set of *fud decompositions* has been restricted to those having (a) *fuds* that are *non-overlapping*, $\mathcal{F}_{\mathrm{n}}$, (b) *fuds* with a *limited-underlying*, *limited-derived*, *limited-layer* and *limited-breadth* structure, $\mathcal{F}_{\mathrm{q}} = \mathcal{F}_{\mathrm{u}} \cap \mathcal{F}_{\mathrm{d}} \cap \mathcal{F}_{\mathrm{h}} \cap \mathcal{F}_{\mathrm{b}}$, and (c) *fuds* with *derived alignment*, $\mathrm{algn}(A * C * F^{\mathrm{T}})>0$. The tractable optimal *model* is
\[
\begin{eqnarray}
D_{\mathrm{Sd}}~\in~\mathrm{maxd}(I_{z,\mathrm{Sd,D,F},\infty,\mathrm{n,q}}^{‘ * }(A))
\end{eqnarray}
\]
The *limited-models summed alignment valency-density substrate aligned non-overlapping infinite-layer fud decomposition inducer*, $I_{z,\mathrm{Sd,D,F},\infty,\mathrm{n,q}}^{‘}$, limits the optimisation to make *aligned induction* tractable. By additionally imposing a sequence on the search and other constraints, tractable *induction* can be made practicable in the *highest-layer summed shuffle content alignment valency-density fud decomposition inducer*, $I_{z,\mathrm{Scsd,D,F,\infty,q},P,\mathrm{d}}^{‘}$.