A physically universal Turing machine

Tietueen suppeat tiedot
dc.contributor.authorSalo Ville
dc.contributor.authorTörmä Ilkka
dc.contributor.organizationfi=matematiikka|en=Mathematics|
dc.contributor.organization-code1.2.246.10.2458963.20.41687507875
dc.converis.publication-id177553931
dc.converis.urlhttps://research.utu.fi/converis/portal/Publication/177553931
dc.date.accessioned2025-08-27T22:46:20Z
dc.date.available2025-08-27T22:46:20Z
dc.description.abstract<p>We construct a two-dimensional <a href="https://www.sciencedirect.com/topics/computer-science/turing-machines" title="Learn more about Turing machine from ScienceDirect's AI-generated Topic Pages">Turing machine</a> that is physically universal in both the moving tape and moving head model. In particular, it is mixing of all finite orders in both models. We also provide a variant that is physically universal in the moving tape model, but not in the moving head model.</p>
dc.format.pagerange44
dc.identifier.jour-issn0022-0000
dc.identifier.olddbid202779
dc.identifier.oldhandle10024/185806
dc.identifier.urihttps://www.utupub.fi/handle/11111/48855
dc.identifier.urlhttps://doi.org/10.1016/j.jcss.2022.08.003
dc.identifier.urnURN:NBN:fi-fe2023022528654
dc.language.isoen
dc.okm.affiliatedauthorSalo, Ville
dc.okm.affiliatedauthorTörmä, Ilkka
dc.okm.discipline113 Computer and information sciencesen_GB
dc.okm.internationalcopublicationnot an international co-publication
dc.okm.internationalityInternational publication
dc.okm.typeA1 ScientificArticle
dc.publisherAcademic Press
dc.publisher.countryUnited Statesen_GB
dc.publisher.countryYhdysvallat (USA)fi_FI
dc.publisher.country-codeUS
dc.relation.doi10.1016/j.jcss.2022.08.003
dc.relation.ispartofjournalJournal of Computer and System Sciences
dc.relation.volume132
dc.source.identifierhttps://www.utupub.fi/handle/10024/185806
dc.titleA physically universal Turing machine
dc.year.issued2023

Tiedostot

Näytetään 1 - 1 / 1
Name:
1-s2.0-S0022000022000617-main.pdf
Size:
747.79 KB
Format:
Adobe Portable Document Format
Lataa

Kokoelmat

Rinnakkaistallenteet