Fundamental Concepts in Computer Science

The following sections are included:

• PREFACE

• CONTENTS

The following sections are included:

• Introduction

• Böhm's Theorem for Trees

• Böhm's Theorem for λ-Calculus

• Follow-Up to Böhm's Theorem
  • Böhm's work on Böhm's theorem
  • Generalizations of Böhm's theorem
  • Theories and models of λ-calculus
  • Böhm trees and Böhm-out-technique
  • Observational equivalence

• References

At the moment when these notes are written, membrane computing is only eight years old. Is this an age when a “history” can be recalled? The doubt suggested by the mere formulation of this question is removed by the personal feeling that, actually, the domain has a long history, a feeling grounded on the large number of notions, research directions, results, applications, publications, and events related to membrane computing. The second part of these notes will (try to) prove these assertions, providing the reader with a quick introduction to membrane computing, pointing out mainly basic ideas and types of results and of applications. Before that, the first part of the paper, provides a personal view about these last (more than) eight years, remembering facts which might not have a great significance for somebody not involved in this field or not knowing the persons which will be mentioned below, but significant for me. This is, indeed, a personal history of membrane computing.

Consequently, the reader is asked not to evaluate this text with modest/non-modest measures. I used to say several times (e.g. in interviews for Romanian newspapers) that, while everybody tries to become a name in science, I “failed”, because I just became a letter: the computing devices studied in membrane computing are called P systems. It is not easy to become a letter and then to discuss about it in conferences or in texts like the present one, but, at the same time, your vanity is highly pleased when doing it. This should be the same for everybody, the only difference being that customarily the people do not admit that they are vanitous. Moreover, in general, the scientists are not modest, and mathematicians still less. Pretending to be exact, they promote themselves, without any thought paid to any shame, because no thought is paid to any self-promotion. The same with my recollections here: I will just try to be exact.

In this text, we attempt to shortly highlight certain constitutive principles of the particular form of knowledge provided by the digital machine, the modern computer, in its relationship to mathematics (from which it originates) and to the natural sciences (physics and biology). Our basic thesis is that the historical and conceptual richness of the theory which enabled the concrete realization of this extraordinary type of machine is far from being neutral or transparent with regard to reality. Specifically, we will see that the digital machine proposes causal structures and the breakings of symmetry which are intrinsic to its theory as being the central structures of the intelligibility of nature. This will enable to point out a distinction between “imitation” and “modeling” in terms of simulation or formalization, and therefore enable to highlight the limits and the potentialities of digital simulation.

The theory of computation generally considers functions that map discrete denumerable structures into structures, while most practical computation is numerical in scope and deals with real numbers. Computing with real numbers is still the bread and butter of the key computer applications such as medical diagnostics, large science, engineering design, sensing and signal processing, business, commerce, the stock market, and so on. While Turing machines and models derived from the logical behavior of computation provide universal models of computation for discrete structures, one can also consider the question of how to characterize universal models of numerical computation. By describing the “G-Network” or “random neural network” and examining its ability to approximate functions, this paper provides an example of a “universal model” of computation for continuous and bounded functions, and also shows how discrete continuous time stochastic systems can offer intriguing models of computation.

An assertion is a Boolean formula written in the text of a program, at a place where its evaluation will always be true — or at least, that is the intention of the programmer. In the absence of jumps, it specifies the internal interface between the part of the program that comes before it and the part that comes after. The interface between a procedure declaration and its call is defined by assertions known as pre-conditions and post-conditions. If the assertions are strong enough, they express everything that the programmers on either side of the interface need to know about the program on the other side, even before the code is written. Indeed, such strong assertions can serve as the basis of a formal proof of the correctness of a complete program.

In this paper, I will describe how my early experience in industry triggered my interest in assertions and their role in program proofs; and how my subsequent research at university extended the idea into a methodology for the specification and design of programs. Now that I have returned to work in industry, I have had the opportunity to investigate the current role of assertions in industrial program development. My personal perspective illustrates the complementary roles of pure research, aimed at academic ideals of excellence, and the unexpected ways in which the results of such research contribute to the gradual improvement of engineering practice.

By the end of 2007, more than 10,000,000,000 ARM processors had been manufactured, making the ARM the highest volume processor in the 32-and-above-bit space of all time, by a very large margin. The origins of the ARM can be traced back to a small UK supplier of desk-top machines, Acorn Computer Ltd, in the early 1980s, for whose staff the original ARM(then the “Acorn RISC Machine”) was a first attempt at designing a microprocessor. The ultimate success of the ARM is a result of serendipity (of course) combined with a little good technical judgement, a great deal of creativity in developing a novel business model, and a focus on customer service. The technical development of the ARM has as its foundations some of the important developments in computer science over the last quarter of a century: its architectural conception was a result of skillful selling of the RISC philosophy by its exponents at Berkeley; its silicon design employed very early design automation tools; its simplicity, small size and power-efficiency suited it to the emerging System-on-Chip (SoC) technology of the early 1990s, and its foothold there enabled it to climb into its dominant position in the consumer technology of the digital age — the pervasive mobile multimedia communications appliances of the early 21st century. This chapter will principally cover the early period of ARM history, during the 1980s, before the ARM emerged onto the world stage under the management of the company that bears its name.

The following sections are included:

• Introduction

• The Dissertation

• Carl Adam Petri, The Man

• The Years Until 1980

• The Years Since 1980

• Honors

• What Will the Future Bring?

• References

The following sections are included:

• Stochastic Processes and the Central Server Model

• Early Concerns About Stochastic Modeling

• Impact of Empirical Success

• Lectures at Serre Chevalier and Bologna

• Emergence of Operational Analysis

• References

Applied mathematicians, such as John Von Neumann, have had a great influence on the design of computers and have adapted them to their need such as optimal control of trajectories, game theory and the numerical study of fluid flows. Ordinary differential equations and optimization problems were among the first to be solved after the Fortran language came into being, but computational fluid dynamics took much longer to mature, and still one cannot say that the partial differential equations of fluid mechanics are solvable using today's computers. For this reason such open problems continue to influence computer architectures. Nevertheless it is now possible to design a virtual aircraft prototype entirely and fairly accurately, and the impact of this technology is felt even more on software development for Computer Aided Design systems. This paper is a short history of the interaction between numerical simulations in engineering, and the development of hardware and software over the past thirty years based on the author's personal experience.