Turing machines, transition systems, and interaction

详细信息    查看全文

• 作者：Goldin ; Dina Q. ; Smolka ; Scott A. ; Attie ; Paul C. ; Sonderegger ; Elaine L.
• 关键词：Models of interactive computation ; Persistent Turing machine ; Persistent stream language ; Interactive transition system ; Sequential interactive computation
• 刊名：Information and Computation
• 出版年：2004
• 出版时间：November 1, 2004
• 年：2004
• 卷：194
• 期：2
• 页码：101-128
• 全文大小：326 K

文摘

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 aaanormalaaa 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.