DECISION PROBLEMS FOR MULTIPLE SUCCESSOR ARITHMETICS.

Abstract

Let N sub k denote the set of words over the alphabet S sub k = (1, ..., k). N sub k contains the null word which is denoted. Decision problems are considered for various first-order interpreted predicate languages in which the variables range over N sub k (k > 2). The main result is that there is no decision procedure for truth in the interpreted language which has the subword relation as its only non-logical primitive. This, together with known results summarized in the report, settles the decision problem for any language constructed on the basis of a large number of relations and functions. (Author)

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1965
Accession Number
AD0615085

Entities

People

  • J. W. Thatcher

Organizations

  • University of Michigan

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Alphabets
  • Behavior And Behavior Mechanisms
  • Behavioral Disciplines And Activities
  • Behavioral Sciences
  • Contract Administration
  • Contracts
  • Cooperation
  • Group Dynamics
  • Language

Fields of Study

  • Mathematics

Readers

  • Artificial Intelligence
  • Regression Analysis.
  • Theoretical Analysis.