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

In this paper, we prove that a k -tape Minsky machine operating with time can be modeled by a three-tape Minsky machine in a time not exceeding . It is shown that multitape Turing machines can be modeled by three-tape Minsky machines with optimal word encoding.

Saved in:
Bibliographic Details
Published in:Programming and computer software 2020-11, Vol.46 (6), p.428-432
Main Authors: Marchenkov, S. S., Makeev, S. D.
Format: Article
Language:English
Subjects:
Artificial Intelligence
Computer Science
Mathematical functions
Operating Systems
Software Engineering
Software Engineering/Programming and Operating Systems
Turing machines
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we prove that a k -tape Minsky machine operating with time can be modeled by a three-tape Minsky machine in a time not exceeding . It is shown that multitape Turing machines can be modeled by three-tape Minsky machines with optimal word encoding.
ISSN:0361-7688
1608-3261
DOI:10.1134/S0361768820060055