Catálogo de publicaciones - libros

This essay is a slightly edited transcription of a lecture given in 1997 in King’s College, Cambridge, where Alan Turing had been a Fellow. The lecture was part of a meeting to celebrate the 60th anniversary of the publication of Turing’s paper , published in the in 1937.

This chapter offers a rough sketch of the landscape of computing with the specific aim of identifying and interrelating well-established topics such as computability and concurrency to newer areas such as interaction and composition of behavior.

This chapter explores the authors’ 10-year contributions to interactive computing, with special emphasis on the philosophical question of how truth has been used and misused in computing and other disciplines. We explore the role of and in formulating true principles of computer science, politics, and religion. We show that interaction is an empiricist rather than rationalist principle, and that rationalist proponents of computing have been the strongest opponents of our belief that interaction provides an empirical foundation for both computer problem solving and human behavior. The rationalist position was adopted by Pythagoras, Descartes, Kant, and many modern philosophers; our interactive approach to computing suggests that empiricism provides a better framework for understanding principles of computing.

We provide an empirical analysis of questions like “can machines think”, and “why interaction is more powerful than algorithms”. We discuss as a model of sequential interaction that formally proves the greater power of interaction over algorithms and Turing machines. We explain that the , formulated by theorists in the 1960s, violates Turing’s original thesis about unsolvability of the decision problem and is a myth, in the sense that it departs from the principles of Turing’s unsolvability result in his 1936 paper. Our analysis contributes to the book’s goals towards the acceptance of interactive computing as a principle that goes beyond Turing machine models of computer problem solving.

We study models, specification, and refinement techniques of distributed interactive software systems composed of interfaces and components. A theory for the interaction between such systems is given. We concentrate on the interaction between systems and their environments as well as the interaction between the components of systems. We show how to model interfaces and interactions by logical formulas in the style of design by contract, by state machines, and streams of messages and signals. This leads to a theory interface abstraction of systems, which is essential for an interaction view. In particular, we treat interaction refinement. We introduce a service concept that is purely based on interaction.

In order to check whether an open system satisfies a desired property, we need to check the behavior of the system with respect to an arbitrary environment. In the most general setting, the environment is another open system. Given an open system and a property , we say that iff for every open system , which serves as an environment to , the composition satisfies . The problem of is then to decide, given and , whether robustly satisfies . In essence, robust model checking focuses on reasoning algorithmically about interaction. In this work we study the robust-model-checking problem. We consider systems modeled by nondeterministic Moore machines, and properties specified by branching temporal logic (for linear temporal logic, robust satisfaction coincides with usual satisfaction). We show that the complexity of the problem is EXPTIME-complete for CTL and the -calculus, and is 2EXPTIME-complete for CTL*. Thus, from a complexity-theoretic perspective, robust satisfaction behaves like satisfiability, rather than like model checking.

Many embedded systems behave very differently from classical machine models: they interact with an unpredictable environment, they are “always on”, and they change over time. This leads to the interesting question of what a computational theory of interactive, evolving programs should look like. While the behavior of such programs has been well-studied in concurrency theory, there has been much less emphasis on their computational aspects. A theory of interactive computation must necessarily lead beyond the classical, finitary models of computation.

We describe a simple model of interactive computing consisting of one component and an environment , interacting using single streams of input and output signals and with a number of realistic conditions in effect. The model enables us to study the computational implications of interaction, building on the theory of -automata. Viewing components as interactive transducers, we show that the interactive capabilities of components for recognition and generation are equivalent. We also show that all interactively computable functions are limit-continuous and that interactively computable bijections have interactively computable inverses. The model elegantly characterizes interactive computation in a stream setting.

We describe an interaction based approach for computer modeling and simulation of large integrated biological, information, social and technical (BIST) systems. Examples of such systems are urban regional transportation systems, the national electrical power markets and grids, gene regulatory networks, the World-Wide Internet, infectious diseases, vaccine design and deployment, theater war, etc. These systems are composed of large numbers of interacting human, physical, informational and technological components. These components adapt and learn, exhibit perception, interpretation, reasoning, deception, cooperation and non-cooperation, and have economic motives as well as the usual physical properties of interaction.

The theoretical foundation of our approach consists of two parts: (i) mathematics of complex interdependent dynamic networks, and (ii) mathematical and computational theory of a class of finite discrete dynamical systems called (SDSs). We then consider engineering principles based on such a theory. As with the theoretical foundation, they consist of two basic parts: (i) Efficient data manipulation, including synthesis, integration, storage and regeneration and (ii) high performance computing oriented system design, development and implementation. The engineering methods allow us to specify, design, and analyze simulations of extremely large systems and implement them on massively parallel architectures. As an illustration of our approach, an interaction based computer modeling and simulation framework to study very large interdependent societal infrastructures is described.

A sequential algorithm just follows its instructions and thus cannot make a nondeterministic choice all by itself, but it can be instructed to solicit outside help to make a choice. Similarly, an object-oriented program cannot create a new object all by itself; a create-a-new-object command solicits outside help. These are but two examples of intrastep interaction of an algorithm with its environment. Here we motivate and survey recent work on interactive algorithms within the Behavioral Computation Theory project.

Generalizing the traditional concepts of predicates and their truth to interactive computational problems and their effective solvability, computability logic conservatively extends classical logic to a formal theory that provides a systematic answer to the question of what and how can be computed, just as traditional logic is a systematic tool for telling what is true. The present chapter contains a comprehensive yet relatively compact overview of this very recently introduced framework and research program. It is written in a semitutorial style with general computer science, logic and mathematics audiences in mind.

We describe an interaction based approach for computer modeling and simulation of large integrated biological, information, social and technical (BIST) systems. Examples of such systems are urban regional transportation systems, the national electrical power markets and grids, gene regulatory networks, the World-Wide Internet, infectious diseases, vaccine design and deployment, theater war, etc. These systems are composed of large numbers of interacting human, physical, informational and technological components. These components adapt and learn, exhibit perception, interpretation, reasoning, deception, cooperation and non-cooperation, and have economic motives as well as the usual physical properties of interaction.

The theoretical foundation of our approach consists of two parts: (i) mathematics of complex interdependent dynamic networks, and (ii) mathematical and computational theory of a class of finite discrete dynamical systems called (SDSs). We then consider engineering principles based on such a theory. As with the theoretical foundation, they consist of two basic parts: (i) Efficient data manipulation, including synthesis, integration, storage and regeneration and (ii) high performance computing oriented system design, development and implementation. The engineering methods allow us to specify, design, and analyze simulations of extremely large systems and implement them on massively parallel architectures. As an illustration of our approach, an interaction based computer modeling and simulation framework to study very large interdependent societal infrastructures is described.