Weight-reducing Turing machines
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00367675" target="_blank" >RIV/68407700:21230/23:00367675 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1016/j.ic.2023.105030" target="_blank" >https://doi.org/10.1016/j.ic.2023.105030</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ic.2023.105030" target="_blank" >10.1016/j.ic.2023.105030</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Weight-reducing Turing machines
Popis výsledku v původním jazyce
It is well known that one-tape Turing machines running in linear time are no more powerful than finite automata; namely they recognize exactly the class of regular languages. We prove that it is not decidable if a one-tape machine runs in linear time, even if it is deterministic and restricted to use only the portion of the tape that initially contains the input. This motivates the introduction of a constructive variant of one-tape machines, called a weight-reducing machine, and the investigation of its properties. We focus on the deterministic case. In particular, we show that, paying a polynomial size increase only, each weight-reducing machine can be turned into a halting one that runs in linear time. Furthermore each weight-reducing machine can be converted into equivalent nondeterministic and deterministic finite automata by paying an exponential and doubly-exponential increase in size, respectively. These costs cannot be reduced in the worst case.
Název v anglickém jazyce
Weight-reducing Turing machines
Popis výsledku anglicky
It is well known that one-tape Turing machines running in linear time are no more powerful than finite automata; namely they recognize exactly the class of regular languages. We prove that it is not decidable if a one-tape machine runs in linear time, even if it is deterministic and restricted to use only the portion of the tape that initially contains the input. This motivates the introduction of a constructive variant of one-tape machines, called a weight-reducing machine, and the investigation of its properties. We focus on the deterministic case. In particular, we show that, paying a polynomial size increase only, each weight-reducing machine can be turned into a halting one that runs in linear time. Furthermore each weight-reducing machine can be converted into equivalent nondeterministic and deterministic finite automata by paying an exponential and doubly-exponential increase in size, respectively. These costs cannot be reduced in the worst case.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA19-21198S" target="_blank" >GA19-21198S: Složité predikční modely a jejich učení z částečně anotovaných dat</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2023
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 periodika
Information and Computation
ISSN
0890-5401
e-ISSN
1090-2651
Svazek periodika
292
Číslo periodika v rámci svazku
June
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
13
Strana od-do
—
Kód UT WoS článku
000981888800001
EID výsledku v databázi Scopus
2-s2.0-85151530958