Accession Number : AD0668755

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

Corporate Author : RAND CORP SANTA MONICA CALIF

Personal Author(s) : Di Paola,R. A.

Report Date : APR 1968

Pagination or Media Count : 12

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)

Descriptors :   (*DATA PROCESSING, MAN MACHINE SYSTEMS), (*INFORMATION RETRIEVAL, MATHEMATICAL LOGIC), SET THEORY, PROBLEM SOLVING, DECISION THEORY, THEOREMS

Subject Categories : Information Science

Distribution Statement : APPROVED FOR PUBLIC RELEASE