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

Altmetrics

Downloads

2 downloads since deposited on 23 Feb 2018
2 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:14 Mar 2018 18:01
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