Infinite Computations and a Hierarchy in 3 Reconsidered
Branislav Rovan, Ľuboš Steskal · Journal of Logic and Computation · 2008
In this note, we reconsider the results in Rovan and Steskal (2007, Vol. 4497 of Lecture Notes in Computer Science, pp. 660–669, Springer) concerning TMDC (Display Turing Machines with Control) with Chomsky like control language. We shall show that, under the given assumptions, various degrees of the control complexity do not give rise to a hierarchy of language families, thus correcting an error in Rovan and Steskal (2007, Vol. 4497 of Lecture Notes in Computer Science, pp. 660–669, Springer).