Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDienstag, 23. Juli 2019 

Berechenbarkeitstheorie


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik der sich mit dem Begriff der Berechenbarkeit befasst insbesondere welche Probleme mit Hilfe Maschine (genauer: eines mathematischen Modelles einer Maschine) sind.

Inhaltsverzeichnis

Hauptfragen


Welche Art Aufgaben kann eine Turingmaschine lösen?

Nicht alle Aufgaben können gelöst werden. unentscheidbares Problem ist eines das nicht durch Algorithmus gelöst werden kann auch wenn unbeschränkt und Geld zur Verfügung steht. Man kennt unentscheidbare Aufgaben.

Z. B. kann das Entscheidungsproblem nicht gelöst werden: Gegeben ist eine der Prädikatenlogik erster Ordnung. Aufgabe ist es entscheiden ob die Aussage allgemein gültig ist.

Church und Turing haben unabhängig nachgewiesen dass Aufgabe nicht gelöst werden kann.

Ein weiteres Problem ist das Halteproblem siehe dort.

Andere Modelle für Berechenbarkeit mit gleicher Leistungsfähigkeit

Welche Aufgaben können durch weniger leistungsfähige Maschinen werden?

Die Chomsky-Hierarchie beschreibt diejenigen formalen Sprachen die durch Klassen von Algorithmen erkannt werden können. Sie setzten einen nichtdeterministischen endlichen Automaten voraus mit Speicher. Wenn der Speicher unendlich groß ist entspricht die Situation der Turingmaschine. Wenn der proportional zur Größe der Eingabezeichenkette ist dann kontext-abhängige Sprachen erkannt werden. Wenn der Speicher einen Stapel umfasst dann können kontextfreie Sprachen werden. Wenn die Maschine keinen Speicher hat können nur Sprachen die durch reguläre Ausdrücke definiert sind erkannt werden.



Bücher zum Thema Berechenbarkeitstheorie

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Berechenbarkeitstheorie.html">Berechenbarkeitstheorie </a>