| Autor |
Beitrag |
    
Subzero (Subzero)
Moderator
Benutzername: Subzero
Nummer des Beitrags: 22
Registriert: 02-2001
| | Veröffentlicht am Mittwoch, den 22. September, 2004 - 09:47: | 
|
Hi Ihr,
kürzlich bin ich während meine Diplomarbeit auf ein Problem gestoßen:
Es gibt eine (unendliche) Menge an berechenbaren Funktionen, die sich mit folgenden Methoden ausdrücken lassen:
1. rekursive Funktionen
2. while-Schleifen
3. Horn-Klauseln
4. Turing-Maschine
Die Frage ist, ob die Mengengeleichheit dieser vier Methoden schon bewiesen wurde oder ob der Beweis noch aussteht. Vielleicht weiß jemand von euch die Antwort. In einem Buch hab ich gelesen, dass dieses Frage noch nicht bewiesen wurde, aber das Buch war schon über 20 Jahre alt...
Grüße
Subzero
|
Mainziman (Mainziman)
Senior Mitglied
Benutzername: Mainziman
Nummer des Beitrags: 931
Registriert: 05-2002
| | Veröffentlicht am Mittwoch, den 22. September, 2004 - 11:02: |
|
Hm,
die Frage ist was da unter berechenbar verstanden wird;
z.b. f_<n+2> = sqrt( f_<n> ) + ( f_<n+1> - f_<n> )^2 * f_<n-1> mit f_0 = f_1 = 2, f_2 = 3 und n aus IN
wirst Du kaum als explizite Formel hinbekommen,
aber berechnen kannst Du die Folge sehr wohl;
Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*
|
Subzero (Subzero)
Moderator
Benutzername: Subzero
Nummer des Beitrags: 23
Registriert: 02-2001
| | Veröffentlicht am Mittwoch, den 22. September, 2004 - 16:16: |
|
Hi,
wie fast immer habe ich wiedermal vergeseen den Kontext zu beschreiben. Es geht im Grunde genommen um die Klasse der berechenbaren Funktionen. Also, salop ausgedrückt um alle Funktionen(Programme) die ein Computer berechnen kann. Dabei stellt sich die Frage ob jeder Algorithmus, der in bspw. C++ geschrieben werden kann auch in Prolog geschrieben werden kann ? (while-Schleife vs. Horn-Klauseln)
Du hast natürlich Recht, dass nicht jede rekursive Funktion auch explizit ausgedrückt werden kann. Wie ja auch die bekannte Ackermannfunktion...
Ich hab aber nun doch noch ein Skript gefunden was mich der Lösung ein Stück näher bringt. Der Schlüssl ist die Churchsche These, die besagt, dass die Turing-Berechenbarkeit einer Klasse von Funktionen mit der Klasse der im intuitiven Sinne berechenbaren Funktionen übereinstimmt. Dies ist nicht beweisbar, aber gilt als allgemein anerkannt.
Danke trotzdem,
Subzero
|
Mainziman (Mainziman)
Senior Mitglied
Benutzername: Mainziman
Nummer des Beitrags: 932
Registriert: 05-2002
| | Veröffentlicht am Mittwoch, den 22. September, 2004 - 18:04: |
|
"Dabei stellt sich die Frage ob jeder Algorithmus, der in bspw. C++ geschrieben werden kann auch in Prolog geschrieben werden kann?"
Da Prolog eine compilierte Sprache ist (es gibt Compiler für Prolog, Turbo Prolog sei als Beispiel genannt), ergibt die Umsetzung ebenso Maschinencode, wie der die Umsetzung mit C/C++ compilern; die Frage die sich dann stellt; ist es möglich an Hand der Maschinensprache einen Prolog Quellcode zu "fischen"?
Wenn ja, dann ist Deine Frage mit ja zu beantworten, wenn nein, dann ist Deine Frage mit nein zu beantworten;
Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*
|
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 239
Registriert: 10-2001
| | Veröffentlicht am Donnerstag, den 23. September, 2004 - 10:25: |
|
@all:
Es geht hier IMHO um einen Bereich der Theroretischen Informatik (siehe Berechenbarkeit).
Hierbei geht es kaum um "reale" Programmiersprachen - auch wenn manche Arten der Berechenbarkeit nur in einigen Programmiersprachen dargestellt werden können.
Aber dazu wurden diese ja konstruiert.
@Subzero:
Es gilt:
"Jede WHILE-berechenbare Funktion ist GOTO-berechenbar und umgekehrt sowie Turing-berechenbar."
Die Menge der Rekursiven Funktionen teilt sich in die m-rekursiven und die anderen :-)
Es gilt:
"Jede m-rekursive Funktion entspricht einer WHILE-Schleife und umgekehrt."
Ich weis aber weder wie mächtig die Menge der μ-rekursiven Funktionen ist noch ob die Horn-Klausel Turingberechnbar ist.
Vielleicht hilft Dir das weiter,
Onkel Murray
(Beitrag nachträglich am 23., September. 2004 von murray editiert) |
|
