A Turing Machine Distance Hierarchy
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F13%3A00383266" target="_blank" >RIV/67985807:_____/13:00383266 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-37064-9_50" target="_blank" >http://dx.doi.org/10.1007/978-3-642-37064-9_50</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-37064-9_50" target="_blank" >10.1007/978-3-642-37064-9_50</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A Turing Machine Distance Hierarchy
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
A Turing Machine Distance Hierarchy
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2013
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Language and Automata Theory and Applications
ISBN
978-3-642-37063-2
ISSN
0302-9743
e-ISSN
—
Počet stran výsledku
9
Strana od-do
570-578
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Bilbao
Datum konání akce
2. 4. 2013
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—