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. (c) 2023 Elsevier Inc. All rights reserved.
Weight-reducing Turing machines / B. Guillon, G. Pighizzini, L. Prigioniero, D. Prusa. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 292:(2023), pp. 105030.1-105030.13. [10.1016/j.ic.2023.105030]
Weight-reducing Turing machines
G. Pighizzini
Secondo
;L. PrigionieroPenultimo
;
2023
Abstract
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. (c) 2023 Elsevier Inc. All rights reserved.File | Dimensione | Formato | |
---|---|---|---|
wrhm-part1.pdf
accesso aperto
Descrizione: Article - pre-print
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
554.21 kB
Formato
Adobe PDF
|
554.21 kB | Adobe PDF | Visualizza/Apri |
1-s2.0-S0890540123000317-main.pdf
accesso riservato
Descrizione: Article
Tipologia:
Publisher's version/PDF
Dimensione
429.4 kB
Formato
Adobe PDF
|
429.4 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.