From an arbitrary Turing machine, Z, a monogenic Post normal system, v(Z), is constructed. It is then shown not only that the halting problem for Z is reducible to that of v(Z) but also that the halting problem for v(Z) is reducible to that of Z. Since ...
Let N(T) be the normal system of Post which corresponds to the Thue system, 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, D, ...
For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognise this language with a non-deterministic or alternating parity automaton. These questions are known as, respectively, the non-...
Association for Computing Machinery
New York, NY, United States
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in