The Experts below are selected from a list of 14148 Experts worldwide ranked by ideXlab platform
Damien Woods - One of the best experts on this subject based on the ideXlab platform.
-
the complexity of small universal Turing Machines a survey
arXiv: Computational Complexity, 2011Co-Authors: Turlough Neary, Damien WoodsAbstract:We survey some work concerned with small universal Turing Machines, cellular automata, tag systems, and other simple models of computation. For example it has been an open question for some time as to whether the smallest known universal Turing Machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing Machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these Machines are indeed efficient simulators. In addition, another related result shows that Rule 110, a well-known elementary cellular automaton, is efficiently universal. We also discuss some old and new universal program size results, including the smallest known universal Turing Machines. We finish the survey with results on generalised and restricted Turing machine models including Machines with a periodic background on the tape (instead of a blank symbol), multiple tapes, multiple dimensions, and Machines that never write to their tape. We then discuss some ideas for future work.
-
small weakly universal Turing Machines
Fundamentals of Computation Theory, 2009Co-Authors: Turlough Neary, Damien WoodsAbstract:We 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. Despite their small size these Machines are efficient polynomial time simulators of Turing Machines.
-
the complexity of small universal Turing Machines a survey
Theoretical Computer Science, 2009Co-Authors: Damien Woods, Turlough NearyAbstract:We survey some work concerned with small universal Turing Machines, cellular automata, tag systems, and other simple models of computation. For example, it has been an open question for some time as to whether the smallest known universal Turing Machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing Machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these Machines are indeed efficient simulators. As a related result, we also find that Rule 110, a well-known elementary cellular automaton, is also efficiently universal. We also review a large number of old and new universal program size results, including new small universal Turing Machines and new weakly, and semi-weakly, universal Turing Machines. We then discuss some ideas for future work arising out of these, and other, results.
-
four small universal Turing Machines
Machines Computations and Universality, 2009Co-Authors: Turlough Neary, Damien WoodsAbstract:We present universal Turing Machines with state-symbol pairs of (5, 5), (6, 4), (9, 3) and (15, 2). These Machines simulate our new variant of tag system, the bi-tag system and are the smallest known single-tape universal Turing Machines with 5, 4, 3 and 2-symbols, respectively. Our 5-symbolmachine uses the same number of instructions (22) as the smallest known universal Turing machine by Rogozhin. Also, all of the universalMachines we present here simulate Turing Machines in polynomial time.
-
small semi weakly universal Turing Machines
Machines Computations and Universality, 2009Co-Authors: Damien Woods, Turlough NearyAbstract:We present three small universal Turing Machines that have 3 states and 7 symbols, 4 states and 5 symbols, and 2 states and 13 symbols, respectively. These Machines are semi-weakly universal which means that on one side of the input they have an infinitely repeated word, and on the other side there is the usual infinitely repeated blank symbol. This work can be regarded as a continuation of early work by Watanabe on semi-weak Machines. One of our Machines has only 17 transition rules, making it the smallest known semi-weakly universal Turing machine. Interestingly, two of our Machines are symmetric with Watanabe's 7-state and 3-symbol, and 5-state and 4-symbol Machines, even though we use a different simulation technique.
Turlough Neary - One of the best experts on this subject based on the ideXlab platform.
-
the complexity of small universal Turing Machines a survey
arXiv: Computational Complexity, 2011Co-Authors: Turlough Neary, Damien WoodsAbstract:We survey some work concerned with small universal Turing Machines, cellular automata, tag systems, and other simple models of computation. For example it has been an open question for some time as to whether the smallest known universal Turing Machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing Machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these Machines are indeed efficient simulators. In addition, another related result shows that Rule 110, a well-known elementary cellular automaton, is efficiently universal. We also discuss some old and new universal program size results, including the smallest known universal Turing Machines. We finish the survey with results on generalised and restricted Turing machine models including Machines with a periodic background on the tape (instead of a blank symbol), multiple tapes, multiple dimensions, and Machines that never write to their tape. We then discuss some ideas for future work.
-
small weakly universal Turing Machines
Fundamentals of Computation Theory, 2009Co-Authors: Turlough Neary, Damien WoodsAbstract:We 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. Despite their small size these Machines are efficient polynomial time simulators of Turing Machines.
-
the complexity of small universal Turing Machines a survey
Theoretical Computer Science, 2009Co-Authors: Damien Woods, Turlough NearyAbstract:We survey some work concerned with small universal Turing Machines, cellular automata, tag systems, and other simple models of computation. For example, it has been an open question for some time as to whether the smallest known universal Turing Machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing Machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these Machines are indeed efficient simulators. As a related result, we also find that Rule 110, a well-known elementary cellular automaton, is also efficiently universal. We also review a large number of old and new universal program size results, including new small universal Turing Machines and new weakly, and semi-weakly, universal Turing Machines. We then discuss some ideas for future work arising out of these, and other, results.
-
four small universal Turing Machines
Machines Computations and Universality, 2009Co-Authors: Turlough Neary, Damien WoodsAbstract:We present universal Turing Machines with state-symbol pairs of (5, 5), (6, 4), (9, 3) and (15, 2). These Machines simulate our new variant of tag system, the bi-tag system and are the smallest known single-tape universal Turing Machines with 5, 4, 3 and 2-symbols, respectively. Our 5-symbolmachine uses the same number of instructions (22) as the smallest known universal Turing machine by Rogozhin. Also, all of the universalMachines we present here simulate Turing Machines in polynomial time.
-
small semi weakly universal Turing Machines
Machines Computations and Universality, 2009Co-Authors: Damien Woods, Turlough NearyAbstract:We present three small universal Turing Machines that have 3 states and 7 symbols, 4 states and 5 symbols, and 2 states and 13 symbols, respectively. These Machines are semi-weakly universal which means that on one side of the input they have an infinitely repeated word, and on the other side there is the usual infinitely repeated blank symbol. This work can be regarded as a continuation of early work by Watanabe on semi-weak Machines. One of our Machines has only 17 transition rules, making it the smallest known semi-weakly universal Turing machine. Interestingly, two of our Machines are symmetric with Watanabe's 7-state and 3-symbol, and 5-state and 4-symbol Machines, even though we use a different simulation technique.
Jack C H Lin - One of the best experts on this subject based on the ideXlab platform.
-
theory of one tape linear time Turing Machines
Theoretical Computer Science, 2010Co-Authors: Kohtaro Tadaki, Tomoyuki Yamakami, Jack C H LinAbstract:A theory of one-tape two-way one-head off-line linear-time Turing Machines is essentially different from its polynomial-time counterpart since these Machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing Machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing Machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing Machines and clarify how the Machines' resources affect their computational patterns and power.
-
theory of one tape linear time Turing Machines
Conference on Current Trends in Theory and Practice of Informatics, 2004Co-Authors: Kohtaro Tadaki, Tomoyuki Yamakami, Jack C H LinAbstract:A theory of one-tape linear-time Turing Machines is quite different from its polynomial-time counterpart. This paper discusses the computational complexity of one-tape Turing Machines of various machine types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing Machines) that halt in time O(n), where the running time of a machine is defined as the height of its computation tree. We also address a close connection between one-tape linear-time Turing Machines and finite state automata.
-
theory of one tape linear time Turing Machines
arXiv: Computational Complexity, 2003Co-Authors: Kohtaro Tadaki, Tomoyuki Yamakami, Jack C H LinAbstract:A theory of one-tape (one-head) linear-time Turing Machines is essentially different from its polynomial-time counterpart since these Machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing Machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing Machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing Machines and clarify how the Machines' resources affect their computational patterns and power.
John Watrous - One of the best experts on this subject based on the ideXlab platform.
-
revisiting the simulation of quantum Turing Machines by quantum circuits
Proceedings of The Royal Society A: Mathematical Physical and Engineering Sciences, 2019Co-Authors: Abel Molina, John WatrousAbstract:Yao's 1995 publication Quantum circuit complexity in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pp. 352361, proved that quantum Turing Machines and quantum ci...
-
revisiting the simulation of quantum Turing Machines by quantum circuits
arXiv: Computational Complexity, 2018Co-Authors: Abel Molina, John WatrousAbstract:Yao (1993) proved that quantum Turing Machines and uniformly generated quantum circuits are polynomially equivalent computational models: $t \geq n$ steps of a quantum Turing machine running on an input of length $n$ can be simulated by a uniformly generated family of quantum circuits with size quadratic in $t$, and a polynomial-time uniformly generated family of quantum circuits can be simulated by a quantum Turing machine running in polynomial time. We revisit the simulation of quantum Turing Machines with uniformly generated quantum circuits, which is the more challenging of the two simulation tasks, and present a variation on the simulation method employed by Yao together with an analysis of it. This analysis reveals that the simulation of quantum Turing Machines can be performed by quantum circuits having depth linear in $t$, rather than quadratic depth, and can be extended to variants of quantum Turing Machines, such as ones having multi-dimensional tapes. Our analysis is based on an extension of a method of Arrighi, Nesme, and Werner (2011) that allows for the localization of causal unitary evolutions.
Kohtaro Tadaki - One of the best experts on this subject based on the ideXlab platform.
-
theory of one tape linear time Turing Machines
Theoretical Computer Science, 2010Co-Authors: Kohtaro Tadaki, Tomoyuki Yamakami, Jack C H LinAbstract:A theory of one-tape two-way one-head off-line linear-time Turing Machines is essentially different from its polynomial-time counterpart since these Machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing Machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing Machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing Machines and clarify how the Machines' resources affect their computational patterns and power.
-
theory of one tape linear time Turing Machines
Conference on Current Trends in Theory and Practice of Informatics, 2004Co-Authors: Kohtaro Tadaki, Tomoyuki Yamakami, Jack C H LinAbstract:A theory of one-tape linear-time Turing Machines is quite different from its polynomial-time counterpart. This paper discusses the computational complexity of one-tape Turing Machines of various machine types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing Machines) that halt in time O(n), where the running time of a machine is defined as the height of its computation tree. We also address a close connection between one-tape linear-time Turing Machines and finite state automata.
-
theory of one tape linear time Turing Machines
arXiv: Computational Complexity, 2003Co-Authors: Kohtaro Tadaki, Tomoyuki Yamakami, Jack C H LinAbstract:A theory of one-tape (one-head) linear-time Turing Machines is essentially different from its polynomial-time counterpart since these Machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing Machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing Machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing Machines and clarify how the Machines' resources affect their computational patterns and power.
