Berechenbarkeitstheorie

Zum Forum
Passwort vergessen? Noch keinen Account?

lexikon

Hauptseite

Zufälliger Artikel

Diskussion

Diskussion : Berechenbarkeitstheorie

Links

Forum

Portale

Reisen

Versicherung

Inhaltsverzeichnis

Hauptmenü

Home

Bildung

Wissen

--------------------------

Reisen

Lexikon

Versicherung

Suchen

News

Treffpunkt

Chat

Forum

Suche

Schnellsuche

Sitemap

Kontakt

Impressum

Berechenbarkeitstheorie

Stichpunkte

Allgemein
	Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik
	insbesondere welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen Modelles einer Maschine) lÃ¶sbar sind
	der sich mit dem Begriff der Berechenbarkeit befasst
	richtet aber die Aufmerksamkeit mehr auf die Terminiertheit von Programmen und Algorithmen
	Sie ist eng verwandt mit der formalen Semantik
	und nicht die abstrakteren Spezifikationssprachen. Inhaltsverzeichnis showTocToggle("Anzeigen"
	Auch verwendet sie als Ausgangspunkt die verschiedenen Modelle von Maschinen
	"Verbergen") 1 Hauptfragen 2 Welche Art Aufgaben kann eine Turingmaschine lÃ¶sen? 3 Andere Modelle fÃ¼r Berechenbarkeit mit gleicher LeistungsfÃ¤higkeit 4 Welche Aufgaben kÃ¶nnen durch weniger leistungsfÃ¤hige Maschinen gelÃ¶st werden? 5 Zusammenhang mit der Physik 5.1 Literatur 6 Andere Namen [Bearbeiten]
Hauptfragen
	Wie kann man den Begriff der Berechenbarkeit formalisieren? Welche Art Aufgaben kann welche Klasse von Maschinen lÃ¶sen? Insbesondere werden deterministische und nichtdeterministische Varianten folgender Modelle untersucht: endlicher Automat Kellerautomat Linear beschrÃ¤nkte Turingmaschine (LBA) Turingmaschine Registermaschine Welche Art Probleme wÃ¼rden leistungsfÃ¤higere Maschinen benÃ¶tigen? [Bearbeiten]
Welche Art Aufgaben kann eine Turingmaschine lÃ¶sen?
	Nicht alle Aufgaben kÃ¶nnen gelÃ¶st werden
	Ein unentscheidbares Problem ist eines
	das nicht durch einen Algorithmus gelÃ¶st werden kann
	auch wenn unbeschrÃ¤nkt Zeit und Geld zur VerfÃ¼gung steht
	Man kennt viele unentscheidbare Aufgaben
	ZB
	. kann das spezielle Entscheidungsproblem nicht gelÃ¶st werden: Gegeben ist eine Aussage der PrÃ¤dikatenlogik erster OrdnungA
	ufgabe ist es zu entscheiden
	ob die Aussage allgemein gÃ¼ltig istC
	hurch und Turing haben unabhÃ¤ngig nachgewiesen
	dass diese Aufgabe nicht gelÃ¶st werden kannE
	in weiteres Problem ist das Halteproblem
	siehe dort. [Bearbeiten]
Andere Modelle fÃ¼r Berechenbarkeit mit gleicher LeistungsfÃ¤higkeit
	Turingmaschine mit mehreren BÃ¤ndern Turingmaschinen mit einem zweidimensionalen "Band" Registermaschinen Erweitereter Kellerautomat mit zwei Kellerspeichern Endlicher Automat mit zwei ZÃ¤hlern Typ-0-Grammatiken Lambda-KalkÃ¼l rekursive Funktionen Erweiterte Petri-Netze mit Sperrkanten Markow-Algorithmen die meisten modernen Programmiersprachen [Bearbeiten]
Welche Aufgaben kÃ¶nnen durch weniger leistungsfÃ¤hige Maschinen gelÃ¶st werden?
	dann kÃ¶nnen kontext-abhÃ¤ngige Sprachen erkannt werden. Wenn der Speicher nur einen Stapel umfasst
	dann entspricht die Situation der Turingmaschine. Wenn der Speicher proportional zur GrÃ¶ÃŸe der Eingabezeichenkette ist
	dann kÃ¶nnen nur Sprachen
	erkannt werden. [Bearbeiten]
	Die Chomsky-Hierarchie beschreibt diejenigen formalen Sprachen die durch vier Klassen von Algorithmen erkannt werden kÃ¶nnen. Sie alle setzten einen nichtdeterministischen endlichen Automaten voraus mit einem Speicher. Wenn der Speicher unendlich groÃŸ ist
	die durch regulÃ¤re AusdrÃ¼cke definiert sind
	dann kÃ¶nnen kontextfreie Sprachen erkannt werden. Wenn die Maschine nur einen endlichen Speicher hat
Zusammenhang mit der Physik
	Dem Physiker Richard Feynman fiel auf
	Problemstellungen aus der Quantenmechanik zu berechnen
	dass Computer ziemlich schlecht sind
	als wir dies mit einem Computer kÃ¶nnen
	Ein wichtiger Vortrag von ihm hierzu aus dem Jahre 1981 hatte den Titel Can (quantum) physics be (efficiently) simulated by (classical) computers? Offenbar kann die Natur den Ausgang eines quantenmechanischen Experimentes schneller ausrechnen
	einen Quantenprozessor
	einen besonderen Computer zu bauen
	Daher schlug er vor
	um Ergebnisse fÃ¼r quantenmechanische Probleme effizienter zu berechnen
	Dessen Rechenwerk sollte quantenmechanische Prozesse nutzen
	dass die einfachen mathematischen Modelle der theoretischen Informatik eigentlich nur mit einer Teilklasse der realen Computer korrespondieren kÃ¶nnen
	weil man nicht alle physikalischen MÃ¶glichkeiten ausgeschÃ¶pft hatte
	Dabei wurde dann irgendwann klar
	Diese neue Klasse von Computern wird als Quantencomputer bezeichnet. [Bearbeiten]
Literatur
	Tony Hey: Richard Feynman and Computation
	Volume 40
	Contemporary Physics
	p
	1999
	number 4
	257-265
	ISSN 0010-7514 [Bearbeiten]
Andere Namen
	wie Berechenbarkeitstheorie
	Der frÃ¼her verwendete Begriff Rekursionstheorie meint heute das gleiche
	da die rekursiven Funktionen gerade die berechenbaren Funktionen sind
	um nur die Funktionen mit explizitem Selbstbezug zu kennzeichnen. cs:Teorie vyÄ?Ãslitelnosti en:Computability theory es:TeorÃa de la computabilidad fr:ThÃ©orie de la calculabilitÃ© ja:è¨ˆç®—å?¯èƒ½æ€§ç?†è«–
	Einige Autoren verwenden den Begriff Rekursion

Dieser Artikel basiert auf dem Artikel Berechenbarkeitstheorie aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.

Berechenbarkeit BÃ¤rlappe Bettina BrachsenkrautgewÃ¤chse

[ Zurück ]

Inhalt Lexikon:

Allgemein

Hauptfragen

Welche Art Aufgaben kann eine Turingmaschine lÃ¶sen?

Andere Modelle fÃ¼r Berechenbarkeit mit gleicher LeistungsfÃ¤higkeit

Welche Aufgaben kÃ¶nnen durch weniger leistungsfÃ¤hige Maschinen gelÃ¶st werden?

Zusammenhang mit der Physik

Literatur

Andere Namen