Skip to main content
  • Textbook
  • © 1996

Elementare Berechenbarkeitstheorie

Authors:

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

Buy it now

Buying options

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

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

Table of contents (13 chapters)

  1. Front Matter

    Pages I-X
  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. Das Halteproblem und der Satz von Rice

    • Einar Smith
    Pages 67-76
  8. Rekursive Funktionen

    • Einar Smith
    Pages 77-95
  9. Turing-Maschinen

    • Einar Smith
    Pages 97-111
  10. Das Postsche Korrespondenzproblem

    • Einar Smith
    Pages 131-139
  11. Unentscheidbarkeit der Prädikatenlogik

    • Einar Smith
    Pages 141-147
  12. Back Matter

    Pages 161-166

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

Buy it now

Buying options

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