Single Premise Post Canonical Forms Defined Over One-Letter Alphabets
Hughes, Charles E.
J. Symbolic Logic, Tome 39 (1974) no. 1, p. 489-495 / Harvested from Project Euclid
In this paper we investigate some families of decision problems associated with a restricted class of Post canonical forms, specifically, those defined over one-letter alphabets whose productions have single premises and contain only one variable. For brevity sake, we call any such form an RPCF (Restricted Post Canonical Form). Constructive proofs are given which show, for any prescribed nonrecursive r.e. many-one degree of unsolvability $D$, the existence of an RPCF whose word problem is of degree $D$ and an RPCF with axiom whose decision problem is also of degree $D$. Finally, we show that both of these results are best possible in that they do not hold for one-one degrees.
Publié le : 1974-09-14
Classification: 
@article{1183739183,
     author = {Hughes, Charles E.},
     title = {Single Premise Post Canonical Forms Defined Over One-Letter Alphabets},
     journal = {J. Symbolic Logic},
     volume = {39},
     number = {1},
     year = {1974},
     pages = { 489-495},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183739183}
}
Hughes, Charles E. Single Premise Post Canonical Forms Defined Over One-Letter Alphabets. J. Symbolic Logic, Tome 39 (1974) no. 1, pp.  489-495. http://gdmltest.u-ga.fr/item/1183739183/