Accession Number:

AD0668755

Title:

THE RECURSIVE UNSOLVABILITY OF THE DECISION PROBLEM FOR THE CLASS OF DEFINITE FORMULAS,

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CALIF

Personal Author(s):

Report Date:

1968-04-01

Pagination or Media Count:

12.0

Abstract:

A class of formulas of the first-order predicate calculus--the definite formulas--have recently been proposed as formal representations of reasonable questions to be processed by an actual data retrieval system known as the Relational Data File. It is shown in this study that the decision problem for the class of definite formulas is recursively unsolvable. Hence there is no algorithm that can be used to decide whether or not a given formula is definite. Author

Subject Categories:

  • Information Science

Distribution Statement:

APPROVED FOR PUBLIC RELEASE