Rekursion und Iteration < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 20:45 Di 08.01.2008 | | Autor: | BJJ |
Hallo,
es gibt angeblich ein Theorem das besagt "jede Rekursion ist als Iteration darstellbar und umgekehrt". Wo kann ich denn einen Beweis zu dieser Aussage finden?
Vielen Dank und beste Gruesse
bjj
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:15 Mi 09.01.2008 | | Autor: | Gilga |
Beweisidee: Church-Turing These. Die sagt man kann jede berechenbare Rekursion z.B. wegen Turing-vollständigkeit von while Programmen durch dieses lösen.
Antwort: Für jede Rekursion gibt es ein while-Programm, dass das gleich kann.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:03 Do 10.01.2008 | | Autor: | BJJ |
hallo,
vielen dank fuer deine antwort
soviel ich weiss ist die these von church nicht beweisbar. deswegen heisst es ja auch these und nicht theorem.
auf der anderen seite suche ich den beweis. gibt es dazu eine literaturangabe/webseite, die du oder jemand anders mir empfehlen kann?
danke und beste gruesse
bjj
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:08 Sa 12.01.2008 | | Autor: | Infinit |
Wenn es sich hierbei um eine Hypothese handelt, und es hat ja den Anschein, dass dem so ist, so kann es dafür keinen Beweis geben.
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Sa 12.01.2008 | | Autor: | Gilga |
Ich muss doch mal was richtigstellen.
Als ich meinen Vorschlag gemacht habe dachte ich an rekursiv berechenbare Funktionen. Dieses wären nach Definition als ein while Programm darstellbar. Dies ist unberührt von der Church These.
Vermutlich willst du aber eine lösung für rekursionen im allgemeinen.
Such dir erst mal eine formale def von rekursion.
z.b. wäre ein einfacher Fall ~~~ f(n)=f(g(n)) wobei g angibt wie in f aus der eingabe n mittels g eine neue eingabe für sich selbst erzeugt wird. Das macht man bis man eine abbrucheigenschaft getroffen hat (steht auch in g )
while(n!=Wert zum Abbruch){
n=g(n)
}
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 12:16 Mo 14.01.2008 | | Autor: | BJJ |
Hallo,
danke fuer die Antworten. Tut mir leid, der skizzierte Beweis erschliesst sich mir leider nicht. Mir wuerde eine Literaturangabe sehr weiterhelfen.
Danke und beste Gruesse
BJ
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Mi 16.01.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
