Berechenbarkeit

Zum Forum
Passwort vergessen? Noch keinen Account?

lexikon

Hauptseite

Zufälliger Artikel

Diskussion

Diskussion : Berechenbarkeit

Links

Forum

Portale

Reisen

Versicherung

Inhaltsverzeichnis

Hauptmenü

Home

Bildung

Wissen

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

Reisen

Lexikon

Versicherung

Suchen

News

Treffpunkt

Chat

Forum

Suche

Schnellsuche

Sitemap

Kontakt

Impressum

Berechenbarkeit

Stichpunkte

Allgemein
	n_k right)<math> berechnet
	...
	n_k right) in mathbb{N}^k<math> nach endlicher Zahl von Schritten <math>f left( n_1
	n_k right)<math> definiert ist und andernfalls nicht terminiert
	wenn es einen Algorithmus gibt
	sofern <math>f left( n_1
	Eine Funktion <math>f : mathbb{N}^k rightarrow mathbb{N}<math> heiÃŸt berechenbar
	...
	...
	der bei Eingabe von <math>left( n_1
	Der Begriff Algorithmus muss dabei exakt definiert sein
	Von ihm hÃ¤ngt ab
	welche Funktionen berechenbar sind und welche nicht
	UnabhÃ¤ngig davon ist zu beachten
	dass nicht jede mathematische Funktion berechenbar ist
	Dies folgt aus dem GÃ¶delschen UnvollstÃ¤ndigkeitssatz beziehungsweise der UnlÃ¶sbarkeit des Halteproblems von Alan Turing
	Es gibt eine ganze Reihe von Definitionen des Algorithmusbegriffs
	die gleichmÃ¤chtig sind und fÃ¼r die bisher noch keine sinnvolle Erweiterung im Sinne des Berechbarkeitsbegriffs gefunden werden konnte
	Beispiele dafÃ¼r sind While-Programme oder Turingmaschinen
	Die Churchsche These besagt
	dass die Menge der mittels While-Programmen oder Turingmaschinen berechenbaren Funktionen gerade die Menge aller jemals mit einem beliebigen Algorithmus berechenbaren Funktionen ist
	Es ist zu beachten
	dass es auch schwÃ¤chere Algorithmus-Definitionen als While-Programme oder Turingmaschinen gibt
	Dazu gehÃ¶ren zum Beispiel die Loop-Programme
	"Verbergen") 1 Genauere mathematische Definition 1.1 Zahlenfunktionen 1.1.1 Definition berechenbarer Funktionen mit Registermaschinen 1.1.2 Definition mit WHILE Programmen 1.1.3 Definition durch Rekursion 1.1.4 Ãœbergang von einstelligen zu mehrstelligen Funktionen 1.2 Wortfunktionen 2 Spezielle Probleme 3 Siehe auch [Bearbeiten]
	Diese kÃ¶nnen beispielsweise die Ackermann-Funktion nicht berechnen. Inhaltsverzeichnis showTocToggle("Anzeigen"
Genauere mathematische Definition
	[Bearbeiten]
Zahlenfunktionen
	[Bearbeiten]
Definition berechenbarer Funktionen mit Registermaschinen
	also <math>f = f_M<math> gilt
	Eine Funktion <math>f : mathbb{N}^k rightarrow mathbb{N}<math> ist berechenbar genau dann
	deren Maschinenfunktion mit <math>f<math> Ã¼bereinstimmt
	wenn es eine k-stellige Registermaschine <math>M<math> gibt
	Z.B. ist die Funktion <math>f(x) = mbox{div}<math> (die fÃ¼r kein Argument terminiert) berechenbar
	da es eine entsprechende Registermaschine gibt. [Bearbeiten]
Definition mit WHILE Programmen
	AC die Ausgabecodierung und <math>tau(P)<math> die von P Ã¼ber die Semantik realisierte Maschinenfunktion. [Bearbeiten]
	mit <math> f = AC circ tau(P) circ EC<math>. Dabei ist EC die Eingabecodierung
	Eine Funktion f (wie oben) ist berechenbar genau dann
	wenn es ein WHILE-Programm P gibt
Definition durch Rekursion
	der Substitution und primitiven Rekursion
	Sub und Prk die Operationen der <math>mu<math>-Rekursion
	Seien <math>mu<math>
	Funktionen
	die sich aus der Menge der primitiv-rekursiven Grundfunktionen durch wiederholtes Anwenden dieser Operatoren erzeugen lassen
	heiÃŸen Âµ-rekursiv
	Die Menge der <math>mu<math>-rekursiven Funktionen ist genau die Menge der berechenbaren Funktionen. [Bearbeiten]
Ãœbergang von einstelligen zu mehrstelligen Funktionen
	Ãœber die cantorsche Paarungsfunktion fÃ¼hrt man die Berechenbarkeit von einstelligen Mengen weiter auf k-stellige Mengen
	Insbesondere kann man damit die Berechenbarkeit fÃ¼r Funktionen Ã¼ber rationale Zahlen zeigen. [Bearbeiten]
Wortfunktionen
	Die Berechenbarkeit von Wortfunktionen lÃ¤sst sich entweder mit Hilfe von Turingmaschinen oder Bandmaschinen zeigen
	Alternativ fÃ¼hrt man eine Standardnummerierung Ã¼ber die WÃ¶rter Ã¼ber <math>Sigma^*<math> ein und zeigt
	dass die so erzeugten Zahlenfunktionen berechenbar sind
	die eine schnell konvergierende Approximation von reellen Zahlen darstellen. Ãœber solche WÃ¶rter lÃ¤sst sich der Berechenbarkeitsbegriff auf die Menge der reellen Zahlen ergÃ¤nzen. [Bearbeiten]
	Zudem lassen sich geeignete WÃ¶rter definieren
Spezielle Probleme
	also ein Problem mit nur einer Instanz
	immer berechenbar ist
	Eine KuriositÃ¤t ist
	dass ein spezielles
	der diese Funktion berechnet
	Man kÃ¶nnte auch sagen
	dass es fÃ¼r jede Funktion die keine Parameter hat
	einen Algorithmus gibt
	Das klingt verwirrend
	ist aber trivial
	Angenommen
	und die Definition von "Gott" sei in irgendeiner Form vorgegeben
	die Frage lautet "gibt es Gott"
	Diese Frage reprÃ¤sentieren wir durch die (parameterlose) Funktion <math>g()<math>
	der die korrekte Antwort ausgibt
	Die Antwort muss nun entweder ja oder nein lauten â€“ und fÃ¼r beide Antworten lÃ¤sst sich leicht ein Algorithmus konstruieren
	wir wissen nur nicht
	welcher es ist
	Es gibt also immer einen solchen Algorithmus
	WÃ¼rden wir das gleiche Problem allgemein stellen
	so dass die Definition von Gott (nennen wir sie <math>d<math>) als Eingabe des Algorithmus verlangt ist (also ein Parameter der Funktion <math>g<math> wÃ¤re)
	so wÃ¤re die resultierende Aussage <math>g(d)<math> nicht berechenbar
	Das gleiche gilt natÃ¼rlich auch fÃ¼r Fragestellungen aus weniger esoterischen Bereichen. [Bearbeiten]
Siehe auch
	These von Church Berechenbarkeitstheorie Halteproblem Entscheidungsproblem GÃ¶delscher UnvollstÃ¤ndigkeitssatz en:computability

Dieser Artikel basiert auf dem Artikel Berechenbarkeit 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.

BÃ¤rlappe Bettina BrachsenkrautgewÃ¤chse

[ Zurück ]

Inhalt Lexikon:

Allgemein

Genauere mathematische Definition

Zahlenfunktionen

Definition berechenbarer Funktionen mit Registermaschinen

Definition mit WHILE Programmen

Definition durch Rekursion

Ãœbergang von einstelligen zu mehrstelligen Funktionen

Wortfunktionen

Spezielle Probleme

Siehe auch