Accession Number:

AD0660886

Title:

NEW PROOFS OF OLD THEOREMS IN LOGIC AND FORMAL LINGUISTICS,

Descriptive Note:

Corporate Author:

CARNEGIE INST OF TECH PITTSBURGH PA

Personal Author(s):

Report Date:

1966-11-01

Pagination or Media Count:

19.0

Abstract:

Theorem 1 constructs, from any word problem in a semi-Thue system, an equivalent Post correspondence problem, showing the undecidability of the general Post correspondence problem. Theorem 2 constructs, from any Post correspondence problem, a minimal linear grammar which is ambiguous exactly if the Post correspondence problem has a solution, showing the undecidability of the general ambiguity problem. Other standard undecidability results on phrase structure grammars are implied. Theorem 3 constructs, from any word problem in a semi-Thue system, an ambiguity problem, combining the results of Theorem 1 and 2 by more direct means. No new results are presented, but standard proofs were shortened and constructions eliminated, combined, or simplified. Author

Subject Categories:

  • Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE