
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 firstorder predicate calculusthe definite formulashave 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