[Playlisten] [Impressum und Datenschutzerklärung]

Ackermann-Funktion, primitiv rekursive Funktionen, Hyperoperationen

CC-BY-NC-SA 3.0

Nachtmodus Pausen an Schnitten Tempo: 0,5 0,7 1,0 1,3 1,5

Anklickbares Transkript:

die Ackermann Funktion – gefunden von Herrn Ackermann neunzehn hundert achtundzwanzig – dies heute vor allem bekannt wegen des schnellen Wachstums – ein Beispiel für eine Funktion die extrem – schnell wächst – schneller als – alle Kommentarfunktionen – schneller als Fakultät – muss aber dazu sagen das – noch viel schneller wachsende Funktion gefunden worden sind – die – wie sie Biberfunktion – ist eine davon – gucken will – der – Grund warum – man diese Funktion gebaut hat ist – nicht – besonders schnell wachsen Funktion zu finden sondern eine Funktion – an der man studieren kann was sich berechnen lässt mit einem Computer – was ich nicht berechnen lässt – die Theorie der Berechenbarkeit – zu der Zeit war noch nicht klar – wie man das korrekt normalisieren muss – nicht vergessen was zum schnellen Wachstum der seitlich am Ende was – zu dieser Berechenbarkeit – die – es geht um die sogenannten primitiv – rekursiven Funktion – Komma – vorsichtiges mal an – wie kann ich eine Funktion – durch Rekursion – definieren – das ist – eine wesentliche – Technik – Komma – Definition – einer Funktion – durch Rekursion – erst ?? zum warm werden ein Beispiel – die vier hundert ?? Folge – Punkt – Folge heißt ich kann die einzelnen Werte durch nummerieren – in der Informatikbesetzung – mit null acht – fünf sechs – acht null und so weiter – so der Nolte Wert in der Fibel deutsche Folge soll – eins sein – der erste Wert in der Folge soll auch ein Zeit das Licht Komma fest dass ich sage das an null – Element eins sein soll und ich sage das A eins das erste Element – auch ein sein soll – und nun kommt die wesentliche Regel – jeder Nachfolger – soll die Summe seiner beiden Vorgänger sei in den nächsten hier kriege ich in den ich eins und eins addiere ich zwei Stellen – den Essen kriege ich in dem ich die zwei – und die – eins addiere hier muss drei stehen – den kriege ich in dem – die drei und die zwei Tiere da musste fünf stehen drei und fünf zusammen hier muss nachstehend fünf hundert acht dreizehn – dreizehn einundzwanzig – vierunddreißig – fünfundfünfzig – und so weiter – das ist die Rekursion – ?? – ich kriege – den Eintrag einer Stelle N plus zwei sehr in ist – ich den Eintrag erstellen plus zwei – vorschreiben in – ein – indem ich – den Eintrag der vornehme – HN plus eins – und dazu addiere – den Eintrag – noch ein zweiter links ein – das für alle natürlichen Zahlen in – null aufwärts – das ist die – Rekursion Formel – für die – monarchische Reihe – ich – verwende – um den Funktionswert festzulegen – ?? erstellen plus zwei – die Funktionswerte – an den Stellen der vor – der Partyrekursion – aus – Ackermann – Funktion macht man es nicht unähnlich – aber – auf einem ganz anderen Niveau – die – Gammafunktion – muss dazu sagen ich zeige die in der heutigen – Fassung – der gute Herr Ackermann hatte sich eine etwas komplizierte Variante ausgedacht heute ist das bisschen schlichter geworden nach dem paar Leute aufgeräumt haben – das – ganze Ding klebt – in zwei Dimensionen – ich – mal – ärgerlicherweise – falsch rum benenne – x-Achse zeigt nach unten Y – Achse zeigt nach rechts – an – diesem Wissen ungemütlich – auf den ersten Blick – führt aber dazu dass die Formel nachher so aussehen – wie man sie dann – üblicherweise – im Lehrbuch findet – auf beiden Achsen wieder die natürlichen Zahlen null aufwärts – und – die Ackermann Funktion für dieses Feld – zu jedem Party im geordneten Paar von natürlichen Zahlen – null aufwärts – hat die Ackermann Funktion dann – einen Wert – müssen irgendwie – putzig anfangen mit irgendwelchen – anfangs werden analog zum – Che – Ackermann macht ist – an für die erste Zeile – mit den natürlichen Zahlen ab – eins aufwärts – und so weiter – das heißt in der Spalte mit der Nummer Y – steht hier – in der Notenzeile – Y plus eins – und so weiter – das ist die – erste Regel diesbezüglich – also in der Zeile mit der Nummer null – Spalte mit der Nummer Y steht Y plus eins – für alle Y – null zwei – drei und so weiter – nun sicher noch Gedanken um diese äußerste Spalte machen – die Spalte mit der Nummer null – kopiert man hin was in der Zeile davor in der Spalte mit der Nummer eins gestand diese zwei wird hier – in kopiert – was auch immer hier gleichstehen wird mit dahin kopiert werden und so weiter – das ist die zweite Regel – wenn ich in der Spalte – mit der Nummer null bin in irgendeiner Zeile – soll da stehen – was in der Zeit davor steht in der Spalte mit der Nummer eins – das geht natürlich nur – mit den Zahlen eins aufwärts – nicht mit der – Zeile mit der Nummer null ich kann nicht vor die Zeile mit der Nummer null Coke – so – bis dahin ist das billig – jetzt kommt die Rekursionsvorschrift – dass es Ähnlichkeiten über ein Telefonat schien – anfangs billig und dann kommt die – komplizierte Rekursionsvorschrift – Komma – die Rekursionsvorschrift – ist nun – folgendes – den zu fördern – ich mir an was davor steht in der Zeile – versteht zwei – ?? gucke ich – in der Zeit davor – in der Spalte mit der Nummer zwei nach und finde die drei – das kompliziert ?? Hornissen – drei – die nächsten fünf – ich gucke mir an was davor steht in der selben – Zeile – in drei – dagegen eine Zeile nach oben und gucken was da in der Spalte mit der Nummer drei steht – vier – Tage das weitergehen wird fünf sechs sieben acht neun zehn Klammer zu Fuß überlegen Beistrich wann das Gitter in einer Schritten startet mit zwei steht also in der Spalte mit der Nummer Y die Zahl – Y plus zwei – ist eine Seite noch Zustand – in der Zeile mit der Nummer zwei etwas spannender – und es ?? die zweite Regel – wo ich jetzt den – Kopieren – Zuges für den nächsten – gucken uns diese drei Armen gehen in der – Zeit davor – zur Spalte mit der Nummer drei und finden die fünf Damensattel – fünf – um den zu bestimmen – gehen wir eins nach links versteht die fünf in der Zeile davor – steht bei der fünf die sieben – hundert sieben rein – ernannt wie es weitergeht – Komma nicht mit machen neun – elf – dreizehn – fünfzehn – siebzehn – neunzehn – und so weiter – das geht in Zweierschritten – allgemein steht also sowas wie zweimal Y – das Kind mit drei Los – drei – und so weiter – gemessen – mal abstrakt hinschreiben was ist das für eine Regel – um die Ackermann Funktion an der Stelle X Y zu bestimmen – ?? definiert gleich – gucke ich mir an – was davor – steht – selbe – Zeile – eine Spalte davor – gucke dann unter dieser Nummer das hier als – Nummer der Spalte genommen – in der Zeile davor nach – der Zeile davor – guck ich unter dieser Nummer sowie das Haus – für alle X Y die nicht – links liegen oder oben liegen die beiden Ränder ausgenommen – das ist die Rekursionsvorschrift – für die Ackermann Funktion – das sieht wirklich haarsträubend aus dem ersten Blick – es gibt – eine andere Art sich das – vorzustellen – was da passiert – diese drei – stand daher – für diese fünf – bei der drei nach gucke nach was jetzt – in der Spalte Nummer drei gestanden hat das es die fünf gewesen – um diese sieben zu kriegen – gucke ich nach – was – in der Spalte Nummer fünf gestanden hat – und so weiter – was passiert ist also folgendes – dass diese Folgezeile – aus Lautelementen – der Zeile davor besteht – nun wird das ganze ?? mit Siebenmeilenstiefeln – durchlaufen – ?? mit dem zweiten Hunter steht in drei – und Punkt was da in der Spalte Nummer drei steht der steht die fünf hundert gucke ich was in der Spalte Nummer fünf steht die sieben – ?? sieben D neun und so weiter – das ist hier die nächste Zeile drei fünf sieben neun drei fünf sieben neun – Ziffer bereit für die Teile Nummer drei – nach – der zweiten Regel kopiere ich die fünf er vornherein – und jetzt muss ich nachgucken – was – in der Spalte Nummer fünf – steht – die dreizehn – für den ?? muss ich nachgucken müssen ersparte Nummer dreizehn steht – aber gar nicht mehr aber ganz ausrechnen ?? dreizehn steht – zweimal dreizehntes drei – hier muss neununddreißig – ?? – für den hier – muss ich gucken was in der Spalte neununddreißig – steht – zweimal neununddreißig – plus drei – einundachtzig – stehen – und so weiter – das geht also schon deutlich zügiger – dafür können uns jetzt meine allgemeine Form überlegen – ist nicht mehr ganz offensichtlich – ist was hier steht etwas anders zu schreiben – zweimal – zum Schluss drei – minus – drei – mal – prüfen – Beistrich verdoppeln und Reiter zu addieren – ?? verdoppelt und zweimal drei sechs dazu addiert – ?? drei abgezogen – dasselbe – lustigerweise sie dann leichter zu verstehen – was gleich passiert – ich gehe jetzt ja – in Siebenmeilenstiefeln – durch die Zeile Nummer zwei fange an mit fünf – und gucke danach in der Spalte Nummer fünfter steht die dreizehn – dann muss ich zur – Sparte dreizehn und so weiter und so weiter das geht ziemlich – flott – was ich als eigentlich immer mache – ist immer wieder zweimal – plus drei ausrechnen – mit der fünf Staaten – zweimal – fünf plus drei die dreizehn – dann mit der dreizehn zweimal dreizehntes – drei GP neununddreißig – und so weiter – fünf dreizehn neunundneunzig einundachtzig das passiert – ?? ich nehme die Zahl von setzte sie immer wieder – in zwei Markus drei ein – Serviceteil – mit fünf Ausgängen dreizehn – plus drei mit dreizehn Cents und dreißig und so weiter – und so weiter – Klammer auf – in – der Zeile Nummer drei – Spaltennummer – null da steht Fünftel der ?? kopiert aus der Zeit vor – ?? – für die nächsten – rechne ich – zwei – mal – was versteht – mich fünf – Teile zu – minus drei – ?? funktioniert ja – das in der Zeit davor – zweimal plus drei – ?? dasselbe zwei – mal das Ding plus drei – minus – und dann den nächsten – komme ich als zweimal – das was davor steht plus drei – minus drei – bietet sich das ?? – zweimal – fünf plus drei – minus drei – und den nächsten ?? – bekomme ich als zwei mal – was davor steht plus drei – minus drei – steht hier vor zwei mal – zwei mal fünf plus drei – drei – plus drei minus drei – dieses ganze eingesetzt – wird sieht man – warum – die etwas andere Schreibweise raffiniert ist das ich nicht schreibe zweimal plus drei sondern zweimal – Klammer auf Pluszeichen – drei abziehen – Beistrich diese drei Diesel ?? weggeben – das sieht man jetzt minus drei Pluszeichen das ergibt sich Weg minus zwei Pluszeichen – Zweck – Wasser zum Schluss steht es zweimal zwei mal zwei – mal fünf plus drei – noch minus drei – das geht jetzt natürlich so weiter – dieses – Aufheben von minus drei plus drei – geht ständig so weiter – Beistrich einfach hiervon immer noch ?? Faktor zwei der zum Endeffekt – dieses reiche vorne – selten – direkt diese Faktoren – zwei – ein – bisschen – hübscher haben – also in der rasch – bald wieder Nummer drei steht zweimal – zwei mal zwei zwei hoch drei – mal acht – minus drei – der Spalte mit der Nummer vier ?? stehen zwei ?? vier mal acht minus drei – und so weiter – das ist die allgemeine Formel – ?? zwei – Y – Spalte mit den hundert minus drei – sieht – hier aber modifizieren – müssen wir schon potenzieren – in der Spalte mit der Nummer drei – aber es kann noch schlimmer – für jede Zeile – eins schlimmer – die nächstenzeilig – kopiere die dreizehn vorne hin – und – jetzt muss ich – Ende Ersatzteile – an der Stelle dreizehn – nachgucken – toll achtmal zwei hoch dreizehn minus drei – ?? oftmals frei hoch dreizehn – minus drei – achtzehn zwei hoch drei – zwei ?? Klammer zu – dreizehnten zweiter sechzehn – macht die drei – nicht viel kaputt – ?? sechzehn ungefähr fünfundsechzig tausend – hat sie sind wir schon bei – vierundsechzig tausend ?? urplötzlich – davor sieht es alles so harmlos aus fünf dreizehn neunundneunzig einundachtzig – dreizehn von sechzig tausend ?? und der Rest wird – monströs – gar nicht ins unseres für das und hier natürlich auch wieder die vierundsechzig tausend – durch die zweite Regel – und es geht alles ganz fürchterlich monströs weiter – an dieser Stelle explodiert die – Ackermann Funktion dann offensichtlich – auch für diese Zeit hier kann man sich noch überlegen – wieder die allgemeine Rechenvorschrift – sein muss – die wir bisher kompliziert – in der Spalte mit der Nummer Y was wir hier stehen in der Spalte mit der Nummer Y – Klammer zu der Zahl – am – Anfang – der Spalte null – vier ?? zweite null – steht die dreizehn ?? gesehen – daneben rechts daneben – zweite Nummer eins – steht zwei hoch dreizehn plus drei – minus drei ?? auch gesehen – Punkt jetzt wird das – ständig wieder ineinander eingesetzt – in der Spalte davor – nur auf höherem Niveau jetzt – diese dreizehn – setzt sich hier für das – Y ein – was rauskommt – setzt sich wieder für das ein und so weiter – und so weiter – kann sich auch für die Zeile mit der Nummer vier überlegen wie das denn allgemein aussieht – ziemlich heftig – dazu muss man den ?? wieder etwas umschreiben – vor harten Bedingungen geschrieben uns raffiniert zu machen schreibe ich den etwas – acht mal zwei ?? Y – acht SR zwei hoch drei – zwei hoch drei – mal zwei hoch Y – ist zwei hundert plus drei – dreizehn – hier – steht zwei Y plus drei minus drei – davon sind gleich wieder der Trick – bei minus drei – wird sich weggeben – jetzt aber mal zwei ?? Y – ?? Y – zwei drei – acht mal – diese – Funktion ständig wieder verschachtelt werden müssen – ich setze – die dreizehn ein – dreizehn Pluszeichen – zweiunddreißig – plus drei minus drei gibt ein wichtiges Resultat und für den nächsten muss ich das wieder – einsetzen – sind – Fenster – also in der – Zeile mit der Nummer vier und der Notenspalte – fange ich an mit der dreizehn – der nächste die – alte Nummer eins – ist – dann zwei – Hochwasservorstand – dreizehn plus drei – minus drei – Zimmer – Y plus drei zwei hochgenommen – minus drei das allgemeine Formel – den ausgerechnet um fünfundsechzig tausend – der nächste – dann will ich wieder zwei hoch soundsoviel – plus drei – minus drei – zwar mit dem Wasser um stets zwei hoch dreizehn plus drei minus drei – es mir schon wieder den Trick minus drei plus drei mit sich gleich weg ähm – der nächste – vierte Zeile – versandte Zeile mit der Nummer vier die Spalte mit der Nummer drei – ich bilde zwei Hochschluss – drei – minus drei – alle Meister steht also zwei hoch zwei – hoch dreizehntes – drei minus drei plus drei – minus drei – ?? – sprechen wieder weg minus drei Pluszeichen – sich weg minus drei Pluszeichen zig Weg – dreizehn Pluszeichen – sechzehn hier steht also zwei hoch zwei – hoch zwei – hochsechzehn – minus drei – sechzehn Komma noch bisschen raffinierter schreiben – sechzehn ist zwei hoch vier zwei hoch – vier aber vier ?? zwei hoch zwei – dann bin ich also – zweiundzwanzigster – zweiter zwei hoch zwei hoch zwei hoch zwei hoch zwei hoch zwei – minus drei – bei diesen Potenzstörungen – des immer gemeint – oben anfangen – zwei hoch zwei – und dann zwei hoch – zwei hoch zwei – dann zwei hoch – zwei ?? – zwei – das wird jetzt natürlich so weitergehen wird es schon – ins – zweite – bestehenden Seite miteinander stehen – mit sechzehn suchen vorne – stehen hier also insgesamt – Y – plus drei – zweien übereinander – dass wir die allgemeine Formel werden – die Stapler als Potenzturm – Y plus drei zweiundneunzig – drei ab – allgemein – zwei ?? hoch zwei – hoch zwei – Y dreimal – und siehe drei ab – das wächst monströs – das ist die – Zeile mit der Nummer vier bezahle mit der Nummer fünf – sind dann potentielle – von Potenztürmen von Potenzstörungen – ganz fürchterlich – an – die dass die – Ackermann Funktion – die – die Rechenoperationen – zu verallgemeinern – scheint hier wird um Witz addiert – hier wird modifiziert – hiermit potenziert – hier habe ich Potenztürme – das ist verwandt mit den Proportionen – in der ursprünglichen – Definition – von Ackermann war es auch tatsächlich die Überoperation – verwandt damit – der Gedanke dahinter ist folgender – drei mal fünf – ist das eigentlich drei plus drei plus drei – drei – drei – fünf – drei – Bindestrich drei Hof fünf – ist das dreimal drei mal drei mal drei – mal drei verschwanden – die drei – kann man das weitertreiben – aus dem mal – des hoch fünf kann ich das weitertreiben in der Tat das kann ich weiter treiben – in beide Richtungen ich kann sogar noch eins zurück – was es drei plus fünf – drei plus drei plus eins plus eins – plus eins plus eins – plus eins – fünfmal die eins addiert fünfmal die Operation ausgeführt – eins zu addieren ?? sogar noch einen Schritt zurück kümmern will – Komma vor einigen geht es jetzt – beliebig weit nach oben – bei den über Operation – an – der übermäßigen – Schreibweise – verschiedene Schreibweisen – muss – der Informatikpapst – und – Autor von Tisch – hat sich folgende Schreibweise ausgedacht mit dem Pfeil nach oben – für – die Potenz der Thermalpotenz – drei hoch fünf – und es versuchen eine Überpotenz – zu bilden drei Doppelpfeil – fünf was müsst ihr als nächstes stehen – Herr – bei der Haarpotenz – schreibe ich so viele Faktoren miteinander wie mit S fünf angeht jetzt mach ich dasselbe hier – am – über Potenz der Traktion hast du offiziell – so – weit das bei der – Integration – mit der Potenz ich schreibe – drei hoch drei hoch drei hoch drei fünf Faktoren also gemeint ist – drei hoch drei ausrechnen dann drei hoch – ausrechnen drei hoch – drei hoch ?? aus ?? plus drei hoch das ganze ausrechnen – fünfmal die drei – in sein Potenzturm – benannte geschrieben das soll sein drei – Generation fünf – das nicht was dann folgt – und was dann folgt – Beistrich jetzt – aber fortsetzen – soll sein – dieses dann mehrfach ausführen – drei – Filtration – von drei Integration – von Integration – von – drei – der Tradition – von drei – Klammer zu – ja das hier fünfmal die drei miteinander steht – aber mit dieser Operation – das wird fürchterlich – der hinten – steht ja drei hoch drei hoch drei drei Faktoren drei – übereinander gesetzt – dieses hier – bedeutet jetzt das ich drei hoch drei – und so weiter und so weiter bilde – ein Potenzturm – mit soundsoviel Potenzen nämlich drei hoch drei hoch drei Potenzen ?? übereinander – dieses – ist jetzt ein Potenztour – mit so viel Potenzen übereinander – und so weiter schreiben ihm Hindus – fürchterlich zu schreiben – ist in einem selbst damit Potenzen und Potenzen von Potenzen potentiellen – gehen irgendwann – die Symbole aus was ganz vernünftig zu schreiben – die – Ackermann Funktion – macht eigentlich auch im modernen Zuschnitt – ziemlich genau dieses hier – bin ?? kleinen Körnchen Salz – an ?? sehen hier die – Potenz – steht in der Zeile – nach – die Potenz steht in der Zeile mit der Nummer drei – und dann die Detonation – in der Zeile mit der Nummer vier – dieses – hier das ist die Zeile mit der Nummer vier in der Ackermann Funktion – das hier wird dann offensichtlich – die Zeile mit der Nummer fünf werden – in der Argumentation – und so weiter – und so weiter es wird rapide – schlimmer – mit dem Wachstum – das – Wachstum ist aber eigentlich gar nicht – der Grund weshalb der gute Herr kann man sich das ausgedacht hat – sich das ausgedacht hat ist – um zu studieren was eigentlich berechenbar – ist was kann ein Computer – nicht – selber – merkt man das Ackermann Funktion berechenbar ist im üblichen Sinne – kann ein Computer so programmieren – ?? – mit einem einzigen festen Programm – des Demir – Ackermann von dreizehn zwoundvierzig – oder von tausend – ?? zwei tausend ?? Wasser Komma aus theoretischen – kann ein einziges Programm schreiben – die mich dann Koordinaten gebe – und dieses eine – einzige feste Programm wird mehr ausrechnen was da steht – dass wir zwar monströs lange dauern und – extrem viel Speicherplatz benötigen aber rein theoretisch ist das möglich sein Programm zu schreiben – ein festes Programm – das nach Eingabe von X und Y – losgeht – Ewigkeiten rechnet ich Ewigkeiten rechnet sehr lange rechnet aber eben nicht ewig rechnen sehr lange rechneten dann irgendwann mit einem Resultat zurück Punkt ein einziges festes Programm – das wir offensichtlich nie – vorgeführt wie die Tabelle hierzu für – an dem Sinn ist die Ackermann Funktion berechenbar – aber – sie ist nicht – das was Ackermann Seiten die große Frage – ist aber nicht eine primitiv – rekursive Funktion – das hatten seinerzeit die Leute versucht – als Modell für berechenbare – Funktion zu verwenden – die sogenannten primitiv rekursiven Funktion – Komma damit ihn gezeigt Punkt – das – ?? leider nicht in – die Funktion die wir wirklich ausrechnen können – das sind mehr als die primitiv rekursiven – Funktion – was – in primitiv rekursive Funktion – hinterlässt ?? Funktionen – die Double von natürlichen Zahlen ab null aufwärts entgegennehmen – und daraus wieder natürliche Zahlen ab null aufwärts machen jede Funktion dann – feste Größe ?? Tube eine bis vier Variablen haben – acht Variablen haben – einfach nur ein – und dann sagt man – wie man diese Funktion den finden kann erstens sollen alle konstanten Funktionen – primitiv rekursiv sein – Komma eine Funktion – die ganze Zeit zwoundvierzig ist egal was ich einsetze die soll – primitiv rekursiv sein dafür den Programm schreiben klettern zwoundvierzig – ?? auch gerne eine besondere Funktion dabei nämlich der Nachfolger – die Funktion die eins addiert – auf Ixus eins auch die soll dabei sein – dann sollen die sogenannten Projektionen – dabei sei zum Beispiel eine Funktion – die das – geordnete Tripolis Y Z nimmt und auf Z abbildet für alle X Y Z – eine Projektion – alle von der Sorte sollen dabei sein – kann somit auch verketten können zum Beispiel – nicht zum – Quint Double habe – den Trubel und bildet das ab auf – F ein primitiv rekursive Funktion X Y – G – noch eine relativ rekursive Funktion – so etwas die Verkettung zweier primitiv rekursive Funktionen auf diese Weise oder entsprechende andere weisen – auch das soll wieder primitiv rekursiv sein – Komposition – primitiv rekursive Funktion hundert ?? für – die – primitiv – rekursiv – und man überlegt sich was kann man diesen Funktionen jetzt alles antun und kanntet was was – berechenbar ist – das wichtigste ist – die primitive Rekursion – ich baue eine neue Funktion in dem ich sage – das erste Argument null ist egal was das zweite Argument ist soll diese Funktion sein eine gegebene – primitiv rekursive Funktion – die – die Rekursion – wenn ich – den nächsten wissen will ?? Express eins die Funktion für den nächsten bei meinem Y – soll das sein ?? – andere rekursive Funktionen – von diesem Mix – von Y und der vorherige – Wert – Exits – einer Funktion – X Y – das ist die – Rekursion – auf der Zunge zergehen lassen ?? – ich gewarnt was den Startwert vor für jedes Y – mit einer primitiv rekursiven Funktion gehen – rekursiv – und hier – habe ich nie Rekursion – die Funktion – für das nächste X – einundzwanzig – bauen will für das nächste X soll sein – primitiv rekursiven Funktion H immer dieselbe – Funktion haben – zu ?? – an den links – an dem Y – und – vom alten Wert – enthalten wertvolle Funktion eingetragen – das ziemlich allgemeine Vorschrift für rekursive Funktionen – lustigerweise – umfasst das eben nicht die Ackermann Funktion – zeigen werde – müssen auf ?? zu schreiben und so weiter – wenn ich meine Y steht sondern bin hier zehn Y sind einander stehen ?? zehn Emsland – und so weiter und so weiter das wird ein ziemlich hässlicher Mann das im Detail – sauber ausformuliert – aber das ist der wesentliche Gedanke – die allgemeine Konstruktionsrekursion – das alles erlaubt sei mit dem primitiv rekursiven Funktion – ?? die üblichen Verdächtigen dabei sein – möchte ?? komponieren können ?? verketten können – Deutsch – und ich möchte – aus den – primitiv rekursiven Funktionen – auch wieder per Primitivrekursion – neue Funktion zusammenbauen können – alle – Funktionen die ich so kriegen kann das sollen die primitiv rekursiven Funktion sein – kann relativ einfach seine für sich relativ einfach zeigen dass Additionsmodifikationen – Konsorten jede für sich ?? mit der primitiven Rekursion sofort – machbar ist als die üblichen Verdächtigen sind – primitiv rekursive – Funktion – des Acker überhaupt erst der Verdacht auf das man damit schon alles berechenbarer – hat – Ackermann hat ebenso abstruse Funktionen gebaut wie man damit nicht kriegen kann ?? trotzdem berechnen kann – um das zu sehen macht man folgendes anzeigt dass die Ackermann – Funktion – schneller wächst – als alle primitiv rekursiven Funktion – dann kann es ja keine von denen sein – das – wäre – zentral zu zeigen – was technischer wie formuliere ich das – zeige dazu schreibe ich mal – wenn ich eine – primitiv rekursive Funktion von – N Variablen habe – die primitiv – rekursiv – dann – gibt es das nicht ?? bemerkt dann gibt es – ein festes und – feste Zahl – die gehört fest zu dieser Funktion – F – so – das diese Funktion – aber sicher ?? Einsätze – immer kleiner ist Ackermann von – diesem – an das Maximum – von ?? zahle ich dahin eingesetzt habe – egal was ich einsetze – merkt – fest dieses Ruß eine feste Zahl – das – ist die Zeile – in der – Ackermann Funktion – das ist die Behauptung hier – jede primitiv rekursive Funktion – wird durch irgendeine – Zeile – der Ackermann Funktion gedeckt gilt – das kann die tausendste seiner Definition – aber jede primitiv rekursive Funktion ist nicht irgend eine Zeile – entwickelt – dass die Behauptung – dann ist klar wie das funktioniert – im Sternchen nicht zeigen kann – das Ackermann – also keine primitiv rekursive Funktion ist – denn – das haben Sie sofort das kann ich mit Ackermann Funktion selbst nicht machen – die – Ackermann Funktion ist er nicht durch eine Zeile von sich gewickelt die Folgezahlen – wachsen ja noch viel stärker als die Zahlen der Vorgang keine Chance – also folgt – aus diesem hier automatisch – das was ich zeigen will dass die Ackermann Funktion schneller wächst als die rekursive Funktion – die Ackermann Funktion kann keine primitiv rekursive Funktion sein – es ist also nur noch – das hier zu zeigen – das andere – primitiv rekursiven Funktionen dieser Eigenschaft haben dass sie durch eine Zeile der Ackermann Funktion – gedeckt sind Beistrich ist als – Spalte das Maximum von einem einsetze – was in der Funktion vorkommt – wie – beweist man das – diese Eigenschaft – dann – diese Eigenschaft ist klar das es gedeckt ist für durch Ackermann – diese Eigenschaft ist klar für die – Basisfunktionen – für die Konzernfunktion – ist offensichtlich – hier weit raus kann man – für die Nachfolgefunktion – ist auch klar sofort aus den ersten Zeilen des Ackermann schneller wachsen muss – mir also nur noch Gedanken darüber machen – ob denn beim – Kombinieren – von den Basisfunktionen – etwas kaputt gehen kann – eine Projektion – nicht kaputt gehen – bei den verkehrten hier – fünf Minuten nach und stellt auch fest dass das wohl in Ordnung ist – der Haltepunkt es wenn ich zwei primitiv rekursive Funktion habe die Getränke sind durch Ackermann – kann ich damit – primitive Rekursion machen und hat wieder eine Funktion die gedeckt ist durch ?? Komma – das ist der Kernpunkt des Beweises – das wäre zu zeigen – dass – sich dieser Eigenschaft – primitive – Rekursion vererbt – also – ich baue eine Funktion F – mit primitive Rekursionsstaat – und – echte Rekursion für das nächste X – ist meine Funktion – eine vorgegebene Funktion von X von Y von – X sondern die Funktion mit dem extra vor – Y – ihr einfaches aber auch wieder nur mit einem einzigen Y müsse sich durch definieren mit – ganz viel Substanz ineinander das umständliche Schreiben und Idee ist – dieselbe – also angenommen – das G und H Funktionen – sind die diese Eigenschaft haben dass sie durch Ackermann gedeckt sind – möchte ich zeigen dass auch die Funktion F dieser Eigenschaft hat – die – beiden erfüllen – diese Deckelungseigenschaft – das heißt – dieses gehen – ist kleiner gleich – eine bestimmte – Zeile von H – ?? Y – also diese so fest – und – dieses Haar – selbst – ist kleiner gleich ?? kann man von einem – an einer anderen Zeile – derselben – auf jeden Fall ein festes Foul hier – vom Maximum – dieser – drei Argumente – X Y Z – für alle – Punkt also angenommen diese beiden sind durch Ackermann in der ?? – möchte ich jetzt zeigen dass die daraus – mit primitiver – Rekursion gebaute Funktion auch gedeckt ist ?? mit dem Song das war der – hier – Ackermann hatte nur zwei – Variablen die einsetzen kann wenn ich hier achtundneunzig haben sich in Word zwei kommende Trick ist das Maximum zu bilden wär's sicher fest – in der sonstigen Zeile – ist Ackermann größer gleich – und jährlich das Maximum von allen – Programmen ?? Funktion – okay – das ist mein Ausgangspunkt – mache eine primitive Rekursion mit diesem gehen diesem Haar möchte zeigen dass die Funktion ?? rauskommt – auch wieder – durch Ackermann gedeckt ist – ?? – kein großes Wunder – wie weit Ackermann gehen muss – ich gehe mal einfach – immer das Maximum – von der Nummer der Zeile durch die einige Deckel ist und der neue Zeile durch die andere Decke diesen eins dazu – das schon ein guter Kandidat – weiß nicht hundertprozentig das sollte schon ein guter Kandidat – für eine Zeile die die – Fusion ersticken sollte – möchten – ?? erfolgen – nicht ganz das was ich – brauche – ?? wie ich möchte folgendes sei zeigen dass die Funktion die ich baue – durch Ackermannzeile – mit einem ?? wie X plus Y – gedeckt ist – ?? kleines X plus Substanzen – Zwischenschritt – Bauernhaus – mit einem Maximum – das möchte ich zeigen – und das geht ganz schon mäßig mit Induktion – vollständige Induktion – trägt – mir das erst mal an wenn X gleich null ist ?? von X gleichen – null – und irgendein Y – ein Atoll – von ist gleich null – ist meine Funktion ja mit EG gebaut und je ist sogar – sogar durch dieses – die Unterzeile – von Ackermann beschränkt – ?? das gibt's geschenkt das es garantiert dann auch eine als Vergleich der vierten Zeile – von Ackermann für alle Y – geschenkte Induktion Anfang – Induktionsschritt – des bisschen – raffinierter – ich nehme also an – das meine Funktion – für ein gegebenes X – auf diese Weise gedeckt ist – für alle Y und ein bestimmtes X – und versuche jetzt nachzuweisen – dass für X plus eins – das Geld von Express eins kleines K ?? A von B plus eins – plus Y das wäre der Induktionsschritt – also was ist denn X plus eins dann – die Funktionsstelle – X plus eins – nach Definition – nehme ich mein Haar – stelle X Y – von X – Y – Y das ist einfach – die Definition der primitiven Rekursion – so – und nun entspannt – Haar soll durch Ackermann – beschränkt sein – und zwar mit – der – Zeilennummer – V – ist durch die Zeilennummer Frau – von Ackermann beschränkt – steht hinten eben das Maximum – von – X Y – und der Funktion – X Y aber jetzt habe ich schon dass die Funktionsnutzung – Annahme hier – an der Stelle X – beschränkt ist ?? schreibe ich gleiche Funktion ?? im Sommer sofort reinschreiben ?? von – Fi X plus – Y – Forschung – eingebaut – das gilt für alle – so – das Maximum von X und Y – der Ackermann Funktion von W von X plus Y – ich gehe also in der Zeile mit der Nummer B in die Spalte mit der Nummer X bis Y – an der Stelle – ist die Ackermann Funktion sicherlich größer als X und sicherlich größer als Y das heißt aus dem Maximum hier kann X und Y rausschmeißen – hier steht einfach – die Ackermann Funktion von W – vorn – und hinten plus Y – widersteht – die gewinnt garantiert gegen X und Y – an – dieses V hervor – gucken das V ist garantiert – kleiner gleich – W minus eins – dieses – hier ist garantiert kleiner – minus eins – Komma alles beisammen – was hier steht kann ich sagen ?? kleiner gleich Ackermann von – wenn dieses Frau wird durch die minus eins ersetzen kannst ?? nur schlimmer werden – größer – werden hier von Frau – zu Windows eins gehe und hier steht jetzt aber von – B von – etwa wenn es um sehr komische Art – X – plus – eins – Y – minus eins – Plus eins minus eins gibt sich mit steter Exposition – für alle – Y – und meiner Definition nach – ?? in der – Zeile eins nach oben – und hier hinten gehe ich in der – ?? – halte – eins nach links – aber – hoffentlich schon – ich gehe – in der – Eile wie – in der Spalte – eins nach links – benutze das – um in der Zeit davor nach zu gucken toll das ist schlicht und ergreifend das Wasser jetzt als nächstes steht groß X – plus eins – plus Y – das ist Definition der Ackermann Funktion wieder – die Rekursionsvorschrift – ?? Komma von zu – finden irgendwo – um – da – diese Rekursionsvorschrift – ist das – und – damit bin ich am Ziel – Bayern auf halber Strecke zumindest für diesen – Beweis durch vollständige – Induktion auf jeden Fall – die Annahme Komma dass die Funktionen für das X – beschränkt ist durch die wieder Zeile von Ackermann – und ich haben gezeigt – dass das selber funktioniert mit Ixus eins – die vollständige – Iteration durch – und ich finde – die Funktionen – der ständig Simpsons – kleiner als man von X plus Y – für alle – X Y – wie gesagt das ist noch nicht ganz – das was ich brauche ich brauche hinten ein Maximum – von Exposition – sowas vorgesehen – und der Definition – hier – steht das mit dem Maximum – dass es keine groß Aktion wenn ich das habe – schon in ?? Funktion von X Y ist kleiner gleich ein ?? – von X aus Y das habe jetzt für alle – X Y – X plus Y ist garantiert – einer gleich zweimal – das Maximum – von X und Y – nicht den größeren von den beiden nehmen und mal zwei nehme – ich garantiert mindestens so viel als wenn ich die beiden addieren – sich noch an der Ackermann Funktion angucken okay ich gehe in der – Spalte – auf das Doppelte – wie kann ich das durch die – Seile abfedern ich möchte hier – einfach max X Y stehen haben – diese zwei nach vorne bringen – in der – zu – der doppelten Spalte gehen – was kann ich stattdessen mit der – Zeile machen – zum Beispiel die in die Spalte mit der Nummer drei – das – verdoppelt sich – nach der Spalte mit der Nummer sechs – stattdessen der Zeile ANTUN – und sieht – man stattdessen einfach in den Zeilen – zwei weitergehen – von D vier für dich zu den sieben gehen wenn ich die Spalte verdoppeln – ?? wenn in der Zeile zwar weiter gehe – ich hier bei der neun das reicht auf jeden Fall – an – von der ?? war – hier von dieser ?? – drei für dich hier auf die fünf gehen beim verdoppeln der – Spalte – hier weitergehen – ?? zu sieben kein Problem – hier hinten wird's ja noch – viel einfacher je weiter ich nach unten rutscht es so monströser werden ja die Zeilen im Verhältnis in seiner vor ?? überhaupt kein Problem das wir funktionieren müssen ?? offiziell nachrechnen – ?? funktioniert – das heißt – statt dass sich hinten zwei modifizierte Kraniche vorne auch zwei addieren – und habe garantiert etwas das nicht kleiner sein kann – und das ist was zu zeigen war die Funktion F – die – durch primitive Rekursion gewonnen worden ist – aus zwei gedeckten Funktionen ist auch wieder – integrierte Funktion – Punkt – das fand sich dann fort durch diesen – nicht gesamten Raum der – primitiv rekursiven Funktionen – die können dir nicht entfliehen die bleiben weiterhin – durch Ackermann gedeckt wird – Komma kann man selbst ist nicht durch Ackermann gewickelt – also Wörter kann man nicht dazu