Skip to main content
SpringerLink
Log in

Elementare Berechenbarkeitstheorie

  • Textbook
  • © 1996

Overview

Authors:
  1. Einar Smith

    1. Institut für Algorithmen und Wissenschaftliches Rechnen, GMD — Forschungszentrum Informationstechnik GmbH, Sankt Augustin, Deutschland

    View author publications

    You can also search for this author in PubMed   Google Scholar

Part of the book series: Springer-Lehrbuch (SLB)

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 19.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 24.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 (13 chapters)

  1. Front Matter

    Pages I-X
    Download chapter PDF

  2. Einleitung

    • Einar Smith
    Pages 1-7

  3. Registermaschinen

    • Einar Smith
    Pages 9-16

  4. Berechenbare Funktionen

    • Einar Smith
    Pages 17-30

  5. Zeichenketten und Gödelnummern

    • Einar Smith
    Pages 31-37

  6. Universelle Programme

    • Einar Smith
    Pages 39-51

  7. Beschränkte und unbeschränkte Schleifen

    • Einar Smith
    Pages 53-66

  8. Das Halteproblem und der Satz von Rice

    • Einar Smith
    Pages 67-76

  9. Rekursive Funktionen

    • Einar Smith
    Pages 77-95

  10. Turing-Maschinen

    • Einar Smith
    Pages 97-111

  11. Berechenbarkeit, Entscheidbarkeit, Aufzählbarkeit

    • Einar Smith
    Pages 113-129

  12. Das Postsche Korrespondenzproblem

    • Einar Smith
    Pages 131-139

  13. Unentscheidbarkeit der Prädikatenlogik

    • Einar Smith
    Pages 141-147

  14. Unentscheidbare Probleme in den formalen Sprachen

    • Einar Smith
    Pages 149-159

  15. Back Matter

    Pages 161-166
    Download chapter PDF
Back to top

Keywords

About this book

Das Buch führt in leicht verständlicher und dennoch präziser Form in die Grundlagen der Berechenbarkeitstheorie ein. Es richtet sich an Informatikstudenten, ist aber für alle an der algorithmischen Berechenbarkeit Interessierten geeignet; vom Leser wird nur eine gewisse Vertrautheit mit formaler Argumentation erwartet. Der Darstellung liegt das Modell der Registermaschine zugrunde, das dem Umgang mit realen Computern und Programmiersprachen entlehnt ist. Daneben werden auch die klassischen Berechenbarkeitsmodelle betrachtet und die Gleichwertigkeit der Ansätze untereinander gezeigt. Darüber hinaus werden nicht-berechenbare Funktionen und unentscheidbare Probleme nachgewiesen. Als weiterführendes Thema wird die Unentscheidbarkeit der Prädikatenlogik und einiger Probleme aus dem Bereich der formalen Sprachen behandelt.

Authors and Affiliations

  • Institut für Algorithmen und Wissenschaftliches Rechnen, GMD — Forschungszentrum Informationstechnik GmbH, Sankt Augustin, Deutschland

    Einar Smith

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation