Turing machines, transition systems, and interaction Export

@article{citeulike:240919, abstract = {This paper presents persistent Turing machines (PTMs), a new way of interpreting Turing-machine computation, based on dynamic stream semantics. A PTM is a Turing machine that performs an infinite sequence of "normal" Turing machine computations, where each such computation starts when the PTM reads an input from its input tape and ends when the PTM produces an output on its output tape. The PTM has an additional worktape, which retains its content from one computation to the next; this is what we mean by persistence.A number of results are presented for this model, including a proof that the class of PTMs is isomorphic to a general class of effective transition systems called interactive transition systems; and a proof that PTMs without persistence (amnesic PTMs) are less expressive than PTMs. As an analogue of the Church-Turing hypothesis which relates Turing machines to algorithmic computation, it is hypothesized that PTMs capture the intuitive notion of sequential interactive computation.}, author = {Goldin, Dina Q. and Smolka, Scott A. and Attie, Paul C. and Sonderegger, Elaine L.}, citeulike-article-id = {240919}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1044145.1044148}, citeulike-linkout-1 = {http://dx.doi.org/10.1016/j.ic.2004.07.002}, citeulike-linkout-2 = {http://www.sciencedirect.com/science/article/B6WGK-4DCMFR3-2/2/29b26bfd92e37e2fcac8a2d94dd78410}, day = {01}, doi = {10.1016/j.ic.2004.07.002}, journal = {Information and Computation}, month = {November}, number = {2}, pages = {101--128}, posted-at = {2008-02-01 11:19:55}, priority = {0}, title = {Turing machines, transition systems, and interaction}, url = {http://dx.doi.org/10.1016/j.ic.2004.07.002}, volume = {194}, year = {2004} }

TY - JOUR ID - citeulike:240919 L3 - citeulike-article-id:240919 N2 - This paper presents persistent Turing machines (PTMs), a new way of interpreting Turing-machine computation, based on dynamic stream semantics. A PTM is a Turing machine that performs an infinite sequence of "normal" Turing machine computations, where each such computation starts when the PTM reads an input from its input tape and ends when the PTM produces an output on its output tape. The PTM has an additional worktape, which retains its content from one computation to the next; this is what we mean by persistence.A number of results are presented for this model, including a proof that the class of PTMs is isomorphic to a general class of effective transition systems called interactive transition systems; and a proof that PTMs without persistence (amnesic PTMs) are less expressive than PTMs. As an analogue of the Church-Turing hypothesis which relates Turing machines to algorithmic computation, it is hypothesized that PTMs capture the intuitive notion of sequential interactive computation. IS - 2 JF - Information and Computation EP - 128 TI - Turing machines, transition systems, and interaction VL - 194 SP - 101 AU - Goldin, Dina AU - Smolka, Scott AU - Attie, Paul AU - Sonderegger, Elaine PY - 2004/11/01/ UR - http://dx.doi.org/10.1016/j.ic.2004.07.002 ER -