A Turing Machine Distance Hierarchy

Autoři: Stanislav Žák
doc. RNDr. Jiří Šíma, DSc.
Rok vydání: 2013
Typ publikace: Konferenční příspěvek (mezinárodní konf.)
Periodikum: Language and Automata Theory and Applications
Projekty: NoSCoM: nestandardní výpočetní modely a jejich aplikace ve složitosti, lingvistice a učení
Centrum excelence - Institut teoretické informatiky (CE-ITI)
Bibliografická citace: ŽÁK, Stanislav, ŠÍMA, Jiří. A Turing Machine Distance Hierarchy. In: DEDIU, A.H., MARTÍN-VIDE, C., TRUTHE, B., eds. Language and Automata Theory and Applications. Berlin: Springer, 2013, S. 570-578. Lecture Notes in Computer Science, 7810. ISBN 978-3-642-37063-2. ISSN 0302-9743
Dostupné z: doi:10.1007/978-3-642-37064-9_50
DOI: 10.1007/978-3-642-37064-9_50
ID: 383266

Abstrakt

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.