Accession Number : AD0667209

Title :   THE UNSOLVABILITY OF THE EQUIVALENCE PROBLEM FOR LAMBDA-FREE NONDETERMINISTIC GENERALIZED MACHINES.

Descriptive Note : Physical sciences research papers, no. 349,

Corporate Author : AIR FORCE CAMBRIDGE RESEARCH LABS L G HANSCOM FIELD MASS

Personal Author(s) : Griffiths,T. V.

Report Date : JAN 1968

Pagination or Media Count : 14

Abstract : We show that the equivalence problem for Lambda-free nondeterministic generalized machines is unsolvable and observe that this result implies the unsolvability of the equality problem for c-finite languages. (Author)

Descriptors :   (*PROGRAMMING LANGUAGES, THEOREMS), ALGORITHMS, SET THEORY, MAPPING(TRANSFORMATIONS), DETERMINATION, ARTIFICIAL INTELLIGENCE, LINGUISTICS, LEARNING MACHINES, GROUPS(MATHEMATICS)

Subject Categories : Linguistics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE