Modeling Multitape Minsky and Turing Machines by Three-Tape Minsky Machines

Autor:	Sergey Seraphimovich Marchenkov, S. D. Makeev
Rok vydání:	2020
Předmět:	Discrete mathematics Turing machine symbols.namesake TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Computer science Encoding (memory) symbols Software Word (computer architecture)
Zdroj:	Programming and Computer Software. 46:428-432
ISSN:	1608-3261 0361-7688
DOI:	10.1134/s0361768820060055
Popis:	In this paper, we prove that a k-tape Minsky machine operating with time $$T(n)$$ can be modeled by a three-tape Minsky machine in a time not exceeding $$T{{(n)}^{k}} \times \log T(n)$$ . It is shown that multitape Turing machines can be modeled by three-tape Minsky machines with optimal word encoding.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::68da9891c66e513bc9809289feae7fae https://doi.org/10.1134/s0361768820060055 Zobrazit plný text záznamu Full text from SpringerLink