• About
  • About the Department
  • Contact
  • Directions
  • Partners
  • Rooms
  • Systems & Software
  • Conduit
  • News
  • Events
• People
  • Our Community
  • Faculty
  • Staff
  • Grad Students
  • Ugrad Students
  • Alums
  • Directory
• Research
  • Research Links
  • Areas
  • Publications
• Degrees
  • Degree Programs
  • Doctoral
  • Masters
  • Undergrad
  • Programs
  • Miscellaneous
• Courses
  • Course List
  • Schedule
  • Sections
  • TA Program

Tech Report CS-99-14

Behavior and Expressiveness of Persistent Turing Machines

Dina Goldin and Peter Wegner

September 1999

Abstract:

D. Goldin, Univ. of Massachusetts - Boston P. Wegner, Brown University Persistent Turing machines (PTMs) are multitape machines with a persistent worktape preserved between successive interactions. They are a minimal extension of Turing machines (TMs) that express interactive behavior. Their behavior is characterized by input-output streams; PTM equivalence and expressiveness are defined relative to its behavior. Four different models of PTM behavior are examined: language-based, automaton-based, observation-based, and function-based. A number of special subclasses of PTMs are identified, and several expressiveness results are obtained, both for the general class of all PTMs and for the special subclasses. The methods, formalisms, and tools for studying models of PTM computation developed in this paper can serve as a basis for a more comprehensive theory of interactive computation.

(complete text in pdf or gzipped postscript)