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

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)

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1968
Accession Number
AD0668755

Entities

People

  • R. A. Di Paola

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Calculus

Fields of Study

  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.