To assess a single operator's expressive power, first fix the target functions, allowed constants, domains, and composition rules.
What does generating a function mean
Functional completeness means that composing specified operations can express every function in a target class. Saying that there is only one operator is insufficient. The inputs, outputs, allowed constants, and permitted composition rules must also be specified.
NAND is a standard Boolean example. For inputs 0 and 1, define NAND(x, y) = NOT(x AND y). Sheffer's work on Boolean algebras is a classical source for expressing basic Boolean operations with one binary operation.
NOT(x) = NAND(x, x)
AND(x, y) = NAND(NAND(x, y), NAND(x, y))
OR(x, y) = NAND(NAND(x, x), NAND(y, y))These identities can be checked on all four Boolean input pairs. Once negation, conjunction, and disjunction are available, each true row of a truth table becomes a conjunction. Combining those rows with disjunction expresses any Boolean function with finitely many inputs.
This conclusion does not establish completeness for real elementary functions. A finite Boolean truth table and a continuous real domain require different arguments.
Domains matter for elementary functions
When composing logarithms and exponentials, first distinguish real from complex operations. The real logarithm is defined on positive inputs. A complex logarithm can have multiple values, so selecting one value requires a branch.
NIST DLMF's logarithm definitions distinguish the general logarithm from its principal branch. An inverse identity valid over the reals therefore cannot be applied across the complex plane without restrictions.
| Item | Required specification |
|---|---|
| Target functions | Which functions and domains must be represented |
| Constants | Whether 0, 1, or other constants are provided initially |
| Intermediate values | Whether complex or undefined intermediate values are allowed |
| Composition | Whether only finite composition is allowed, or also limits and inverse functions |
| Equality | Whether equality holds throughout the domain or only approximately on samples |
Providing a constant as a leaf differs from generating that constant with the operator alone. Any restriction on a target function's domain must be included in the final theorem.
Constructive proofs and automated search
A constructive proof gives a finite procedure for expressing target functions with the permitted operations. Numerically fitting a few examples does not replace that procedure. Conversely, a representation theorem does not guarantee that an optimizer will find the representation within a fixed budget.
Symbolic regression searches for formulas that fit data. An evaluation must specify target formulas, input ranges, noise, permitted tree sizes, computational budgets, and failed runs. These are criteria for interpreting experiments, not evidence that a particular operator is superior.
flowchart LR
A[Function class and composition rules] --> B[Proof of representability]
B --> C[Construct a concrete expression]
C --> D[Check equality across its domain]
A --> E[Automated search within a budget]
E --> F[Measure success and failure conditions]Fewer node types can simplify a grammar. However, expressions may become deeper or produce numerically unstable intermediate values. Simpler parsing, expressive completeness, numerical stability, and search success must be assessed separately.
Summary
Assess a single-operator claim only after specifying its function class and permitted operations. Boolean completeness of NAND is an established example, but it does not prove completeness for real elementary functions. Compositions of logarithms and exponentials require domain and complex-branch conditions. A representation proof and successful automated symbolic regression are different verification results.