Definition Theory as Basis for a Creative Problem Solver

T. Gorgely, Hajnal Andréka, István NémetiIJCAI 1975

Abstract

This paper, originating from the Hungarian Academy of Sciences in the mid-1970s, explores the application of First-Order Logic and Model Theory to Artificial Intelligence. It proposes a framework for "creative" problem solving within Systems for Automatic Designing (SAD). By treating vague user expectations as implicit definitions, the authors demonstrate how model-theoretic theorems—specifically Beth’s, Svenonius’, and Chang-Makkai’s—can be used to derive explicit, executable specifications, thereby formalizing the transition from conceptual hints to concrete designs.

Introduction

A persistent challenge in Artificial Intelligence is the semantic gap between a user’s vague "expectations" and a computer’s requirement for "explicit definitions." In traditional software engineering, tasks are typically well-defined. However, in "creative" design, users often provide only incomplete conditions or hints—what the authors term constructive tasks. The goal of this research is to build a system capable of taking these implicit, "program-like" expectations and automatically generating a precise mathematical definition of the object to be constructed.

Methodology: The SAD Architecture

The authors frame the design process within the rigorous bounds of First-Order Logic and Model Theory. They propose a two-part architecture for a System for Automatic Designing (SAD):

  1. High-Level Problem Defining Unit: This component processes the user's implicit requirements ($\Sigma(P)$) alongside the system's background knowledge ($\Gamma$). Its objective is to find an explicit formula ($\phi$) that defines the unknown relation $P$.
  2. Solving Unit: Once an explicit definition is obtained, this unit performs the actual construction or computation.

The "High-Level Unit" leverages fundamental theorems from logic to bridge the gap between implicit and explicit knowledge:

  • Beth’s Theorem: Determines if a set of requirements is sufficiently strong to yield a unique explicit definition.
  • Svenonius’ and Chang-Makkai Theorems: These handle "weaker" requirements where the object can only be defined up to a finite set of possibilities or parameters.
Formalization of weaker requirements using disjunctions of potential definitions.

Formalizing Creativity

The paper argues that "creativity" in design is not a mystical process but can be modeled as a search for a formula that satisfies specific model-theoretic constraints. This involves a formal distinction between knowing about an object (implicit) and possessing a recipe to build it (explicit).

If a system fails to find a definition, the authors suggest the limitation lies in the "discipline" or background knowledge ($\Gamma$). A truly creative solver must therefore possess "inductive logical means" to extend its own knowledge base to meet user expectations. This insight notes that users often communicate in "expectations" rather than specifications, and AI must be designed to handle this inherent ambiguity.

Key Results

The theoretical roadmap provided in this work establishes several critical points:

  • Circumscribed Tasks: If a design task is limited in a specific way across all possible mathematical models, a finite number of parametric formulas exist that can define the solution.
  • Theorem Proving as Search: A SAD can operate as a theorem prover that searches for definitions rather than just checking for truth.
  • Theorem Selection: The "strength" of a user's request dictates whether Beth’s or Svenonius’ theorem is required to resolve the problem.
The derivation of parametric formulas to define solutions under specific constraints.

Limitations and Future Outlook

While the framework is theoretically sound, the authors acknowledge significant hurdles:

  • Computational Complexity: Finding these formulas involves a potentially massive search space, described as "trying" formulas sequentially.
  • Inductive Logic: The paper identifies the need for inductive logic to expand the knowledge base but does not provide specific algorithms for this learning process.
  • Open Questions: The work concludes by challenging the field to define the exact necessary and sufficient conditions to guarantee that an explicit definition can be found given a specific knowledge base and set of requirements.

This summary is based on research from the Hungarian Academy of Sciences, circa 1975.

Summary updated

BibTeX
@inproceedings{gorgely1975definition,
  author = {T. Gorgely and Hajnal Andréka and István Németi},
  title = {{Definition Theory as Basis for a Creative Problem Solver}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1975},
}
Figure