### A Remark on Post Normal SystemsA Remark on Post Normal Systems

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