WHILE-Programm - Versionsgeschichte

217.61.192.163: ,

2023-07-23T09:38:30Z

← Nächstältere Version		Version vom 23. Juli 2023, 11:38 Uhr
Zeile 52:		Zeile 52:
	Jede WHILE-berechenbare Funktion kann durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.		Jede WHILE-berechenbare Funktion kann durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.

	'''Beweis:''' Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt „Simulation durch GOTO-Programme“ dieses Artikels beschrieben um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math> den Anweisungen im Abschnitt „Simulation durch WHILE-Programm“ im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm <math>P''</math> um. Hierbei ist zu beachten, dass die für diese Konstruktion notwendigen IF THEN END Anweisungen durch LOOPs simuliert werden können. Per Konstruktion hat <math>P''</math> nur eine WHILE-Schleife.		'''Beweis:''' Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt „Simulation durch GOTO-Programme“ dieses Artikels beschrieben, um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math> den Anweisungen im Abschnitt „Simulation durch WHILE-Programm“ im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm <math>P''</math> um. Hierbei ist zu beachten, dass die für diese Konstruktion notwendigen IF THEN END Anweisungen durch LOOPs simuliert werden können. Per Konstruktion hat <math>P''</math> nur eine WHILE-Schleife.

	== Konsequenzen ==		== Konsequenzen ==

Aka: typografische Anführungszeichen, Leerzeichen in Überschrift, Kleinkram

2022-10-10T18:44:04Z

typografische Anführungszeichen, Leerzeichen in Überschrift, Kleinkram

← Nächstältere Version		Version vom 10. Oktober 2022, 20:44 Uhr
Zeile 48:		Zeile 48:
	Mit <math>\mathrm{WHILE}</math> wird ferner die Menge aller WHILE-Programme gemäß obiger Definition bezeichnet.		Mit <math>\mathrm{WHILE}</math> wird ferner die Menge aller WHILE-Programme gemäß obiger Definition bezeichnet.

	==Kleenesche Normalform für WHILE-Programme==		== Kleenesche Normalform für WHILE-Programme ==

	Jede WHILE-berechenbare Funktion kann durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.		Jede WHILE-berechenbare Funktion kann durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.

	'''Beweis:''' Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt ~~"Simulation~~ durch GOTO-~~Programme"~~ dieses Artikels beschrieben um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math> den Anweisungen im Abschnitt ~~"Simulation~~ durch WHILE-~~Programm"~~ im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm <math>P''</math> um. Hierbei ist zu beachten, dass die für diese Konstruktion notwendigen IF THEN END Anweisungen durch LOOPs simuliert werden können. Per Konstruktion hat <math>P''</math> nur eine WHILE-Schleife.		'''Beweis:''' Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt „Simulation durch GOTO-Programme“ dieses Artikels beschrieben um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math> den Anweisungen im Abschnitt „Simulation durch WHILE-Programm“ im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm <math>P''</math> um. Hierbei ist zu beachten, dass die für diese Konstruktion notwendigen IF THEN END Anweisungen durch LOOPs simuliert werden können. Per Konstruktion hat <math>P''</math> nur eine WHILE-Schleife.

	==Konsequenzen==		== Konsequenzen ==

	Die einfach beweisbare Tatsache, dass jedes [[GOTO-Programm]] in ein WHILE-Programm überführt werden kann und umgekehrt, hat zur Konsequenz, dass man beweisen kann, dass ein beliebiges [[Pascal (Programmiersprache)\|Pascal]]-Programm die gleichen Leistungen erbringen kann wie ein beliebiges [[BASIC]]-Programm. Außerdem zeigt sie, dass man jedes Programm auch strukturiert programmieren kann, ohne „[[Spaghetticode]]“ zu erzeugen.		Die einfach beweisbare Tatsache, dass jedes [[GOTO-Programm]] in ein WHILE-Programm überführt werden kann und umgekehrt, hat zur Konsequenz, dass man beweisen kann, dass ein beliebiges [[Pascal (Programmiersprache)\|Pascal]]-Programm die gleichen Leistungen erbringen kann wie ein beliebiges [[BASIC]]-Programm. Außerdem zeigt sie, dass man jedes Programm auch strukturiert programmieren kann, ohne „[[Spaghetticode]]“ zu erzeugen.

	==Simulation durch GOTO-Programm==		== Simulation durch GOTO-Programm ==

	Ein jedes WHILE-Programm		Ein jedes WHILE-Programm
