0383266 - ÚI 2014 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Žák, Stanislav - Šíma, Jiří
A Turing Machine Distance Hierarchy.
Language and Automata Theory and Applications. Berlin: Springer, 2013 - (Dediu, A.; Martín-Vide, C.; Truthe, B.), s. 570-578. Lecture Notes in Computer Science, 7810. ISBN 978-3-642-37063-2. ISSN 0302-9743.
[LATA 2013. International Conference on Language and Automata Theory and Applications /7./. Bilbao (ES), 02.04.2013-05.04.2013]
Grant CEP: GA ČR GAP202/10/1333; GA ČR GBP202/12/G061
Institucionální podpora: RVO:67985807
Klíčová slova: Turing machine * hierarchy * distance complexity * diagonalization
Kód oboru RIV: IN - Informatika
DOI: https://doi.org/10.1007/978-3-642-37064-9_50

We introduce a new so-called distance complexity measure for Turing machine computations which is sensitive to long-distance transfers of information on the worktape. An important special case of this measure can be interpreted as a kind of buffering complexity which counts the number of necessary block uploads into a virtual buffer on top of worktape. Thus, the distance measure can be used for investigating the buffering aspects of Turing computations. In this paper, we start this study by proving a tight separation and hierarchy result. In particular, we show that a very small increase in the distance complexity bound (roughly from c(n) to c(n + 1) + constant) brings provably more computational power to deterministic or nondeterministic Turing machines. For this purpose, we formulate a very general diagonalization method for Blum-like complexity measures. We also obtain a hierarchy of the distance complexity classes.
Trvalý link: http://hdl.handle.net/11104/0196307