Small weakly universal Turing machines

Simple item page
dc.creatorNeary, Turlough
dc.creatorWoods, Damien
dc.date2007-07-30
dc.date.accessioned2026-07-07T08:21:16Z
dc.date.available2026-07-07T08:21:16Z
dc.descriptionWe give small universal Turing machines with state-symbol pairs of (6, 2), (3, 3) and (2, 4). These machines are weakly universal, which means that they have an infinitely repeated word to the left of their input and another to the right. They simulate Rule 110 and are currently the smallest known weakly universal Turing machines.
dc.identifierhttps://arxiv.org/abs/0707.4489
dc.identifierhttp://arxiv.org/abs/0707.4489
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/135306
dc.subjectComputational Complexity
dc.titleSmall weakly universal Turing machines
dc.typetext

Files

Collections

arXiv