Weight-reducing Turing machines

Autor: Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, Daniel Průša
Přispěvatelé: Université Clermont Auvergne (UCA), Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Università degli Studi di Milano = University of Milan (UNIMI), Dipartimento di Informatica, Czech Technical University in Prague (CTU), Dipartimento di Informatica (ISLab)
Rok vydání: 2023
Předmět:
Zdroj: Information and Computation
Information and Computation, 2023, 292, pp.105030. ⟨10.1016/j.ic.2023.105030⟩
ISSN: 0890-5401
1090-2651
DOI: 10.1016/j.ic.2023.105030
Popis: International audience; 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 doublyexponential increase in size, respectively. These costs cannot be reduced in the worst case.
Databáze: OpenAIRE
Externí odkaz: