Introduction
In the field of automated reasoning during the early 1980s, a fundamental tension existed between declarative and procedural knowledge. Declarative knowledge consists of the facts and axioms provided to a system, while procedural knowledge comprises the algorithms used to manipulate those facts. Traditionally, these two domains were strictly separated: a human designer would provide the axioms and then manually select the most efficient algorithms to process them. This paper presents a theorem-proving system that bridges this gap by dynamically adapting its own internal logic, recognizing when a declarative axiom is better handled as a specialized procedural algorithm.
The Problem of Unorderable Rules
The standard approach for automated deduction at the time was the Knuth-Bendix (KB) completion algorithm. This procedure attempts to transform a set of mathematical axioms into a "complete" set of rewrite rules. These rules allow the system to simplify complex expressions into a unique normal form. For the KB algorithm to function, every rule must be orientable—meaning it must have a clear direction where one side of the equation is "simpler" or "smaller" than the other (e.g., $x + 0 \to x$).
However, certain fundamental mathematical properties, such as the commutative law ($x + y = y + x$), are impossible to orient because neither side is simpler than the other. In standard systems, encountering such a rule would cause the KB algorithm to fail. Historically, a human operator would have to intervene, identify the problematic axiom, and manually switch the system to a specialized "commutative unification" algorithm. This manual loop limited the autonomy and efficiency of automated provers.
The Self-Modification Mechanism
The author implemented a theorem prover in Prolog designed to eliminate this human intervention. The system monitors its own derivation process through a three-stage self-modification cycle:
- Pattern Recognition: As the system derives new rules from its initial axioms, a monitoring layer examines their syntactic structure. If a derived rule matches the pattern of a commutative law ($f(x,y) = f(y,x)$), the system flags the specific operator (such as "+") as commutative.
- Procedural Shift: Once an operator is flagged, the system automatically swaps its standard unification algorithm for a specialized Associative-Commutative (AC) unification algorithm. This allows the engine to treat symmetric expressions as identical during its search process without needing an explicit rewrite rule.
- Dynamic Re-evaluation: Following the algorithmic shift, the system performs a "simplification cascade." It re-processes its existing rule database to see if old rules can be simplified or if redundant rules can be eliminated now that the system "understands" the operator's symmetry.
Experimental Results: Group Theory
The system was tested using classical algebraic structures, specifically Group Theory axioms (identity, inverse, and associativity). In a key test case, the system was provided with standard group axioms plus the additional rule $x + x = 0$.
During the execution, the system successfully derived the commutative law $x + y = y + x$ as a consequence of the input. Upon this discovery, the prover automatically transitioned to AC-unification. This self-modification allowed the system to collapse its internal rule set from a complex intermediate state down to a clean, complete set of 10 rewrite rules. This transition was achieved entirely without human guidance, demonstrating that a system can autonomously optimize its own reasoning architecture based on the properties of the domain it is exploring.
Limitations and Future Directions
While the system demonstrates a successful proof-of-concept for self-modifying logic, several challenges remain:
- Computational Complexity: Creating specialized algorithms for every possible combination of algebraic properties (such as idempotency or distributivity) is computationally expensive and difficult to generalize.
- Unification Efficiency: The AC-unification algorithm often generates a high number of redundant possibilities, which can become a performance bottleneck in more complex proofs.
- The Discovery Bottleneck: Currently, the system must derive a property before it can adopt the corresponding algorithm. Future iterations might allow the system to proactively hypothesize properties if it encounters unorderable rules that stall the completion process.
Conclusion
By treating the boundary between data and code as fluid, this research demonstrates that theorem provers can achieve higher levels of autonomy. Moving knowledge from the declarative category to the procedural category not only optimizes the search process but also removes the "restart problem" that previously required human experts to guide automated reasoners through symmetric mathematical spaces.
Summary updated