Header

UZH-Logo

Maintenance Infos

2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets


Neary, Turlough (2017). 2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets. In: 19th International Conference on Descriptional Complexity of Formal Systems, Milan, 3 July 2017 - 5 July 2017, 274-286.

Abstract

We say that a Turing machine has periodic support if there is an infinitely repeated word to the left of the input and another infinitely repeated word to the right. In the search for the smallest universal Turing machines, machines that use periodic support have been significantly smaller than those for the standard model (i.e. machines with the usual blank tape on either side of the input). While generalising the model allows us to construct smaller universal machines it makes proving decidability results for the various state-symbol products that restrict program size more difficult. Here we show that given an arbitrary 2-state 2-symbol Turing machine and a configuration with periodic support the set of reachable configurations is regular. Unlike previous decidability results for 2-state 2-symbol machines, here we include in our consideration machines that do not reserve a transition rule for halting, which further adds to the difficulty of giving decidability results.

Abstract

We say that a Turing machine has periodic support if there is an infinitely repeated word to the left of the input and another infinitely repeated word to the right. In the search for the smallest universal Turing machines, machines that use periodic support have been significantly smaller than those for the standard model (i.e. machines with the usual blank tape on either side of the input). While generalising the model allows us to construct smaller universal machines it makes proving decidability results for the various state-symbol products that restrict program size more difficult. Here we show that given an arbitrary 2-state 2-symbol Turing machine and a configuration with periodic support the set of reachable configurations is regular. Unlike previous decidability results for 2-state 2-symbol machines, here we include in our consideration machines that do not reserve a transition rule for halting, which further adds to the difficulty of giving decidability results.

Statistics

Citations

Dimensions.ai Metrics
1 citation in Web of Science®
1 citation in Scopus®
1 citation in Microsoft Academic
Google Scholar™

Altmetrics

Downloads

3 downloads since deposited on 23 Feb 2018
3 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), not_refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Neuroinformatics
Dewey Decimal Classification:570 Life sciences; biology
Language:English
Event End Date:5 July 2017
Deposited On:23 Feb 2018 10:24
Last Modified:31 Jul 2018 05:13
Publisher:Springer
Number of Pages:13
OA Status:Green
Publisher DOI:https://doi.org/10.1007/978-3-319-60252-3_22

Download

Download PDF  '2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets'.
Preview
Content: Accepted Version
Filetype: PDF
Size: 296kB
View at publisher