{"created":"2025-02-21T04:40:16.496266+00:00","id":2008958,"links":{},"metadata":{"_buckets":{"deposit":"3296c91e-dc72-47a1-9766-4d984c967298"},"_deposit":{"created_by":41,"id":"2008958","owners":[41],"pid":{"revision_id":0,"type":"depid","value":"2008958"},"status":"published"},"_oai":{"id":"oai:hiroshima.repo.nii.ac.jp:02008958","sets":["1730444907710"]},"author_link":[],"item_1617186331708":{"attribute_name":"Title","attribute_value_mlt":[{"subitem_title":"A 1-Tape 2-Symbol Reversible Turing Machine","subitem_title_language":"en"}]},"item_1617186419668":{"attribute_name":"Creator","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Morita, Kenichi","creatorNameLang":"en"}],"familyNames":[{"familyName":"Morita","familyNameLang":"en"}],"givenNames":[{"givenName":"Kenichi","givenNameLang":"en"}]},{"creatorNames":[{"creatorName":"Shirasaki, Akihiko","creatorNameLang":"en"}],"familyNames":[{"familyName":"Shirasaki","familyNameLang":"en"}],"givenNames":[{"givenName":"Akihiko","givenNameLang":"en"}]},{"creatorNames":[{"creatorName":"Yoshifumi, Gono","creatorNameLang":"en"}],"familyNames":[{"familyName":"Yoshifumi","familyNameLang":"en"}],"givenNames":[{"givenName":"Gono","givenNameLang":"en"}]}]},"item_1617186476635":{"attribute_name":"Access Rights","attribute_value_mlt":[{"subitem_access_right":"open access","subitem_access_right_uri":"http://purl.org/coar/access_right/c_abf2"}]},"item_1617186499011":{"attribute_name":"Rights","attribute_value_mlt":[{"subitem_rights":"Copyright (c) 1989 IEICE"}]},"item_1617186609386":{"attribute_name":"Subject","attribute_value_mlt":[{"subitem_subject":"reversible computing","subitem_subject_scheme":"Other"},{"subitem_subject":"Turing machine","subitem_subject_scheme":"Other"}]},"item_1617186626617":{"attribute_name":"Description","attribute_value_mlt":[{"subitem_description":"Bennett proved that any irreversible Turing machine can be simulated by reversible one. However, Bennett's reversible machine uses 3 tapes and many tape symbols. Previously, Gono and Morita showed that the number of symbols can be reduced to 2. In this paper, by improving these methods, we give a procedure to convert an irreversible machine into an equivalent 1-tape 2-symbol reversible machine. First, it is shown that the \"state-degeneration degree\" of any Turing machine can be reduced to 2 or less. Using this result and some other techniques, a given irreversible machine is converted into a 1-tape 32-symbol (i.e., 5-track 2-symbol) reversible machine. Finally the 32-symbol machine is converted into a 1-tape 2-symbol reversible machine. From this result, it is seen that a 1-tape 2-symbol reversible Turing machine is computation universal.","subitem_description_language":"en"}]},"item_1617186643794":{"attribute_name":"Publisher","attribute_value_mlt":[{"subitem_publisher":"電子情報通信学会"}]},"item_1617186702042":{"attribute_name":"Language","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_1617186920753":{"attribute_name":"Source Identifier","attribute_value_mlt":[{"subitem_source_identifier":"0913-574X","subitem_source_identifier_type":"ISSN"},{"subitem_source_identifier":"AA10684666","subitem_source_identifier_type":"NCID"}]},"item_1617187024783":{"attribute_name":"Page Start","attribute_value_mlt":[{"subitem_start_page":"223"}]},"item_1617187056579":{"attribute_name":"Bibliographic Information","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"1989-03-25","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicPageEnd":"228","bibliographicPageStart":"223","bibliographicVolumeNumber":"E72","bibliographic_titles":[{"bibliographic_title":"The Transactions of the IEICE"},{"bibliographic_title":"The Transactions of the IEICE"}]}]},"item_1617258105262":{"attribute_name":"Resource Type","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_1617265215918":{"attribute_name":"Version Type","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_1617353299429":{"attribute_name":"Relation","attribute_value_mlt":[{"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://search.ieice.org/bin/summary.php?id=e72-e_3_223&category=E&lang=E&year=1989&abst=","subitem_relation_type_select":"URI"}},{"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://search.ieice.org/","subitem_relation_type_select":"URI"}}]},"item_1617605131499":{"attribute_name":"File","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_access","date":[{"dateType":"Available","dateValue":"2023-03-18"}],"displaytype":"simple","filename":"TransIEICE_E72-3_223.pdf","filesize":[{"value":"440.9 KB"}],"mimetype":"application/pdf","url":{"objectType":"fulltext","url":"https://hiroshima.repo.nii.ac.jp/record/2008958/files/TransIEICE_E72-3_223.pdf"},"version_id":"7cb38c57-1ecc-4f76-a867-e222a9b9364c"}]},"item_1732771732025":{"attribute_name":"旧ID","attribute_value":"48448"},"item_title":"A 1-Tape 2-Symbol Reversible Turing Machine","item_type_id":"40003","owner":"41","path":["1730444907710"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2023-03-18"},"publish_date":"2023-03-18","publish_status":"0","recid":"2008958","relation_version_is_last":true,"title":["A 1-Tape 2-Symbol Reversible Turing Machine"],"weko_creator_id":"41","weko_shared_id":-1},"updated":"2025-02-22T04:39:51.814631+00:00"}