×

zbMATH — the first resource for mathematics

Turing machines, transition systems, and interaction. (English) Zbl 1090.68040
Summary: 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.

MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Software:
Esterel
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] D. Goldin, S. Smolka, P. Wegner, Turing machines, transition systems, and interaction, Electronic Notes in Theoretical Computer Science 52, Elsevier, 2002 · Zbl 1260.68267
[2] Milner, R., Elements of interaction: Turing award lecture, Commun. ACM, 36, 1, 78-89, (1993)
[3] van Leeuwen, J.; Wiedermann, J., The Turing machine paradigm in contemporary computing, () · Zbl 1012.68068
[4] P. Wegner, Why interaction is more powerful than algorithms, Commun. ACM 40 (5), May 1997
[5] P. Wegner, Interactive foundations of computing, Theoret. Comput. Sci. 192, February 1998 · Zbl 0897.68041
[6] Boudol, G., Notes on algebraic calculi of processes, (), 261-303 · Zbl 0578.68025
[7] de Simone, R., Higher-level synchronizing devices in MEIJE-SCCS, Theoret. comput. sci., 37, 245-267, (1985) · Zbl 0598.68027
[8] Baeten, J.; Bergstra, J.; Klop, J., On the consistency of koomen’s fair abstraction rule, Theoret. comput. sci., 51, 1/2, 129-176, (1987) · Zbl 0621.68010
[9] B.S. Bloom, S. Istrail, A.R. Meyer, Bisimulation can’t be traced, in: Proc. 15th ACM Symposium on Principles of Programming Languages, 1988 · Zbl 0886.68027
[10] P. Darondeau, Concurrency and computability, in: I. Guessarian (Ed.), Semantics of Systems of Concurrent Processes, Proc. LITP Spring School on Theoretical Computer Science, LNCS 469, Springer, Berlin, La Roche Posay, France, 1990
[11] F.W. Vaandrager, Expressiveness results for process algebras, Tech. Rep. CS-R9301, Centrum voor Wiskunde en Informatica, Amsterdam, 1993
[12] Brookes, S.D.; Roscoe, A.W., An improved failures model for communicating sequential processes, () · Zbl 0565.68023
[13] Hopcroft, J.; Motwani, R.; Ullman, J., Introduction to automata theory, languages, and computation, (2001), Addison-Wesley Boston · Zbl 0980.68066
[14] A. Pnueli, M. Shalev, What is in a step: on the semantics of Statecharts, in: Theoretical Aspects of Computer Software, No. 526 in Lecture Notes in Computer Science, 1991, pp. 244-264
[15] J. Barwise, L. Moss, Vicious circles, CSLI Lecture Notes #60, Cambridge University Press, Cambridge, 1996
[16] Lamport, L., Proving the correctness of multiprocess programs, IEEE transactions on software engineering SE-3, 2, 125-143, (1977) · Zbl 0349.68006
[17] Alpern, B.; Schneider, F., Recognizing safety and liveness, Distributed comput., 2, 3, 117-126, (1987) · Zbl 0641.68039
[18] Lynch, N.; Vaandrager, F., Forward and backward simulations—part I: untimed systems, Inform. comput., 121, 2, 214-233, (1995) · Zbl 0834.68123
[19] Dijkstra, E.W., A discipline of programming, (1976), Prentice-Hall Engle-wood Cliffs, NJ · Zbl 0286.00013
[20] Prasse, M.; Rittgen, P., Why church’s thesis still holds: some notes on Peter wegner’s tracts on interaction and computability, Comput. J., 41, 6, 357-362, (1998) · Zbl 0929.68069
[21] A.M. Turing, On computable numbers with an application to the Entscheidungsproblem, in: Proceedings of the London Math Society, vol. 2 (4), 1936, pp. 230-265, reprinted in Martin Davis, Ed., The Undecidable, Raven, New York, 1965, pp. 116-151 · Zbl 0016.09701
[22] Papadimitriou, C., Computational complexity, (1994), Addison-Wesley Reading, MA · Zbl 0833.68049
[23] D. Goldin, S. Srinivasa, B. Thalheim, Information systems=databases + interaction: towards principles of information system design, in: Proc. ER 2000, Salt Lake City, Utah, 2000
[24] Eberbach, E.; Goldin, D.; Wegner, P., Turing’s ideas and models of computation, ()
[25] P. Wegner, D. Goldin, Coinductive models of finite computing agents, Electronic Notes in Theoretical Computer Science 19, Elsevier, 2000 · Zbl 0918.68023
[26] Russell, S.J.; Norvig, P., Artificial intelligence: A modern approach, (1995), Prentice-Hall Upper Saddle River, NJ · Zbl 0835.68093
[27] Y.-J. Chiang, R. Tamassia, Dynamic algorithms in computational geometry, in Proceedings of the IEEE, Special Issue on Computational Geometry, vol. 80 (9), 1992, pp. 362-381
[28] S. Albers, Online algorithms, in: Goldin et al. [57], forthcoming · Zbl 1266.68233
[29] D. Goldin, P. Wegner, Persistence as a form of interaction, Brown University Tech. Rep. CS-98-07, July 1998
[30] D. Goldin, Persistent turing machines as a model of interactive computation, in: K.-D. Schewe, B. Thalheim (Eds.), Foundations of Information and Knowledge Systems, First International Symposium, LNCS 1762, Springer, Berlin, 2000, pp. 116-135 · Zbl 0961.68048
[31] G. Kahn, D.B. MacQueen, Coroutines and networks of parallel processes, in: Proceedings of the IFIP Congress 77, North-Holland, 1977 · Zbl 0363.68076
[32] P. Panangaden, E.W. Stark, Computations, residuals, and the power of indeterminancy, in: Proceedings of the 15th ICALP, Lecture Notes in Computer Science, vol. 317, Springer, Berlin, 1988, pp. 439-454
[33] A.M. Rabinovich, B.A. Trakhtenbrot, Communication among relations, in: Paterson [58], pp. 294-307 · Zbl 0765.68110
[34] P. Panangaden, V. Shanbhogue, E.W. Stark, Stability and sequentiality in dataflow networks, in: Paterson [58], pp. 308-321 · Zbl 0766.68090
[35] Kahn, G.; Plotkin, G., Concrete domains, Theoret. comput. sci., 121, 1-2, 187-277, (1993) · Zbl 0809.68085
[36] Bucciarelli, A.; Ehrhard, T., Sequentiality in an extensional framework, Inform. comput., 110, 2, 265-296, (1994) · Zbl 0807.68064
[37] Milner, R., Communication and concurrency, international series in computer science, (1989), Prentice Hall
[38] Milner, R.; Parrow, J.; Walker, D., A calculus of mobile processes, parts I and II, Inform. comput., 100, 1-77, (1992)
[39] Harel, D., Statecharts: a visual formalism for complex systems, Sci. comput. program., 8, 231-274, (1987) · Zbl 0637.68010
[40] Berry, G.; Gonthier, G., The ESTEREL synchronous programming language: design, semantics, implementation, Sci. comput. program., 19, 87-152, (1992) · Zbl 0772.68013
[41] J. Esparza, D. Hansel, P. Rossmanith, S. Schwoon, Efficient algorithms for model checking pushdown systems, in: Proc. CAV’2000, LNCS 1855, Springer, Berlin, 2000, pp. 232-247 · Zbl 0974.68116
[42] Burkart, O.; Caucal, D.; Moller, F.; Steffen, B., Verification on infinite structures, () · Zbl 1035.68067
[43] S. Abramsky, Concurrent interaction games, in: J. Davies, A.W. Roscoe, J. Woodcock (Eds.), Millenial Perspectives in Computer Science, Pal-grave, 2000, pp. 1-12
[44] V. Saraswat, M. Rinard, Concurrent constraint programming, in: Proceedings of the 17th Annual ACM Symposium on Principles of Programming Languages, San Francisco, CA, 1990, pp. 232-245
[45] Manna, Z.; Pnueli, A., The temporal logic of reactive and concurrent systems, (1992), Springer Berlin, Heidelberg, New York
[46] Alur, R.; Henzinger, T.A., Reactive modules, Formal methods system design, 15, 7-48, (1999)
[47] Lynch, N.A., Distributed algorithms, (1996), Morgan Kaufmann · Zbl 0877.68061
[48] J. van Leeuwen, J. Wiedermann, A computational model of interaction in embedded systems, Tech. Rep. UU-CS-02-2001, Department of Computer Science, Utrecht University, 2001 · Zbl 1011.68503
[49] S. Kosub, Some remarks towards dynamic analysis of computation, Manuscript, Institut fur Informatik, Julius Maximilians Universitat, Wurzburg, March 1998
[50] S. Kosub, Persistent computations, Tech. Rep. 217, December 1998
[51] Fischer, M.J.; Stockmeyer, L.J., Fast on-line integer multiplication, J. comput. system sci., 9, 3, 317-331, (1974) · Zbl 0289.68016
[52] Goldreich, O., Foundations of cryptography, vol. I, (2001), Cambridge University Press Cambridge
[53] B. Ekdahl, Interactive computing does not supersede Church’s thesis, in: Proceedings of the 17th Confernce on International Association of Management, 1999, pp. 261-265
[54] D. Keil, D. Goldin, Modeling indirect interaction in open computational systems, in: WETICE 2003, IEEE Press, 2003, pp. 371-376
[55] D. Goldin, D. Keil, Toward domain-independent formalization of indirect interaction, in: WETICE 2004, IEEE Press
[56] M. Broy, Interactive computation: the new paradigm, in: Goldin et al. [57], forthcoming
[57] D. Goldin, S. Smolka, P. Wegner (Eds.), Interaction: A New Computational Paradigm, Springer, Heidelberg, Germany, 2005, forthcoming
[58] M. Paterson (Ed.), Automata, Languages and Programming (ICALP ’90), vol. 443 of Lecture Notes in Computer Science, Springer, Berlin, Warwick, England, 1990
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.