nach oben

2009 | Buch

Kapitel lesen Erstes Kapitel lesen

Models of Computation

An Introduction to Computability Theory

verfasst von: Dr Maribel Fernández

Verlag: Springer London

Buchreihe : Undergraduate Topics in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

A Concise Introduction to Computation Models and Computability Theory provides an introduction to the essential concepts in computability, using several models of computation, from the standard Turing Machines and Recursive Functions, to the modern computation models inspired by quantum physics. An in-depth analysis of the basic concepts underlying each model of computation is provided.

Divided into two parts, the first highlights the traditional computation models used in the first studies on computability: - Automata and Turing Machines; - Recursive functions and the Lambda-Calculus; - Logic-based computation models.

and the second part covers object-oriented and interaction-based models. There is also a chapter on concurrency, and a final chapter on emergent computation models inspired by quantum mechanics.

At the end of each chapter there is a discussion on the use of computation models in the design of programming languages.

Inhaltsverzeichnis

Frontmatter

Introduction

Frontmatter

1. Introduction

This book is concerned with abstract models of computation. Several new models of computation have emerged in the last few years (e.g., chemical machines, bio-computing, quantum computing, etc.). Also, many developments in traditional computational models have been proposed with the aim of taking into account the new demands of computer system users and the new capabilities of computation engines. A new model of computation, or a new feature in a traditional one, usually is reflected in a new family of programming languages and new paradigms of software development. Thus, an understanding of the traditional and emergent models of computation facilitates the use of modern programming languages and software development tools, informs the choice of the correct language for a given application, and is essential for the design of new programming languages.

Maribel Fernández

Traditional Models of Computation

Frontmatter

2. Automata and Turing Machines

In the 1930s, logicians (in particular Alan Turing and Alonzo Church) studied the meaning of computation as an abstract mental process and started to design theoretical devices to model it. As mentioned in the introduction, they needed a precise, formal definition of an algorithm in order to show that some of the problems posed by David Hilbert at the 1900 International Congress of Mathematicians could not be solved algorithmically. This was a very important step towards the construction of actual computers and, later, the design of programming languages. Turing machines influenced the development of digital computers, and the Lambda calculus is the basis of functional programming languages. At the same time, computers give to the early computability studies a practical application.

Maribel Fernández

3. The Lambda Calculus

The Lambda calculus, or γ-calculus, is a model of computation based on the idea that algorithms can be seen as mathematical functions mapping inputs to outputs. It was introduced by Alonzo Church in the 1930s as a precise notation for a theory of anonymous functions; its name is due to the use of the Greek letter γ in functional expressions. Church remarked that when denoting a function by an expression such as x + y, it was not always clear what the intended function was.

Maribel Fernández

4. Recursive Functions

In the previous chapters, we discussed the notion of a computable function and characterised this class of functions as the ones that can be defined via Turing machines or the β-calculus. In this chapter, we give an alternative characterisation of computable functions based on the notion of a recursive function. Usually, we say that a function is recursive if it “calls itself”. Recursive functions are functions for which the result for a certain argument depends on the results obtained for other (smaller in some sense) arguments. Recursion is a very useful tool in modern programming languages, in particular when dealing with inductive data structures such as lists, trees, etc.

Maribel Fernández

5. Logic-Based Models of Computation

During the late 1920s, Jacques Herbrand, a young mathematician, developed a method to check the validity of a class of first-order logic formulas. In his thesis, published in 1931, Herbrand discussed what can be considered the first unification procedure. Unification is at the heart of modern implementations of logic programming languages

Maribel Fernández

Modern Models of Computation

Frontmatter

6. Computing with Objects

Turing machines and the β-calculus are two examples of universal (i.e., Turingcomplete) models of computation. We will now describe another universal model, based on the use of objects, with method invocation and update as main operations.

Maribel Fernández

7. Interaction-Based Models of Computation

In this chapter, we study interaction nets, a model of computation that can be seen as a representative of a class of models based on the notion of “computation as interaction”. Interaction nets are a graphical model of computation devised by Yves Lafont in 1990 as a generalisation of the proof structures of linear logic. It can be seen as an abstract formalism, used to define algorithms and analyse their cost, or as a low-level language into which other programming languages can be compiled. This is fruitful because interaction nets can be implemented with reasonable efficiency.

Maribel Fernández

8. Concurrency

In the previous chapters, we described several models of computation that reflect different ways in which the process of computation can be understood. All these different abstract models of computation share one characteristic: The goal is to express sequential algorithms. To describe the meaning of a sequential program, we can use an operational approach in which we see an algorithm as a black box transforming some given input data into the desired output. However, in some contexts, for example when describing the behaviour of an operating system, this input-output abstraction is not well suited. The final result of the algorithm might not be of interest, or the notion of “final” might not even apply. Indeed, an operating system does stop running in some cases, typically when we shut down our computer, but then we are not expecting a “result” from the computation.

Maribel Fernández

9. Emergent Models of Computation

In this chapter, we briefly present two fields that have emerged in recent years: natural computing and quantum computing.

Maribel Fernández

10. Answers to Selected Exercises

Give more examples of total and partial functions on natural numbers.

Answer: There are many examples of total functions. Addition, multiplication, and any combination of these, as well as the well-known factorial function, are all total. Subtraction is partial on natural numbers (but total on integers).

Maribel Fernández

Backmatter

Titel: Models of Computation
verfasst von: Dr Maribel Fernández
Verlag: Springer London
Electronic ISBN: 978-1-84882-434-8
Print ISBN: 978-1-84882-433-1
DOI: https://doi.org/10.1007/978-1-84882-434-8

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Introduction

Frontmatter

1. Introduction

Traditional Models of Computation

Frontmatter

2. Automata and Turing Machines

3. The Lambda Calculus

4. Recursive Functions

5. Logic-Based Models of Computation

Modern Models of Computation

Frontmatter

6. Computing with Objects

7. Interaction-Based Models of Computation

8. Concurrency

9. Emergent Models of Computation

10. Answers to Selected Exercises

Backmatter

Premium Partner