Zeile 69:		Zeile 69:
	GOTO M1;		GOTO M1;
	M2: ...		M2: ...


	== Siehe auch ==		== Siehe auch ==
	* [[LOOP-Programm]]		* [[LOOP-Programm]]

91.45.140.169 am 15. Mai 2021 um 08:59 Uhr

2021-05-15T08:59:06Z

← Nächstältere Version		Version vom 15. Mai 2021, 10:59 Uhr
Zeile 61:		Zeile 61:

	Ein jedes WHILE-Programm		Ein jedes WHILE-Programm
	:<math>\mathrm{WHILE} \quad x2 \ne 0 \quad\mathrm{DO} \quad P \quad\mathrm{END}</math>		:<math>\mathrm{WHILE} \quad x_2 \ne 0 \quad\mathrm{DO} \quad P \quad\mathrm{END}</math>

	kann durch das folgende GOTO-Programm simuliert werden:		kann durch das folgende GOTO-Programm simuliert werden:

Petarded: /* Kleenesche Normalform für WHILE-Programme */

2020-05-24T08:08:47Z

Kleenesche Normalform für WHILE-Programme

← Nächstältere Version		Version vom 24. Mai 2020, 10:08 Uhr
Zeile 50:		Zeile 50:
	==Kleenesche Normalform für WHILE-Programme==		==Kleenesche Normalform für WHILE-Programme==

	~~Falls der im obigen Abschnitt beschriebenen Syntax von WHILE-Programmen, zusätzlich IF THEN END Anweisungen hinzugefügt werden, dann gilt, dass jede~~ WHILE-berechenbare Funktion durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden ~~kann~~.		Jede WHILE-berechenbare Funktion kann durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.

	'''Beweis:''' Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt "Simulation durch GOTO-Programme" dieses Artikels beschrieben um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math> den Anweisungen im Abschnitt "Simulation durch WHILE-Programm" im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm um. Per Konstruktion hat ~~dieses~~ nur eine WHILE-Schleife.		'''Beweis:''' Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt "Simulation durch GOTO-Programme" dieses Artikels beschrieben um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math> den Anweisungen im Abschnitt "Simulation durch WHILE-Programm" im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm <math>P''</math> um. Hierbei ist zu beachten, dass die für diese Konstruktion notwendigen IF THEN END Anweisungen durch LOOPs simuliert werden können. Per Konstruktion hat <math>P''</math> nur eine WHILE-Schleife.

	==Konsequenzen==		==Konsequenzen==

Petarded: /* Kleenesche Normalform für WHILE-Programme */

2020-05-23T11:17:13Z

Kleenesche Normalform für WHILE-Programme

← Nächstältere Version		Version vom 23. Mai 2020, 13:17 Uhr
Zeile 52:		Zeile 52:
	Falls der im obigen Abschnitt beschriebenen Syntax von WHILE-Programmen, zusätzlich IF THEN END Anweisungen hinzugefügt werden, dann gilt, dass jede WHILE-berechenbare Funktion durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden kann.		Falls der im obigen Abschnitt beschriebenen Syntax von WHILE-Programmen, zusätzlich IF THEN END Anweisungen hinzugefügt werden, dann gilt, dass jede WHILE-berechenbare Funktion durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden kann.

	Beweis: Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt "Simulation durch GOTO-Programme" dieses Artikels beschrieben um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math> den Anweisungen im Abschnitt "Simulation durch WHILE-Programm" im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm um. Per Konstruktion hat dieses nur eine WHILE-Schleife.		'''Beweis:''' Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt "Simulation durch GOTO-Programme" dieses Artikels beschrieben um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math> den Anweisungen im Abschnitt "Simulation durch WHILE-Programm" im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm um. Per Konstruktion hat dieses nur eine WHILE-Schleife.

	==Konsequenzen==		==Konsequenzen==

