Quasilinear Emulation of Turing Machines by S-machines

arXiv2304.07603MaRDI QIDQ6433201FDOQ6433201

Authors: Bogdan Chornomaz, Francis Wagner 

Publication date: 15 April 2023

Abstract: We prove that for any $varepsilon>0$, a non-deterministic Turing machine $mathcalT$ with time complexity $T(n)$ can be emulated by an $S$-machine with time and space complexities at most $T(n{)}^{1+varepsilon}$ and $T(n)$, respectively. This improves the bounds on the emulation in arXiv:math/9811105 and leads to improved bounds in the main theorem of arXiv:math/9811106. In particular, for a non-hyperbolic finitely generated group $G$ whose word problem has linear time complexity, this yields an embedding of $G$ into a finitely presented group $H$ such that $G$ has bounded distortion in $H$ and the Dehn function of $G$ in $H$ is bounded above by $n^{2+varepsilon}$, an optimal bound modulo the $varepsilon$ factor. As a means to this end, we introduce and develop the theory of $S$-graphs, giving a different perspective on the construction of $S$-machines akin to a crude object-oriented programming language.

This page was built for publication: Quasilinear Emulation of Turing Machines by S-machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433201)