Cantitate/Preț
Produs

Computability and Decidability: An Introduction for Students of Computer Science: Lecture Notes in Economics and Mathematical Systems, cartea 68

Autor J. Loeckx
en Limba Engleză Paperback – 26 iun 1972
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.
Citește tot Restrânge

Din seria Lecture Notes in Economics and Mathematical Systems

Preț: 31101 lei

Preț vechi: 38876 lei
-20% Nou

Puncte Express: 467

Preț estimativ în valută:
5952 6279$ 4960£

Carte tipărită la comandă

Livrare economică 02-16 ianuarie 25

Preluare comenzi: 021 569.72.76

Specificații

ISBN-13: 9783540058694
ISBN-10: 3540058699
Pagini: 84
Ilustrații: VI, 78 p.
Dimensiuni: 178 x 254 x 4 mm
Greutate: 0.16 kg
Ediția:Softcover reprint of the original 1st ed. 1972
Editura: Springer Berlin, Heidelberg
Colecția Springer
Seria Lecture Notes in Economics and Mathematical Systems

Locul publicării:Berlin, Heidelberg, Germany

Public țintă

Research

Cuprins

1: Sets and Functions.- 1.1. The objects.- 1.2. Ordered sequences and sets.- 1.3. Further notations and definitions concerning sets.- 1.4. Functions.- 1.5. Particular objects.- 2: Sets and Functions of Strings.- 2.1. Definitions.- 2.2. String functions.- 2.3. Further notations and definitions.- 2.4. The interpretation of strings.- 2.5. Alphabetic order.- 2.6. Enumeration of strings and n-tuples of strings.- 2.7. Enumeration functions.- 2.8. Calculating the value of the enumeration functions.- 3: Computable Functions.- 3.1. Historical background.- 3.2. The basic idea of Turing.- 3.3. Physical model.- 3.4. Formal definition of a Turing machine.- 3.5. Examples of Turing machines.- 3.6. Computable functions.- 3.7. The thesis of Turing.- 3.8. Normal Turing machines.- 4: The Universal Turing Machine.- 4.1. The string description of a Turing machine.- 4.2. The universal Turing machine.- 4.3. Discussion.- 5: Some Functions Which are Not Computable.- 5.1. The halting problem.- 5.2. The blank tape halting problem.- 5.3. The uniform halting problem.- 5.4. The equivalence problem.- 5.5. General remark.- 6: Effectively Enumerable and Decidable Sets.- 6.1. Introduction.- 6.2. Definitions.- 6.3. Effectively enumerable sets and the domain of computable functions.- 6.4. Effectively enumerable sets and the range of total computable functions.- 6.5. A set which is not effectively enumerable.- 6.6. Decidable sets versus effectively enumerable sets.- 6.7. An effectively enumerable set which is not decidable.- 6.8. Some informal comments.- Appendix 1: Bibliographical Notes.- Appendix 2: List of the Most Important Notations.- Appendix 3: List of the Most Important Concepts.