www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Komplexität & Berechenbarkeit" - Ackermann-Funktion
Ackermann-Funktion < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Ackermann-Funktion: Umfrage (beendet)
Status: (Umfrage) Beendete Umfrage Status 
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?

        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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“."


[]Quelle


Viele Grüße
Josef

Bezug
        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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  


Bezug
                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 00:20 Mo 13.04.2015
Autor: mariem


> > -Definition der Ackermann-Funktion

Was könnte ich bei der Definition schreiben?

Ich habe folgendes in Wikipedia gefunden: []http://de.wikipedia.org/wiki/Ackermannfunktion#Definition_und_Varianten

Kann ich davon etwas schreiben?

Sage ich welche die origialversion von Ackermann ist und welche die Version von Peter ist?





Bezug
                                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
Datum: 04:44 Mo 13.04.2015
Autor: Josef

Hallo mariem,

>
> Was könnte ich bei der Definition schreiben?

"Ackermann selbst definierte die Funktion auf recht umständliche Weise, gab aber kurz darauf die folgende äquivalente Definition an."

[]Ackermann-Definition


>
> Ich habe folgendes in Wikipedia gefunden:
> []http://de.wikipedia.org/wiki/Ackermannfunktion#Definition_und_Varianten
>
> Kann ich davon etwas schreiben?
>

[ok]


Siehe auch []Die Ackermann-Funktion(en) und ihre Inverse(n)


> Sage ich welche die origialversion von Ackermann ist und
> welche die Version von Peter ist?


[ok]






Siehe auch: []hier und []hier



Viele Grüße
Josef

  


Bezug
                                                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?


Bezug
                                                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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]




> 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!


[ok]



Die übrigen Angaben habe ich nicht geprüft.



Viele Grüße
Josef



Bezug
                                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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

Bezug
        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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


Bezug
        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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! [ok]


> 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.

Bezug
                                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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...

Bezug
                                                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                                
Bezug
Ackermann-Funktion: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 00:21 Mo 13.04.2015
Autor: mariem


> > -Definition der Ackermann-Funktion

Was könnte ich bei der Definition schreiben?

Ich habe folgendes in Wikipedia gefunden: []http://de.wikipedia.org/wiki/Ackermannfunktion#Definition_und_Varianten

Kann ich davon etwas schreiben?

Sage ich welche die origialversion von Ackermann ist und welche die Version von Peter ist?


Bezug
                                                        
Bezug
Ackermann-Funktion: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 01:20 Sa 18.04.2015
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
                                                        
Bezug
Ackermann-Funktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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]

Bezug
                                                                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                                                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                                                                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                                                                                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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]

[ok]


> 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]

[ok]


> 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!

[ok] (Eventuell könntest du diesen Abschnitt mündlich vortragen und nur Wertetabelle und Anzahl der Dezimalstellen von A(4,2) anschreiben.)

Bezug
                                                                                                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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!
>  [ok] (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."

Bezug
                                                                                                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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!
>  >  [ok] (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!

Bezug
                                                
Bezug
Ackermann-Funktion: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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



Bezug
                                                        
Bezug
Ackermann-Funktion: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                                
Bezug
Ackermann-Funktion: Frage (reagiert)
Status: (Frage) reagiert/warte auf Reaktion Status 
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?

Bezug
                                                        
Bezug
Ackermann-Funktion: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de