Petarded: /* Kleenesche Normalform für WHILE-Programme */

2020-05-23T11:13:15Z

Kleenesche Normalform für WHILE-Programme

← Nächstältere Version		Version vom 23. Mai 2020, 13:13 Uhr
Zeile 50:		Zeile 50:
	==Kleenesche Normalform für WHILE-Programme==		==Kleenesche Normalform für WHILE-Programme==

	Falls, der im obigen Abschnitt beschriebenen Syntax von WHILE-Programmen, zusätzlich IF THEN END Anweisungen hinzugefügt werden, dann gilt, dass jede WHILE-berechenbare Funktion durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden kann.		Falls der im obigen Abschnitt beschriebenen Syntax von WHILE-Programmen, zusätzlich IF THEN END Anweisungen hinzugefügt werden, dann gilt, dass jede WHILE-berechenbare Funktion durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden kann.

	Beweis: Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt "Simulation durch GOTO-Programme" dieses Artikels beschrieben, um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math>, den Anweisungen im Abschnitt "Simulation durch WHILE-Programm" im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm um. Per Konstruktion hat dieses nur eine WHILE-Schleife.		Beweis: Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt "Simulation durch GOTO-Programme" dieses Artikels beschrieben um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math> den Anweisungen im Abschnitt "Simulation durch WHILE-Programm" im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm um. Per Konstruktion hat dieses nur eine WHILE-Schleife.

	==Konsequenzen==		==Konsequenzen==

Petarded am 23. Mai 2020 um 11:09 Uhr

2020-05-23T11:09:00Z

← Nächstältere Version		Version vom 23. Mai 2020, 13:09 Uhr
Zeile 50:		Zeile 50:
	==Kleenesche Normalform für WHILE-Programme==		==Kleenesche Normalform für WHILE-Programme==

	Falls, der im obigen Abschnitt beschriebenen Syntax von WHILE-Programmen, zusätzlich IF THEN END Anweisungen hinzugefügt werden, dann gilt, dass jede WHILE-berechenbare Funktion durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.		Falls, der im obigen Abschnitt beschriebenen Syntax von WHILE-Programmen, zusätzlich IF THEN END Anweisungen hinzugefügt werden, dann gilt, dass jede WHILE-berechenbare Funktion durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden kann.

	Beweis: Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt "Simulation durch GOTO-Programme" dieses Artikels beschrieben, um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math>, den Anweisungen im Abschnitt "Simulation durch WHILE-Programm" im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm um. Per Konstruktion hat dieses nur eine WHILE-Schleife.		Beweis: Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt "Simulation durch GOTO-Programme" dieses Artikels beschrieben, um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math>, den Anweisungen im Abschnitt "Simulation durch WHILE-Programm" im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm um. Per Konstruktion hat dieses nur eine WHILE-Schleife.

Petarded: /* Kleenesche Normalform für WHILE-Programme */

2020-05-23T11:04:13Z

Kleenesche Normalform für WHILE-Programme

← Nächstältere Version		Version vom 23. Mai 2020, 13:04 Uhr
Zeile 50:		Zeile 50:
	==Kleenesche Normalform für WHILE-Programme==		==Kleenesche Normalform für WHILE-Programme==

	~~Jede~~ WHILE-berechenbare Funktion ~~kann~~ durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.		Falls, der im obigen Abschnitt beschriebenen Syntax von WHILE-Programmen, zusätzlich IF THEN END Anweisungen hinzugefügt werden, dann gilt, dass jede WHILE-berechenbare Funktion durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.

	Beweis: Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten, ~~und~~ ~~dann~~ ~~wieder~~ ~~zurück~~ in ein äquivalentes WHILE-Programm ~~<math>P''</math>~~. Per Konstruktion hat dieses nur eine WHILE-Schleife.		Beweis: Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst, wie im Abschnitt "Simulation durch GOTO-Programme" dieses Artikels beschrieben, um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten. Anschließend formen wir <math>P'</math>, den Anweisungen im Abschnitt "Simulation durch WHILE-Programm" im Artikel [[GOTO-Programm]] folgend in ein äquivalentes WHILE-Programm um. Per Konstruktion hat dieses nur eine WHILE-Schleife.

	==Konsequenzen==		==Konsequenzen==

