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!
cited_by
cites cdi_FETCH-LOGICAL-c268t-45ad3bd766c531524449fcb653b48cee7d482a27a23054a893e977fb1457b5d93
container_end_page 432
container_issue 6
container_start_page 428
container_title Programming and computer software
container_volume 46
creator Marchenkov, S. S.
Makeev, S. D.
description 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.
doi_str_mv 10.1134/S0361768820060055
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2918628931</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2918628931</sourcerecordid><originalsourceid>FETCH-LOGICAL-c268t-45ad3bd766c531524449fcb653b48cee7d482a27a23054a893e977fb1457b5d93</originalsourceid><addsrcrecordid>eNp1kD1PhEAQhjdGE8_TH2BHYo3O7DeluahnvIuFWJMFFo8TAXeh4N8LotHEWE3xvM9M5iXkHOESkfGrJ2ASldSaAkgAIQ7IAiXokFGJh2Qx4XDix-TE-z0AAnC-IA_bJrdVWb8E277qys60NtiWtX8dAlPnQdy7T2ayXVlbH6RDEO-ctWH8K_hNT8lRYSpvz77mkjzf3sSrdbh5vLtfXW_CjErdhVyYnKW5kjITDAXlnEdFlkrBUq4za1XONTVUGcpAcKMjZiOlihS5UKnII7YkF_Pe1jXvvfVdsm96V48nExqhlnRUcEzhnMpc472zRdK68s24IUFIps6SP52NDp0d305_W_ez-X_pAweZbBE</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2918628931</pqid></control><display><type>article</type><title>Modeling Multitape Minsky and Turing Machines by Three-Tape Minsky Machines</title><source>Springer Nature:Jisc Collections:Springer Nature Read and Publish 2023-2025: Springer Reading List</source><creator>Marchenkov, S. S. ; Makeev, S. D.</creator><creatorcontrib>Marchenkov, S. S. ; Makeev, S. D.</creatorcontrib><description>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.</description><identifier>ISSN: 0361-7688</identifier><identifier>EISSN: 1608-3261</identifier><identifier>DOI: 10.1134/S0361768820060055</identifier><language>eng</language><publisher>Moscow: Pleiades Publishing</publisher><subject>Artificial Intelligence ; Computer Science ; Mathematical functions ; Operating Systems ; Software Engineering ; Software Engineering/Programming and Operating Systems ; Turing machines</subject><ispartof>Programming and computer software, 2020-11, Vol.46 (6), p.428-432</ispartof><rights>Pleiades Publishing, Ltd. 2020. ISSN 0361-7688, Programming and Computer Software, 2020, Vol. 46, No. 6, pp. 428–432. © Pleiades Publishing, Ltd., 2020. Russian Text © The Author(s), 2020, published in Programmirovanie, 2020, Vol. 46, No. 6.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c268t-45ad3bd766c531524449fcb653b48cee7d482a27a23054a893e977fb1457b5d93</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail></links><search><creatorcontrib>Marchenkov, S. S.</creatorcontrib><creatorcontrib>Makeev, S. D.</creatorcontrib><title>Modeling Multitape Minsky and Turing Machines by Three-Tape Minsky Machines</title><title>Programming and computer software</title><addtitle>Program Comput Soft</addtitle><description>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.</description><subject>Artificial Intelligence</subject><subject>Computer Science</subject><subject>Mathematical functions</subject><subject>Operating Systems</subject><subject>Software Engineering</subject><subject>Software Engineering/Programming and Operating Systems</subject><subject>Turing machines</subject><issn>0361-7688</issn><issn>1608-3261</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><recordid>eNp1kD1PhEAQhjdGE8_TH2BHYo3O7DeluahnvIuFWJMFFo8TAXeh4N8LotHEWE3xvM9M5iXkHOESkfGrJ2ASldSaAkgAIQ7IAiXokFGJh2Qx4XDix-TE-z0AAnC-IA_bJrdVWb8E277qys60NtiWtX8dAlPnQdy7T2ayXVlbH6RDEO-ctWH8K_hNT8lRYSpvz77mkjzf3sSrdbh5vLtfXW_CjErdhVyYnKW5kjITDAXlnEdFlkrBUq4za1XONTVUGcpAcKMjZiOlihS5UKnII7YkF_Pe1jXvvfVdsm96V48nExqhlnRUcEzhnMpc472zRdK68s24IUFIps6SP52NDp0d305_W_ez-X_pAweZbBE</recordid><startdate>202011</startdate><enddate>202011</enddate><creator>Marchenkov, S. S.</creator><creator>Makeev, S. D.</creator><general>Pleiades Publishing</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>8FE</scope><scope>8FG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>P5Z</scope><scope>P62</scope><scope>PHGZM</scope><scope>PHGZT</scope><scope>PKEHL</scope><scope>PQEST</scope><scope>PQGLB</scope><scope>PQQKQ</scope><scope>PQUKI</scope></search><sort><creationdate>202011</creationdate><title>Modeling Multitape Minsky and Turing Machines by Three-Tape Minsky Machines</title><author>Marchenkov, S. S. ; Makeev, S. D.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c268t-45ad3bd766c531524449fcb653b48cee7d482a27a23054a893e977fb1457b5d93</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Artificial Intelligence</topic><topic>Computer Science</topic><topic>Mathematical functions</topic><topic>Operating Systems</topic><topic>Software Engineering</topic><topic>Software Engineering/Programming and Operating Systems</topic><topic>Turing machines</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Marchenkov, S. S.</creatorcontrib><creatorcontrib>Makeev, S. D.</creatorcontrib><collection>CrossRef</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central UK/Ireland</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central (New)</collection><collection>ProQuest One Academic (New)</collection><collection>ProQuest One Academic Middle East (New)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Applied &amp; Life Sciences</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><jtitle>Programming and computer software</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Marchenkov, S. S.</au><au>Makeev, S. D.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Modeling Multitape Minsky and Turing Machines by Three-Tape Minsky Machines</atitle><jtitle>Programming and computer software</jtitle><stitle>Program Comput Soft</stitle><date>2020-11</date><risdate>2020</risdate><volume>46</volume><issue>6</issue><spage>428</spage><epage>432</epage><pages>428-432</pages><issn>0361-7688</issn><eissn>1608-3261</eissn><abstract>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.</abstract><cop>Moscow</cop><pub>Pleiades Publishing</pub><doi>10.1134/S0361768820060055</doi><tpages>5</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0361-7688
ispartof Programming and computer software, 2020-11, Vol.46 (6), p.428-432
issn 0361-7688
1608-3261
language eng
recordid cdi_proquest_journals_2918628931
source Springer Nature:Jisc Collections:Springer Nature Read and Publish 2023-2025: Springer Reading List
subjects Artificial Intelligence
Computer Science
Mathematical functions
Operating Systems
Software Engineering
Software Engineering/Programming and Operating Systems
Turing machines
title Modeling Multitape Minsky and Turing Machines by Three-Tape Minsky Machines
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-03-05T21%3A22%3A06IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Modeling%20Multitape%20Minsky%20and%20Turing%20Machines%20by%20Three-Tape%20Minsky%20Machines&rft.jtitle=Programming%20and%20computer%20software&rft.au=Marchenkov,%20S.%20S.&rft.date=2020-11&rft.volume=46&rft.issue=6&rft.spage=428&rft.epage=432&rft.pages=428-432&rft.issn=0361-7688&rft.eissn=1608-3261&rft_id=info:doi/10.1134/S0361768820060055&rft_dat=%3Cproquest_cross%3E2918628931%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c268t-45ad3bd766c531524449fcb653b48cee7d482a27a23054a893e977fb1457b5d93%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2918628931&rft_id=info:pmid/&rfr_iscdi=true