Computable Functions

Erscheinungsjahr 2002
ISBN: 978-0-8218-2732-1
Verlag: American Mathematical Society

Buch, Englisch, Band 19, Format (B × H): 139 mm x 217 mm, Gewicht: 209 g

Reihe: Student Mathematical Library

Based on the lectures for undergraduates at Moscow State University, this book presents a concise introduction to the central facts and basic notions of the general theory of computation.

In 1936, before the development of modern computers, Alan Turing proposed the concept of a machine that would embody the interaction of mind, machine, and logical instruction. The idea of a "universal machine" inspired the notion of programs stored in a c

Computable functions, decidable and enumerable sets; Universal functions and undecidability; Numberings and operations; Properties of Godel numberings; Fixed point theorem; m-reducibility and properties of enumerable sets; Oracle computations; Arithmetical hierarchy; Turing machines; Arithmeticity of computable functions; Recursive functions; Bibliography; Glossary; Index

Fachgebiete

• Mathematik | Informatik Mathematik Mathematik Allgemein Mathematische Logik
• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker

Über Autor(innen)

(Moscow State Lomonosov University, Russia)