Skip to main content
SpringerLink
Log in

Computability and Decidability

An Introduction for Students of Computer Science

  • Textbook
  • © 1972

Overview

Authors:
  1. Jacques Loeckx

    1. Institut für Informatik, Universität des Saarlandes, 66 Saarbrücken, Germany

    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: Lecture Notes in Economics and Mathematical Systems (LNE, volume 68)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (6 chapters)

  1. Front Matter

    Pages I-VI
    Download chapter PDF

  2. Sets and Functions

    • Jacques Loeckx
    Pages 1-10

  3. Sets and Functions of Strings

    • Jacques Loeckx
    Pages 11-22

  4. Computable Functions

    • Jacques Loeckx
    Pages 23-44

  5. The Universal Turing Machine

    • Jacques Loeckx
    Pages 45-49

  6. Some Functions which are not Computable

    • Jacques Loeckx
    Pages 50-57

  7. Effectively Enumerable and Decidable Sets

    • Jacques Loeckx
    Pages 58-70

  8. Back Matter

    Pages 71-77
    Download chapter PDF
Back to top

Keywords

About this book

The present Lecture Notes evolved from a course given at the Technische Hogeschool Eindhoven and later at the Technische Hogeschool Twente. They are intended for computer science students; more specifically, their goal is to introduce the notions of computability and decidability, and to prepare for the study of automata theory, formal language theory and the theory of computing. Except for a general mathematical background no preliminary knowledge is presupposed, but some experience in programming may be helpful. While classical treatises on computability and decidability are oriented towards the foundation of mathematics or mathematical logic, the present notes try to relate the subject to computer science. Therefore, the expose is based on the use of strings rather than on that of natural numbers; the notations are similar to those in use in automata theory; in addition, according to a common usage in formal language theory, most of the proofs of computability are reduced to the semi-formal description of a procedure the constructivity of which is apparent to anybody having some programming experience. Notwithstanding these facts the subject is treated with mathematical rigor; a great number of informal comments are inserted in order to allow a good intuitive understanding. I am indebted to all those who drew my attention to some errors and ambiguities in a preliminary version of these Notes. I want also to thank Miss L.A. Krukerink for her diligence in typing the manuscript.

Authors and Affiliations

  • Institut für Informatik, Universität des Saarlandes, 66 Saarbrücken, Germany

    Jacques Loeckx

Bibliographic Information

  • Book Title: Computability and Decidability

  • Book Subtitle: An Introduction for Students of Computer Science

  • Authors: Jacques Loeckx

  • Series Title: Lecture Notes in Economics and Mathematical Systems

  • DOI: https://doi.org/10.1007/978-3-642-80689-6

  • Publisher: Springer Berlin, Heidelberg

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer-Verlag Berlin · Heidelberg 1972

  • Softcover ISBN: 978-3-540-05869-4Published: 26 June 1972

  • eBook ISBN: 978-3-642-80689-6Published: 06 December 2012

  • Series ISSN: 0075-8442

  • Series E-ISSN: 2196-9957

  • Edition Number: 1

  • Number of Pages: VI, 78

  • Topics: Math Applications in Computer Science

Publish with us

Policies and ethics

Back to top

Search

Navigation