Thumbnail
Access Restriction
Subscribed

Author Yasuhara, Ann
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1967
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Let $\textit{N}(\textit{T})$ be the normal system of Post which corresponds to the Thue system, $\textit{T},$ as in Martin Davis, Computability and Unsolvability (McGraw-Hill, New York, 1958), pp. 98-100. It is proved that for any recursively enumerable degree of unsolvability, $\textit{D},$ there exists a normal system, $\textit{N}\textit{T}(\textit{D}),$ such that the decision problem for $\textit{N}\textit{T}(\textit{D})$ is of degree $\textit{D}.$ Define a generalized normal system as a normal system without initial assertion. For such a $\textit{GN}$ the decision problem is to determine for any enunciations $\textit{A}$ and $\textit{B}$ whether or not $\textit{A}$ and $\textit{B}$ are equivalent in $\textit{GN}.$ Thus the generalized system corresponds more naturally to algebraic problems. It is proved that for any recursively enumerable degree of unsolvability, $\textit{D},$ there exists a generalized normal system, $\textit{GN}\textit{T}(\textit{D}),$ such that the decision problem for $\textit{GN}\textit{T}(\textit{D}),$ such that the decision problem for $\textit{GN}\textit{T}(\textit{D})$ is of degree $\textit{D}.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1967-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 14
Issue Number 1
Page Count 5
Starting Page 167
Ending Page 171


Source: ACM Digital Library