Diskussion:WHILE-Programm

Letzter Kommentar: vor 4 Jahren von Petarded in Abschnitt Kleenesche Normalform

korrektur beispiel

Bearbeiten

ist der letzte abschnitt nicht falsch?


Ein jedes WHILE-Programm

WHILE xi != 0 DO P END

kann durch das folgende GOTO-Programm simuliert werden

M1: IF x1 = 0 THEN GOTO M2;
    P;
    x1:= x1-1;
    GOTO M1;
M2: ...


sollte aus dem gotoprogramm nicht das x:= x1-1; gelöscht werden?


Denke ich auch, habe es gelöscht. --GrGr 09:25, 26. Apr 2006 (CEST)

Iteration

Bearbeiten

Ist eine While-Schleife eigentlich eine Iteration? Bis jetzt hatte ich eine Lösung mit while-Schleifen immer als iterative Problemlösung angesehen. In dem Artikel über Rekursion wird allerdings erwähnt, das die primitive Rekursion immer durch eine Iteration ersetzt werden kann. Allerdings kann ein While-Programm ja jede Rekursive Funktion berechnen (da Turing vollständig) und somit macht die Einschränkung auf primitiv rekursive Funktionen keinen Sinn. Oder gilt im Sinne der Informatik Iteration nur für eine feste Anzahl Durchläufe (Wie bei LOOP-Programmen?) In dem Artikel Iteration konnte ich in der Hinsicht nichts finden. --217.232.26.170 19:56, 2. Aug. 2009 (CEST)Beantworten

Ähm, jede WHILE-Funktion ist Touring-berechenbar , das ist nicht dasselbe wie Touring-vollständig .
--arilou (Diskussion) 10:22, 18. Jun. 2015 (CEST)Beantworten
Humbug - die Klasse der WHILE-Programme ist sehr wohl Turing-vollständig (wie kommt man eigentlich auf die Idee, hier zu klugsch... wenn man nicht mal weiß, wie Turing geschrieben wird?) Zur Frage: Primitive Rekursion ist äquivalent zu beschränkter Iteration (wie bei LOOP-Programmen). WHILE-Programme können aber auch unbeschränkte Iteration, was äquivalent zu μ-Rekursion ist. Das ist (nach Satz von Ackermann) in der Tat stärker als primitive Rekursion. --AlgorithMan (Diskussion) 15:13, 19. Aug. 2015 (CEST)Beantworten
a) Bitte WP:KPA beachten, auch wenn ich mal ein 'o' zuviel verwendet habe.
b) Aus der Frage war nicht (offen) ersichtlich, dass es sich speziell um das Fachgebiet 'Theoretische Informatik' handelt. Bei den Praktikern kann "ein WHILE-Programm" auch einfach "ein Programm, das eine WHILE-Schleife enthält" bedeuten - insbesondere wenn der Sprachgebrauch des Fragenden eher auf einen -hm- Noch-Lernenden hindeuten.
--arilou (Diskussion) 13:10, 7. Sep. 2015 (CEST)Beantworten

Kleenesche Normalform

Bearbeiten

Im Artikel wird die formale Syntax der While-Programme ohne If und Loop angegeben. Gleichzeitig merkt der Artikel an, dass alle While-Programme in ein While-Programm mit nur einer While-Schleife umgesetzt werden können.

Allerdings werden für die Kleenesche-Normalform neben einer While-Schleife auch (in aller Regel) mehrere Loops (oder Fallunterscheidungen) benötigt.

In dem angegeben Formalismus wären zu derer Simulation allerdings While-Ausdrücke notwendig, sodass hier weiterhin mehrere While-Schleifen benötigt werden.

Sollte man nicht im Artikel darauf hinweisen oder den Formalismus um Loop erweitern? RandomPerson (Diskussion) 21:54, 13. Aug. 2015 (CEST)Beantworten

Das wollte ich ebenfalls bemängeln. --AlgorithMan (Diskussion) 15:15, 19. Aug. 2015 (CEST)Beantworten

Sorry, hatte gestern übersehen, dass in der WHILE-Program definition loops drinnen waren, weiß auch nicht wie das passieren konnte, oops, habs schon korrigiert. Bitte um Nachsicht! --Petarded (Diskussion) 10:10, 24. Mai 2020 (CEST)Beantworten