Ackermann-Funktion < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Umfrage) Beendete Umfrage  | | Datum: | 03:04 Mi 01.04.2015 | | Autor: | mariem |
Hallo,
ich besuche die Vorlesung der Berechenbarkeitstheorie.
Wir müssen am Ende des Semesters einen Vortrag halten über ein Thema der Berechenbarkeitstheorie.
Ich habe mich für die Ackermann-Funktion entschieden.
Außer den Beweis dass die Funktion rekursiv aber nicht primitiv rekursiv ist, worüber kann man noch bei einen Vortrag über die Ackermann-Funktion sagen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:42 Do 02.04.2015 | | Autor: | Josef |
Hallo mariem,
>
> Ich habe mich für die Ackermann-Funktion entschieden.
>
> Außer den Beweis dass die Funktion rekursiv aber nicht
> primitiv rekursiv ist, worüber kann man noch bei einen
> Vortrag über die Ackermann-Funktion sagen?
"Modifizierte Ackermannfunktion
Häufig werden in der Komplexitätsanalyse leicht modifizierte Versionen der Ackermannfunktion verwendet, die jedoch das gleiche asymptotische Laufzeitverhalten aufweisen. Eine dieser Varianten erlaubt eine Interpretation als „verallgemeinerte Exponentialfunktion“."
![[]](/images/popup.gif) Quelle
Viele Grüße
Josef
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:52 Do 02.04.2015 | | Autor: | Josef |
Hallo mariem,
man kann beweisen, dass die Ackermann-Funktion berechenbar, aber nicht primitiv-rekursiv ist. Weil sie aber µ-rekursiv ist, ist sie auch TURING-berechenbar." Du kannst erläutern, was eine TURING-Maschine ist.
Quelle
Viele Grüße
Josef
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:23 Mo 06.04.2015 | | Autor: | mariem |
> man kann beweisen, dass die Ackermann-Funktion berechenbar,
> aber nicht primitiv-rekursiv ist.
Ich habe mir das Video auf Youtube ( https://www.youtube.com/watch?v=VZz7m91XxoM ) angeschaut, und habe ein paar Fragen.
Um zu zeigen dass die Ackermann-Funktion nicht primitiv rekursiv ist, muss man zeigen dass diese schneller als alle primitiv rekursive Funktionen wächst.
Um das zu zeigen muss man folgendes beweisen:
Sei [mm] f(x_1, \dots [/mm] , [mm] x_n) [/mm] eine primitiv rekursive Funktion. Dann gibt es ein (festes) u, sodass
[mm] f(x_1 [/mm] , [mm] \dots [/mm] , [mm] x_n) \leq [/mm] a(u, [mm] \max (x_1, \dots [/mm] , [mm] x_n)), \forall x_1, \dots [/mm] , [mm] x_n. [/mm]
Ich habe nicht verstanden warum das nicht für die Ackermann selbst geht.
Könntest du mir das erklären?
Außerdem wie könnte man formell beweisen dass
[mm] \max(x,y,a(w,x+y))=a(w,x+y) [/mm] und a(w, 2 [mm] \max [/mm] (x,y)) [mm] \leq [/mm] a(w+2, [mm] \max [/mm] (x,y)) ?
Um die Ungleichung a(w,x+y) [mm] \leq [/mm] a(w,2 [mm] \max [/mm] (x,y)) benutzen zu können muss man vorher gezeigt haben dass die Ackermann eine steigende Funtion ist?
Könntest du mir auch erklären wie man beweisen kann dass die Ackermann-Funktion rekursiv ist?
Um zu zeigen dass die Ackermann-Funktion berechenbar ist muss man ein Programm schreiben, das die Funktion berechnet?
>Weil sie aber µ-rekursiv
> ist, ist sie auch TURING-berechenbar.
Was ist eine µ-rekursive Funktion? Welche ist der Unterschied zwischen eine rekursive und eine µ-rekursive Funktion?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 05:15 Di 07.04.2015 | | Autor: | Josef |
Hallo,
> > man kann beweisen, dass die Ackermann-Funktion berechenbar,
> > aber nicht primitiv-rekursiv ist.
>
> Um zu zeigen dass die Ackermann-Funktion nicht primitiv
> rekursiv ist, muss man zeigen dass diese schneller als alle
> primitiv rekursive Funktionen wächst.
> Um das zu zeigen muss man folgendes beweisen:
> Sei [mm]f(x_1, \dots[/mm] , [mm]x_n)[/mm] eine primitiv rekursive Funktion.
> Dann gibt es ein (festes) u, sodass
> [mm]f(x_1[/mm] , [mm]\dots[/mm] , [mm]x_n) \leq[/mm] a(u, [mm]\max (x_1, \dots[/mm] , [mm]x_n)), \forall x_1, \dots[/mm]
> , [mm]x_n.[/mm]
> Ich habe nicht verstanden warum das nicht für die
> Ackermann selbst geht.
>
> Könntest du mir auch erklären wie man beweisen kann dass
> die Ackermann-Funktion rekursiv ist?
>
>
> Um zu zeigen dass die Ackermann-Funktion berechenbar ist
> muss man ein Programm schreiben, das die Funktion
> berechnet?
>
>
"Der Beweis, dass die Ackermannfunktion berechenbar ist, aber nicht primitiv-rekursiv, nutzt im Wesentlichen aus, dass die Ackermannfunktion stärker wächst als jede primitiv-rekursive Funktion."
siehe Beweisskizze zur Behauptung, dass die Ackermannfunktion nicht primitiv-rekursiv ist:
Viele Grüße
Josef
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 05:26 Di 07.04.2015 | | Autor: | Josef |
Hallo,
> Was ist eine µ-rekursive Funktion? Welche ist der
> Unterschied zwischen eine rekursive und eine µ-rekursive
> Funktion?
>
Siehe unter:
μ-Rekursion
Viele Grüße
Josef
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:46 Sa 11.04.2015 | | Autor: | mariem |
Also soll der Vortrag folgenderweise aussehen?
-Historische Einordnung/Entstehungsgeschichte
-Definition der Ackermann-Funktion
-Beispiel für die Auswertung an kleinen Werten
-Wertetabelle, um das schnelle Wachstum zu verdeutlichen
-Beweis dass die Ackermann-Funktion nicht primitiv rekursiv ist
-Beweis dass die Ackermann-Funktion rekursiv/TURING-berechenbar ist
Was meinst du? Ist das eine gute Struktur für den Vortrag oder könnte ich etwas ändern, z.B. etwas hinzufügen, etwas weglassen oder die Reihenfolge ändern?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:13 Sa 11.04.2015 | | Autor: | Josef |
Hallo mariem,
> Also soll der Vortrag folgenderweise aussehen?
> -Historische Einordnung/Entstehungsgeschichte
> -Definition der Ackermann-Funktion
Ackermanns Idee
Bedeutung in der theoretischen Informatik
> -Beispiel für die Auswertung an kleinen Werten
> -Wertetabelle, um das schnelle Wachstum zu verdeutlichen
> -Beweis dass die Ackermann-Funktion nicht primitiv rekursiv
> ist
> -Beweis dass die Ackermann-Funktion
> rekursiv/TURING-berechenbar ist
Anwendungen
Viele Grüße
Josef
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:36 Di 21.04.2015 | | Autor: | mariem |
Könnte ich es folgenderweise formulieren?
Die Originalfunktion von Ackermann ist die Abbildung [mm] \phi [/mm] : [mm] \mathbb{N}^3 \rightarrow \mathbb{N} [/mm] die folgenderweise rekursiv definiert wird:
[mm] \phi(a,b,0)=a+b [/mm]
[mm] \phi(a,0,n+1)=\alpha [/mm] (a,n)
[mm] \phi(a,b+1, n+1)=\phi(a, \phi(a,b,n+1),n) [/mm]
[mm] \text{ wobei }\alpha(a,n)=\left\{\begin{matrix}
0 & , n=0 \\
1 & , n=1 \\
a & , n>1
\end{matrix}\right. [/mm]
Die vereinfachte Version von Peter, die heute als die Ackermann-Funktion bekannt ist, ist die Abbildung A: [mm] \mathbb{N}^2 \rightarrow \mathbb{N} [/mm] die folgenderweise rekursiv definiert wird: [mm] A(m,n)\left\{\begin{matrix}
n+1 & , m=0\\
A(m-1,1) & , m>0 , n=0\\
A(m-1,A(m,n-1))& ,m>0,n>0
\end{matrix}\right. [/mm]
Die Ackermann-Funktion ist wohldefiniert, also für alle x, y [mm] \in \mathbb{N} [/mm] gibt es ein z [mm] \in \mathbb{N} [/mm] sodass A(x,y)=z.
Beweis: [mm] \dots \dots \dots \dots \dots [/mm]
Die Ackermann-Funktion ist eine der wichtigsten Funktionen in der Informatik. Sie hat die Eigenschaft, dass sie erstaunlich schnell wächst, wie man auf der Wertetabelle sehen kann: [mm] \dots \dots \dots \dots \dots [/mm]
Sogar für kleine Werte von n und m ist der Wert den Funktion riesig. Zum Beispiel, A(4,2) hat schon 19.729 Dezimalstellen!
Ist das so richtig?
Könnte ich etwas verbessern?
Könnte ich etwas hinzufügen oder weglassen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:54 Mi 22.04.2015 | | Autor: | Josef |
Hallo,
>
> Die Originalfunktion von Ackermann ist die Abbildung [mm]\phi[/mm] :
> [mm]\mathbb{N}^3 \rightarrow \mathbb{N}[/mm]
[mm] N^3 \rightarrow{N} [/mm] ?
> die folgenderweise
> rekursiv definiert wird:
> [mm]\phi(a,b,0)=a+b[/mm]
> [mm]\phi(a,0,n+1)=\alpha[/mm] (a,n)
> [mm]\phi(a,b+1, n+1)=\phi(a, \phi(a,b,n+1),n)[/mm]
> [mm]\text{ wobei }\alpha(a,n)=\left\{\begin{matrix}
0 & , n=0 \\
1 & , n=1 \\
a & , n>1
\end{matrix}\right.[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> Sogar für kleine Werte von n und m ist der Wert den
> Funktion riesig. Zum Beispiel, A(4,2) hat schon 19.729
> Dezimalstellen!
Die übrigen Angaben habe ich nicht geprüft.
Viele Grüße
Josef
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 05:15 So 17.05.2015 | | Autor: | mariem |
ch habe mit den Lehrer gesprochen und er hat mit gesagt dass ich den folgenden Punkt:
-Beweis dass die Ackermann-Funktion rekursiv/TURING-berechenbar ist
weglassen kann. Ich soll einfach ein Beispiel wie man ein Wert der Funktion berechnet, geben.
Außerdem hat er gesagt dass ich am Ende des Vortrages zum Publikum Fragen stellen sollte. Was für Fragen kann man stellen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:39 So 17.05.2015 | | Autor: | Josef |
> Außerdem hat er gesagt dass ich am Ende des Vortrages zum
> Publikum Fragen stellen sollte. Was für Fragen kann man
> stellen?
Quiz:
Beantworten Sie kurz die folgenden Fragen:
1. Jede unentscheidbare Sprache enthält eine entscheidbare Teilmenge.
2. Jede Teilmenge einer entscheidbaren Sprache ist entscheidbar.
3. Für jede unentscheidbare Sprache A gibt es eine echte Obermenge, die ebenfalls unentscheidbar ist.
4. Aus "A entscheidbar" und "A [mm] \cap [/mm] B entscheidbar" folgt "B entscheidbar".
siehe Quiz 1 und Lösungsvorschläge; Seite 5
Viele Grüße
Josef
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:04 Mo 18.05.2015 | | Autor: | mariem |
Könnte man vielleicht auch etwas über primitiv rekursive Funktionen fragen oder direkt über die Ackermann-Funktion?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:48 Di 19.05.2015 | | Autor: | Josef |
Hallo,
> Könnte man vielleicht auch etwas über primitiv rekursive
> Funktionen fragen oder direkt über die Ackermann-Funktion?
Selbstverständlich können entsprechende Fragen gestellt werden.
Viele Grüße
Josef
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:23 Fr 03.04.2015 | | Autor: | Josef |
Hallo mariem,
>
> Außer den Beweis dass die Funktion rekursiv aber nicht
> primitiv rekursiv ist, worüber kann man noch bei einen
> Vortrag über die Ackermann-Funktion sagen?
Was hat die Ackermannfunktion mit dem Hyper-Operator und mit den Grundrechenarten zu tun?
Siehe auch hier
Inzwischen wurden Funktionen gefunden, die noch schneller wachsen als die Ackermann-Funktion.
Viele Grüße
Josef
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:25 Fr 03.04.2015 | | Autor: | tobit09 |
Hallo mariem!
> ich besuche die Vorlesung der Berechenbarkeitstheorie.
(Dann gehe ich davon aus, dass Begriffe wie rekursiv/Turing-berechenbar und Churche These bekannt sind und nicht mehr erläutert werden müssen.)
> Außer den Beweis dass die Funktion rekursiv aber nicht
> primitiv rekursiv ist, worüber kann man noch bei einen
> Vortrag über die Ackermann-Funktion sagen?
Das sind auch schon zwei Beweise.
Weitere Punkte, die ich dem Wikipedia-Artikel zur Ackermannfunktion entnommen habe (auch auf die Gefahr hin, schon von Josef genannte Punkte zu wiederholen):
1. Motivation / historische Einordnung:
- 1926 äußert Hilbert die Vermutung, dass die primitiv rekursiven Funktionen bereits alle berechenbaren Funktionen seien, da alle bekannten berechenbaren Funktionen primitiv zu sein schienen.
- Ebenfalls 1926 (Veröffentlichung 1928) entdeckt Ackermann Gegenbeispiel.
- Idee dazu: Extrem schnell wachsende, das größer als jedes Wachstum einer primitiv berechenbaren Funktion ist (ggf. Vergleich eines Funktionswertes mit geschätzter Anzahl der Atome im Universum)
- Später vereinfachte Varianten mit vergleichbaren Eigenschaften.
- Heute wird von Ackermann entwickelte Funktion (bzw. deren Varianten ) als "Ackermannfunktion" bezeichnet.
2. Definition einer Variante; dazu:
- mehrparametrige und einparametrige "Untervariante"
- Wohldefiniertheit
- ggf. Beispiel für die Auswertung an kleinen Werten, um Verständnis der Definition zu verbessern
- ggf. (falls du nicht die heute meistgenutzte Peter-Variante benutzt) Zusammenhang zu wiederholter Addition, wiederholter Multiplikation, wiederholten Potenzen, ... herstellen, um Grundidee hinter Definition zu vermitteln
- ggf. Wertetabelle, um das schnelle Wachstum zu verdeutlichen
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:12 Mo 06.04.2015 | | Autor: | mariem |
> > Außer den Beweis dass die Funktion rekursiv aber nicht
> > primitiv rekursiv ist, worüber kann man noch bei einen
> > Vortrag über die Ackermann-Funktion sagen?
> Das sind auch schon zwei Beweise.
Ich habe mir das Video auf Youtube ( https://www.youtube.com/watch?v=VZz7m91XxoM ) angeschaut, und habe ein paar Fragen.
Um zu zeigen dass die Ackermann-Funktion nicht primitiv rekursiv ist, muss man zeigen dass diese schneller als alle primitiv rekursive Funktionen wächst.
Um das zu zeigen muss man folgendes beweisen:
Sei [mm] f(x_1, \dots [/mm] , [mm] x_n) [/mm] eine primitiv rekursive Funktion. Dann gibt es ein (festes) u, sodass
[mm] f(x_1 [/mm] , [mm] \dots [/mm] , [mm] x_n) \leq [/mm] a(u, [mm] \max (x_1, \dots [/mm] , [mm] x_n)), \forall x_1, \dots [/mm] , [mm] x_n. [/mm]
Ich habe nicht verstanden warum das nicht für die Ackermann selbst geht.
Könntest du mir das erklären?
Außerdem wie könnte man formell beweisen dass
[mm] \max(x,y,a(w,x+y))=a(w,x+y) [/mm] und a(w, 2 [mm] \max [/mm] (x,y)) [mm] \leq [/mm] a(w+2, [mm] \max [/mm] (x,y)) ?
Um die Ungleichung a(w,x+y) [mm] \leq [/mm] a(w,2 [mm] \max [/mm] (x,y)) benutzen zu können muss man vorher gezeigt haben dass die Ackermann eine steigende Funtion ist?
Könntest du mir auch erklären wie man beweisen kann dass die Ackermann-Funktion rekursiv ist?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:52 Fr 10.04.2015 | | Autor: | tobit09 |
> Ich habe mir das Video auf Youtube (
> https://www.youtube.com/watch?v=VZz7m91XxoM ) angeschaut,
> und habe ein paar Fragen.
Das Video skizziert die Ideen ohne alles zu beweisen.
Man braucht in der Tat wohl zunächst ein paar Monotonieaussagen, die ich aus "Uwe Schöning: Theoretische Informatik - kurzgefasst" übernehme:
Für alle natürlichen Zahlen x und y gelten die folgenden Ungleichungen:
(A) $y<a(x,y)$
(B) $a(x,y)<a(x,y+1)$
(C) [mm] $a(x,y+1)\le [/mm] a(x+1,y)$
(D) $a(x,y)<a(x+1,y)$
Aus (B) folgt
(B') [mm] $a(x,y)\le [/mm] a(x,y')$ für alle natürlichen Zahlen [mm] $y'\ge [/mm] y$.
Aus (D) folgt
(D') [mm] $a(x,y)\le [/mm] a(x',y)$ für alle natürlichen Zahlen [mm] $x'\ge [/mm] x$.
> Um zu zeigen dass die Ackermann-Funktion nicht primitiv
> rekursiv ist, muss man zeigen dass diese schneller als alle
> primitiv rekursive Funktionen wächst.
> Um das zu zeigen muss man folgendes beweisen:
> Sei [mm]f(x_1, \dots[/mm] , [mm]x_n)[/mm] eine primitiv rekursive Funktion.
> Dann gibt es ein (festes) u, sodass
> [mm]f(x_1[/mm] , [mm]\dots[/mm] , [mm]x_n) \leq[/mm] a(u, [mm]\max (x_1, \dots[/mm] , [mm]x_n)), \forall x_1, \dots[/mm]
> , [mm]x_n.[/mm]
> Ich habe nicht verstanden warum das nicht für die
> Ackermann selbst geht.
> Könntest du mir das erklären?
Angenommen "es ginge auch für die Ackermannfunktion selbst", d.h. es gäbe eine natürliche Zahl u, so dass für alle natürlichen Zahlen x und y
[mm] $a(x,y)\le a(u,\max(x,y))$
[/mm]
gilt.
Dann erhalten wir insbesondere für $x:=u+1$ und $y:=u+1$ die Ungleichung
[mm] $a(u+1,u+1)\le [/mm] a(u,u+1)$.
Nach Ungleichung (D) gilt aber
$a(u,u+1)<a(u+1,u+1)$,
Widerspruch.
> Außerdem wie könnte man formell beweisen dass
> [mm]\max(x,y,a(w,x+y))=a(w,x+y)[/mm]
Zu zeigen ist [mm] $x\le [/mm] a(w,x+y)$ und [mm] $y\le [/mm] a(w,x+y)$.
Etwa ersteres (letzteres geht analog bzw. folgt aus Symmetrie-Gründen):
Gemäß Ungleichung (A) erhalten wir wie gewünscht die Ungleichungskette
[mm] $x\le [/mm] x+y<a(w,x+y)$.
> und a(w, 2 [mm]\max[/mm] (x,y)) [mm]\leq[/mm]
> a(w+2, [mm]\max[/mm] (x,y)) ?
Ich weiß nicht, ob es einfacher geht als wie folgt:
Es genügt, für alle natürlichen Zahlen z die Ungleichung
(*) [mm] $a(w,2z)\le [/mm] a(w+2,z)$
zu zeigen.
Wir tun dies per Induktion nach z:
Den Induktionsanfang (z=0) überlasse ich dir.
Gelte nun als Induktionsvoraussetzung (*) für ein festes z. Zu zeigen ist nun
[mm] $a(w,2(z+1))\le [/mm] a(w+2,z+1)$.
Hilfsüberlegung: Gemäß Ungleichung (A) gilt
$2z<a(w,2z)$
und somit
(**) [mm] $2z+1\le [/mm] a(w,2z)$.
Die zu zeigende Ungleichung folgt nun aus folgender Ungleichungs-Kette:
$a(w,2(z+1))$
$=a(w,2z+2)$
[mm] $\le [/mm] a(w+1,2z+1)$ (Ungleichung (C))
[mm] $\le [/mm] a(w+1,a(w,2z))$ ((**) und (B'))
[mm] $\le [/mm] a(w+1,a(w+2,z))$ (Induktionsvoraussetzung)
[mm] $\le [/mm] a(w+2,z+1)$ (Definition Ackermannfunktion).
> Um die Ungleichung a(w,x+y) [mm]\leq[/mm] a(w,2 [mm]\max[/mm] (x,y)) benutzen
> zu können muss man vorher gezeigt haben dass die Ackermann
> eine steigende Funtion ist?
Ja, das verwendet (B').
Du stellst genau die richtigen Fragen!
> Könntest du mir auch erklären wie man beweisen kann dass
> die Ackermann-Funktion rekursiv ist?
Wenn Argumentation mittels Churchscher These bei euch erlaubt ist, genügt dazu folgender (Rekursion verwendender) Pseudo-Code (den ich wieder im Wesentlichen von Schöning übernehme), der eigentlich nur die rekursive Definition wiedergibt:
Berechnung von a(x,y) (für natürliche Zahlen x und y):
If x=0 return y+1;
If y=0 return a(x-1,1);
return a(x-1,a(x,y-1));
Per "Doppelinduktion" kann man sich davon überzeugen, dass dieses Programm für alle natürlichen Zahlen x und y tatsächlich terminiert.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:45 Sa 11.04.2015 | | Autor: | mariem |
Ok... Ich werde den Beweis nochmal durchlesen...
Also soll der Vortrag folgenderweise aussehen?
-Historische Einordnung/Entstehungsgeschichte
-Definition der Ackermann-Funktion
-Beispiel für die Auswertung an kleinen Werten
-Wertetabelle, um das schnelle Wachstum zu verdeutlichen
-Beweis dass die Ackermann-Funktion nicht primitiv rekursiv ist
-Beweis dass die Ackermann-Funktion rekursiv/TURING-berechenbar ist
Was meinst du? Ist das eine gute Struktur für den Vortrag oder könnte ich etwas ändern, z.B. etwas hinzufügen, etwas weglassen oder die Reihenfolge ändern?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:03 Sa 11.04.2015 | | Autor: | tobit09 |
> Also soll der Vortrag folgenderweise aussehen?
> -Historische Einordnung/Entstehungsgeschichte
> -Definition der Ackermann-Funktion
> -Beispiel für die Auswertung an kleinen Werten
> -Wertetabelle, um das schnelle Wachstum zu verdeutlichen
> -Beweis dass die Ackermann-Funktion nicht primitiv rekursiv
> ist
> -Beweis dass die Ackermann-Funktion
> rekursiv/TURING-berechenbar ist
>
> Was meinst du? Ist das eine gute Struktur für den Vortrag
> oder könnte ich etwas ändern, z.B. etwas hinzufügen,
> etwas weglassen oder die Reihenfolge ändern?
Ich denke, das kannst du so machen.
Vergiss bei der Definition der Ackermann-Funktion nicht, die Wohldefiniertheit plausibel zu machen.
Die Reihenfolge der beiden Beweise am Ende würde ich tauschen, da die Rekursivität (im Falle der Nutzung der Churchschen These) recht schnell geht.
Solltest du bei einem Probevortrag Zeitmangel feststellen, könntest du die mittleren beiden Punkte wieder streichen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:10 Sa 11.04.2015 | | Autor: | mariem |
> Vergiss bei der Definition der Ackermann-Funktion nicht,
> die Wohldefiniertheit plausibel zu machen.
Wie macht man die Wohldefiniertheit plausibel?
> Die Reihenfolge der beiden Beweise am Ende würde ich
> tauschen, da die Rekursivität (im Falle der Nutzung der
> Churchschen These) recht schnell geht.
Also ich soll erst beweisen dass die Ackermann-Funktion rekursiv ist und dann dass sie nicht primitiv rekursiv ist, richtig?
> Solltest du bei einem Probevortrag Zeitmangel feststellen,
> könntest du die mittleren beiden Punkte wieder streichen.
Ok...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:43 Sa 11.04.2015 | | Autor: | tobit09 |
> > Vergiss bei der Definition der Ackermann-Funktion nicht,
> > die Wohldefiniertheit plausibel zu machen.
>
> Wie macht man die Wohldefiniertheit plausibel?
Anschaulich statt formal argumentiert (mit einer Art "Doppelinduktion", d.h. eine Art Induktion nach x und innerhalb des Induktionsschrittes eine Art Induktion nach y):
Gemäß der ersten der drei "Definitionszeilen" ist $a(x,y)$ für $x=0$ und alle [mm] $y\in\IN_0$ [/mm] direkt erklärt.
Sei nun $x>0$ und $a(x-1,y)$ für alle [mm] $y\in\IN_0$ [/mm] bereits sinnvoll erklärt.
Dann ist auch $a(x,y)$ für alle [mm] $y\in\IN_0$ [/mm] sinnvoll erklärt:
Für $y=0$ gilt dies gemäß der zweiten der drei "Definitionszeilen".
Für $y>0$ sei $a(x,y-1)$ schon sinnvoll erklärt.
Dann ist auch $a(x,y)$ gemäß der letzten der drei "Definitionszeilen" sinnvoll erklärt.
> > Die Reihenfolge der beiden Beweise am Ende würde ich
> > tauschen, da die Rekursivität (im Falle der Nutzung der
> > Churchschen These) recht schnell geht.
>
> Also ich soll erst beweisen dass die Ackermann-Funktion
> rekursiv ist und dann dass sie nicht primitiv rekursiv ist,
> richtig?
Ja, genau das meinte ich mit meinem Vorschlag.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:20 Sa 18.04.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:32 So 19.04.2015 | | Autor: | tobit09 |
Sorry, dass ich nicht rechtzeitig zum Antworten gekommen bin.
Falls du noch interessiert bist:
> Sage ich welche die origialversion von Ackermann ist und
> welche die Version von Peter ist?
Im Rahmen eines Vortrages würde ich nur eine der Versionen wirklich definieren und konsequent mit dieser Version arbeiten.
Wenn du die Peter-Version nimmst, kannst du etwa schreiben:
Die Ackermann-Funktion ist die Abbildung [mm] $a\colon\IN^2\to\IN$ [/mm] definiert durch
(hier die drei Gleichungen von Wikipedia einfügen)
für alle [mm] $n,m\in\IN$.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:08 Mo 20.04.2015 | | Autor: | mariem |
Ok...
Meinst du dass es eine gute Idee wäre die Knuth Pfeilnotation zu erwähnen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:44 Mo 20.04.2015 | | Autor: | tobit09 |
> Meinst du dass es eine gute Idee wäre die Knuth
> Pfeilnotation zu erwähnen?
Aus meiner Sicht führt diese Notation zu weit vom eigentlichen Thema weg.
Insbesondere wenn du die Peter-Version nimmst, würdest du es schwer haben, den Bezug zur Knuth Pfeilnotation herzustellen.
Du kannst übrigens auch den/die Veranstalter(in) des Seminars fragen, was er/sie erwartet; dann bist du auf der ganz sicheren Seite.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:31 Di 21.04.2015 | | Autor: | mariem |
Könnte ich es folgenderweise formulieren?
Die Originalfunktion von Ackermann ist die Abbildung [mm] \phi [/mm] : [mm] \mathbb{N}^3 \rightarrow \mathbb{N} [/mm] die folgenderweise rekursiv definiert wird:
[mm] \phi(a,b,0)=a+b [/mm]
[mm] \phi(a,0,n+1)=\alpha [/mm] (a,n)
[mm] \phi(a,b+1, n+1)=\phi(a, \phi(a,b,n+1),n) [/mm]
[mm] \text{ wobei }\alpha(a,n)=\left\{\begin{matrix}
0 & , n=0 \\
1 & , n=1 \\
a & , n>1
\end{matrix}\right. [/mm]
Die vereinfachte Version von Peter, die heute als die Ackermann-Funktion bekannt ist, ist die Abbildung A: [mm] \mathbb{N}^2 \rightarrow \mathbb{N} [/mm] die folgenderweise rekursiv definiert wird: [mm] A(m,n)\left\{\begin{matrix}
n+1 & , m=0\\
A(m-1,1) & , m>0 , n=0\\
A(m-1,A(m,n-1))& ,m>0,n>0
\end{matrix}\right. [/mm]
Die Ackermann-Funktion ist wohldefiniert, also für alle x, y [mm] \in \mathbb{N} [/mm] gibt es ein z [mm] \in \mathbb{N} [/mm] sodass A(x,y)=z.
Beweis: [mm] \dots \dots \dots \dots \dots [/mm]
Die Ackermann-Funktion ist eine der wichtigsten Funktionen in der Informatik. Sie hat die Eigenschaft, dass sie erstaunlich schnell wächst, wie man auf der Wertetabelle sehen kann: [mm] \dots \dots \dots \dots \dots [/mm]
Sogar für kleine Werte von n und m ist der Wert den Funktion riesig. Zum Beispiel, A(4,2) hat schon 19.729 Dezimalstellen!
Ist das so richtig?
Könnte ich etwas verbessern?
Könnte ich etwas hinzufügen oder weglassen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:40 Mi 22.04.2015 | | Autor: | tobit09 |
> Könnte ich es folgenderweise formulieren?
>
> Die Originalfunktion von Ackermann ist die Abbildung [mm]\phi[/mm] :
> [mm]\mathbb{N}^3 \rightarrow \mathbb{N}[/mm] die folgenderweise
> rekursiv definiert wird:
> [mm]\phi(a,b,0)=a+b[/mm]
> [mm]\phi(a,0,n+1)=\alpha[/mm] (a,n)
> [mm]\phi(a,b+1, n+1)=\phi(a, \phi(a,b,n+1),n)[/mm]
> [mm]\text{ wobei }\alpha(a,n)=\left\{\begin{matrix}
0 & , n=0 \\
1 & , n=1 \\
a & , n>1
\end{matrix}\right.[/mm]
> Die vereinfachte Version von Peter, die heute als die
> Ackermann-Funktion bekannt ist, ist die Abbildung A:
> [mm]\mathbb{N}^2 \rightarrow \mathbb{N}[/mm] die folgenderweise
> rekursiv definiert wird: [mm]A(m,n)\left\{\begin{matrix}
n+1 & , m=0\\
A(m-1,1) & , m>0 , n=0\\
A(m-1,A(m,n-1))& ,m>0,n>0
\end{matrix}\right.[/mm]
> Die Ackermann-Funktion ist wohldefiniert, also für alle x,
> y [mm]\in \mathbb{N}[/mm] gibt es ein z [mm]\in \mathbb{N}[/mm] sodass
> A(x,y)=z.
> Beweis: [mm]\dots \dots \dots \dots \dots[/mm]
Aus meiner Sicht trifft diese Beschreibung nicht ganz den Kern der Wohldefiniertheit, nämlich dass es genau eine Abbildung [mm] $A\colon\IN^2\to\IN$ [/mm] gibt, die den obigen Rekursions-Gleichungen genügt.
Da du den Beweis aber ohnehin eher anschaulich und nicht formal führen wirst, könntest vor dem Beweis einfach nur schreiben:
"Hierdurch wird tatsächlich eine Abbildung [mm] $A\colon\IN^2\to\IN$ [/mm] definiert:"
> Die Ackermann-Funktion ist eine der wichtigsten Funktionen
> in der Informatik.
(Das kann ich nicht beurteilen.)
> Sie hat die Eigenschaft, dass sie
> erstaunlich schnell wächst, wie man auf der Wertetabelle
> sehen kann: [mm]\dots \dots \dots \dots \dots[/mm]
>
> Sogar für kleine Werte von n und m ist der Wert den
> Funktion riesig. Zum Beispiel, A(4,2) hat schon 19.729
> Dezimalstellen!
(Eventuell könntest du diesen Abschnitt mündlich vortragen und nur Wertetabelle und Anzahl der Dezimalstellen von A(4,2) anschreiben.)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:23 So 26.04.2015 | | Autor: | mariem |
> > Die Ackermann-Funktion ist wohldefiniert, also für alle x,
> > y [mm]\in \mathbb{N}[/mm] gibt es ein z [mm]\in \mathbb{N}[/mm] sodass
> > A(x,y)=z.
> > Beweis: [mm]\dots \dots \dots \dots \dots[/mm]
> Aus meiner Sicht trifft diese Beschreibung nicht ganz den
> Kern der Wohldefiniertheit, nämlich dass es genau eine
> Abbildung [mm]A\colon\IN^2\to\IN[/mm] gibt, die den obigen
> Rekursions-Gleichungen genügt.
>
> Da du den Beweis aber ohnehin eher anschaulich und nicht
> formal führen wirst, könntest vor dem Beweis einfach nur
> schreiben:
>
> "Hierdurch wird tatsächlich eine Abbildung
> [mm]A\colon\IN^2\to\IN[/mm] definiert:"
Also meinst du dass wenn man folgendes sagt:
"Die Ackermann-Funktion ist wohldefiniert, also für alle x, y [mm]\in \mathbb{N}[/mm] gibt es ein z [mm]\in \mathbb{N}[/mm] sodass A(x,y)=z. "
zeigt man nicht dass es nur ein z [mm]\in \mathbb{N}[/mm] gibt sodass A(x,y)=z ? Oder habe ich es falsch verstanden?
> > Sie hat die Eigenschaft, dass sie
> > erstaunlich schnell wächst, wie man auf der Wertetabelle
> > sehen kann: [mm]\dots \dots \dots \dots \dots[/mm]
> >
> > Sogar für kleine Werte von n und m ist der Wert den
> > Funktion riesig. Zum Beispiel, A(4,2) hat schon 19.729
> > Dezimalstellen!
> (Eventuell könntest du diesen Abschnitt mündlich
> vortragen und nur Wertetabelle und Anzahl der
> Dezimalstellen von A(4,2) anschreiben.)
Welchen Abschnitt meinst du genau soll ich mündlich vortragen? Den folgenden?
"Sie hat die Eigenschaft, dass sie erstaunlich schnell wächst. Sogar für kleine Werte von n und m ist der Wert den Funktion riesig."
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:40 Mo 27.04.2015 | | Autor: | tobit09 |
> > > Die Ackermann-Funktion ist wohldefiniert, also für alle x,
> > > y [mm]\in \mathbb{N}[/mm] gibt es ein z [mm]\in \mathbb{N}[/mm] sodass
> > > A(x,y)=z.
> > > Beweis: [mm]\dots \dots \dots \dots \dots[/mm]
> > Aus meiner Sicht trifft diese Beschreibung nicht ganz den
> > Kern der Wohldefiniertheit, nämlich dass es genau eine
> > Abbildung [mm]A\colon\IN^2\to\IN[/mm] gibt, die den obigen
> > Rekursions-Gleichungen genügt.
> >
> > Da du den Beweis aber ohnehin eher anschaulich und nicht
> > formal führen wirst, könntest vor dem Beweis einfach nur
> > schreiben:
> >
> > "Hierdurch wird tatsächlich eine Abbildung
> > [mm]A\colon\IN^2\to\IN[/mm] definiert:"
>
>
> Also meinst du dass wenn man folgendes sagt:
>
> "Die Ackermann-Funktion ist wohldefiniert, also für alle
> x, y [mm]\in \mathbb{N}[/mm] gibt es ein z [mm]\in \mathbb{N}[/mm] sodass
> A(x,y)=z. "
>
> zeigt man nicht dass es nur ein z [mm]\in \mathbb{N}[/mm] gibt
> sodass A(x,y)=z ? Oder habe ich es falsch verstanden?
In der Aussage
> "Die Ackermann-Funktion ist wohldefiniert, also für alle
> x, y [mm]\in \mathbb{N}[/mm] gibt es ein z [mm]\in \mathbb{N}[/mm] sodass
> A(x,y)=z. "
verstehe ich nicht, was überhaupt mit $A(x,y)$ gemeint ist, solange $A$ noch gar nicht als wohldefinierte Abbildung erkannt ist.
Streng formal wäre zu zeigen:
1. Es gibt mindestens eine Abbildung [mm] $A\colon\IN^2\to\IN$, [/mm] die den Rekursions-Gleichungen genügt.
2. Es gibt höchstens eine Abbildung [mm] $A\colon\IN^2\to\IN$, [/mm] die den Rekursions-Gleichungen genügt.
Wenn man dies gezeigt hat, hat man also nachgewiesen, dass es genau eine Abbildung [mm] $A\colon\IN^2\to\IN$ [/mm] gibt, die den Rekursions-Gleichungen genügt.
Diese eindeutig bestimmte Abbildung $A$ kann man dann als Ackermann-Funktion bezeichnen.
(Wenn man für den Nachweis von 1. "zu Fuß" eine Abbildung [mm] $A\colon\IN^2\to\IN$ [/mm] der gewünschten Art konstruieren würde, würde man sicherlich begründen müssen, dass tatsächlich eine Abbildung vorliegt, also folgendes gilt:
a) Jedem Element [mm] $(x,y)\in\IN^2$ [/mm] wird mindestens ein Element [mm] $z\in\IN$ [/mm] zugeordnet.
b) Jedem Element [mm] $(x,y)\in\IN^2$ [/mm] wird höchstens ein Element [mm] $z\in\IN$ [/mm] zugeordnet.
Dein Formulierungsversuch, was Wohldefiniertheit in diesem Fall bedeuten soll, scheint mir allenfalls den Teil 1. a) abzudecken.)
(Wenn man einen formalen Beweis der Wohldefiniertheit führen wollte, würde man aber wohl gar nicht "zu Fuß" arbeiten, sondern 1. und 2. auf doppelte Anwendung eines Satzes über rekursive Definitionen von Abbildungen der Form [mm] $f\colon\IN\to [/mm] X$ zurückführen.)
Wie gesagt, würde ich mich mit anschaulichem "plausibel-Machen" der Wohldefiniertheit begnügen und dafür keinen formalen Beweis führen.
> > > Sie hat die Eigenschaft, dass sie
> > > erstaunlich schnell wächst, wie man auf der Wertetabelle
> > > sehen kann: [mm]\dots \dots \dots \dots \dots[/mm]
> > >
> > > Sogar für kleine Werte von n und m ist der Wert den
> > > Funktion riesig. Zum Beispiel, A(4,2) hat schon 19.729
> > > Dezimalstellen!
> > (Eventuell könntest du diesen Abschnitt mündlich
> > vortragen und nur Wertetabelle und Anzahl der
> > Dezimalstellen von A(4,2) anschreiben.)
>
>
> Welchen Abschnitt meinst du genau soll ich mündlich
> vortragen? Den folgenden?
>
> "Sie hat die Eigenschaft, dass sie erstaunlich schnell
> wächst. Sogar für kleine Werte von n und m ist der Wert
> den Funktion riesig."
Ja, genau diesen Abschnitt meinte ich.
Es sollte aber kein Appell sein, den Abschnitt auf jeden Fall mündlich vorzutragen, sondern eine MÖGLICHKEIT aufzeigen, wie du weniger anschreiben und damit freier vortragen kannst.
Probiere am besten selbst aus, mit welcher Variante du dich wohler fühlst!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:58 Mi 13.05.2015 | | Autor: | mariem |
> Die Reihenfolge der beiden Beweise am Ende würde ich
> tauschen, da die Rekursivität (im Falle der Nutzung der
> Churchschen These) recht schnell geht.
Um zu zeigen dass die Ackermann-Funktion rekursiv ist macht man folgendes:
Man zeigt dass die Ackermann-Funktion intuitiv berechenbar ist und aus der Church-Turing These folgt dass die Funktion auch rekursiv ist.
Richtig?
Zeigt man folgenderweise dass die Ackermann-Funktion intuitiv berechenbar ist?
https://vorhilfe.de/read?i=1058329
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:51 Fr 15.05.2015 | | Autor: | tobit09 |
> Um zu zeigen dass die Ackermann-Funktion rekursiv ist macht
> man folgendes:
>
> Man zeigt dass die Ackermann-Funktion intuitiv berechenbar
> ist und aus der Church-Turing These folgt dass die Funktion
> auch rekursiv ist.
>
> Richtig?
Ja.
(Wobei das natürlich streng genommen kein Beweis ist, da der Begriff der intuitiven Berechenbarkeit nicht richtig definiert ist und somit die Church-Turing-These auch nicht beweisbar ist.)
> Zeigt man folgenderweise dass die Ackermann-Funktion
> intuitiv berechenbar ist?
>
> https://vorhilfe.de/read?i=1058329
Dazu schreibe ich dort gleich eine Antwort.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 05:14 So 17.05.2015 | | Autor: | mariem |
> > Also soll der Vortrag folgenderweise aussehen?
> > -Historische Einordnung/Entstehungsgeschichte
> > -Definition der Ackermann-Funktion
> > -Beispiel für die Auswertung an kleinen Werten
> > -Wertetabelle, um das schnelle Wachstum zu verdeutlichen
> > -Beweis dass die Ackermann-Funktion nicht primitiv rekursiv
> > ist
> > -Beweis dass die Ackermann-Funktion
> > rekursiv/TURING-berechenbar ist
Ich habe mit den Lehrer gesprochen und er hat mit gesagt dass ich den folgenden Punkt:
-Beweis dass die Ackermann-Funktion rekursiv/TURING-berechenbar ist
weglassen kann. Ich soll einfach ein Beispiel wie man ein Wert der Funktion berechnet, geben.
Außerdem hat er gesagt dass ich am Ende des Vortrages zum Publikum Fragen stellen sollte. Was für Fragen kann man stellen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:54 So 17.05.2015 | | Autor: | tobit09 |
> Außerdem hat er gesagt dass ich am Ende des Vortrages zum
> Publikum Fragen stellen sollte. Was für Fragen kann man
> stellen?
Tut mir leid, da habe ich auch keine Vorstellung. Fragen an die Zuhörer bei einem Seminarvortrag habe ich noch nicht erlebt...
Ich würde den Lehrer nochmal fragen, an was für Fragen er denkt.
|
|
|
|