Brischniak: Ein fehlendes Komma eingefügt.

2019-10-24T21:21:06Z

Ein fehlendes Komma eingefügt.

← Nächstältere Version		Version vom 24. Oktober 2019, 23:21 Uhr
Zeile 52:		Zeile 52:
	Jede WHILE-berechenbare Funktion kann durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.		Jede WHILE-berechenbare Funktion kann durch ein WHILE-Programm mit nur einer WHILE-Schleife berechnet werden.

	Beweis: Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten und dann wieder zurück in ein äquivalentes WHILE-Programm <math>P''</math>. Per Konstruktion hat dieses nur eine WHILE-Schleife.		Beweis: Sei <math>P</math> ein beliebiges WHILE-Programm. Wir formen <math>P</math> zunächst um, um ein äquivalentes GOTO-Programm <math>P'</math> zu erhalten, und dann wieder zurück in ein äquivalentes WHILE-Programm <math>P''</math>. Per Konstruktion hat dieses nur eine WHILE-Schleife.

	==Konsequenzen==		==Konsequenzen==

Trustable: Kapitelreihenfolge

2018-03-03T20:12:55Z

Kapitelreihenfolge

← Nächstältere Version		Version vom 3. März 2018, 22:12 Uhr
Zeile 38:		Zeile 38:
	::<math>\mathrm{WHILE} \quad x_8 \ne 0 \quad \mathrm{DO} \quad x_8:=x_8+1 \quad\mathrm{END}</math>		::<math>\mathrm{WHILE} \quad x_8 \ne 0 \quad \mathrm{DO} \quad x_8:=x_8+1 \quad\mathrm{END}</math>

	Die Anweisungen sind für sich genommen bereits vollständige WHILE-Programme. Des Weiteren ist die		Die Anweisungen sind für sich genommen bereits vollständige WHILE-Programme. Des Weiteren ist die
	* Aneinanderreihung von WHILE-Programmen, jeweils getrennt durch ein Semikolon, etwa		* Aneinanderreihung von WHILE-Programmen, jeweils getrennt durch ein Semikolon, etwa
	::<math>x_9:=x_9+3; \quad x_{10}:=x_9-2</math>		::<math>x_9:=x_9+3; \quad x_{10}:=x_9-2</math>
Zeile 69:		Zeile 69:
	GOTO M1;		GOTO M1;
	M2: ...		M2: ...

		⚫	== Siehe auch ==
		⚫	* [[LOOP-Programm]]
		⚫	* [[GOTO-Programm]]

	== Literatur ==		== Literatur ==
	*{{Literatur\| Autor=[[Uwe Schöning]]\| Titel=Theoretische Informatik – kurz gefasst\| Auflage=5\| Verlag=Spektrum Akademischer Verlag\| Ort=Heidelberg\| Kapitel=2.3 LOOP-, WHILE und GOTO-Berechenbarkeit\| ISBN=978-3-8274-1824-1}}		* {{Literatur\| Autor=[[Uwe Schöning]]\| Titel=Theoretische Informatik – kurz gefasst\| Auflage=5\| Verlag=Spektrum Akademischer Verlag\| Ort=Heidelberg\| Kapitel=2.3 LOOP-, WHILE und GOTO-Berechenbarkeit\| ISBN=978-3-8274-1824-1}}

⚫	==Siehe auch==
⚫	*[[LOOP-Programm]]
⚫	*[[GOTO-Programm]]


	[[Kategorie:Berechenbarkeitstheorie]]		[[Kategorie:Berechenbarkeitstheorie]]