Weight-reducing Turing machines
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Weight-reducing Turing machines
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-21198S" target="_blank" >GA19-21198S: Complex prediction models and their learning from weakly annotated data</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Information and Computation
ISSN
0890-5401
e-ISSN
1090-2651
Volume of the periodical
292
Issue of the periodical within the volume
June
Country of publishing house
US - UNITED STATES
Number of pages
13
Pages from-to
—
UT code for WoS article
000981888800001
EID of the result in the Scopus database
2-s2.0-85151530958