ich hoffe wirklich, hier ist noch jemand der sich damit auskennt und mich ggf. korrigieren kann!
ansonsten meine aussagen auf die goldwaage legen. ihr wisst ja, dass das von einem absolute n00b kommt,
also falls es oberlehrerhaft klingt, ruhig auf mich draufkloppen!

bitte nicht nach der motivation fragen, renee hat gefragt, ob ich nen extra thread dafür aufmach.
nun, hier ist er, und ich benutze das schamlos, um mich auf meine thinf-klausur vorzubereiten.

:)

[html]<hr />[/html]

fang mal an, kabel! ein grober überblick wär z.b. net schlecht...

es geht in die tiefen der theoretischen informatik. da können wir grob die themen
- formale sprache (sprachtypen, grammatiken, ...),
- automatentheorie (automaten, die die verschiedenen sprachtypen erkennen, turingmaschine, regulärer automat, kellerautomat etc),
- komplexitätstheorie (landau, komplexitätsklassen (z.b. P)) und
- berechenbarkeitstheorie (was ist überhaupt berechenbar?)
unterscheiden (unvollständig).

in welchem bereich fällt nu diese komische ackermannfunktion?

wie ich schon andeutete, hat die ackermannfunktion was mit berechenbarkeit zu tun. berechenbarkeit heisst in diesem fall /intuitive/ berechenbarkeit. berechenbar heisst eine funktion f genau dann, wenn man ein /allgemeines verfahren/ angeben kann, dass f berechnet (z.b. ein algorithmus in pseudocode).

warum jetzt auf einmal _intuitive_ berechenbarkeit?
reichts net von einer funktion zu wissen, dass sie berechenbar ist?

ganz so einfach ist das nicht. was heisst denn berechenbar im /intuitiven/ sinne genau? genau, das interpretiert man sich so zusammen. das ist aber nicht erwünscht, die grundbegriffe müssen exakt definiert sein, ansonsten ist die theorie nicht viel wert; nämlich genau gar nichts.

also wird die definition von _intuitiv berechenbar_ auf die definition des _allgemeine verfahrens_ abgeschoben?

ich gehe mal davon aus, dass du weisst, was eine turingmaschine ist.

denk dir an dieser stelle einfach eine turingmaschine. d.h. eine funktion f ist genau dann intuitiv berechenbar, wenn es eine turingmaschine t gibt, die f berechnet. das ist zwar nicht bewiesen, wird aber heute als gültig angenommen (sog. Churchsche These)

zurück zum thema: ist die ackermannfunktion intuitiv berechenbar? oder was hat die sonst damit zu tun?

ja, die ackermannfunktion ist intuitiv berechenbar per se, da ja die berechnungsvorschrift angebbar ist.

um zu erklären, was diese funktion mit der intuitiven berechenbarkeit zu tun hat, muss ich ein wenig ausholen:

D. Hilbert hat 1926 die vermutung aufgestellt, dass jede berechenbare funktion primitiv-rekursiv ist. Widerlegt worden ist er von einem Herrn Ackermann ( klingelingeling! ), der eine totale Funktion angegeben hat, die nicht primitiv-rekursiv ist.

Jaja, der Hilbert hatte es schon nicht leicht. Er versuchte auch, die mathematik zu "retten" (bzw. den satzvorrat der mathematik), indem er die widerspruchsfreiheit der basisaxiome zeigen wollte ("Hilbert-Programm"). dazu sag ich dann nur noch den namen Kurt Gödel ...

du schwafelst zuviel. erstmal eine begriffsbestimmung. was ist denn _primitive rekursion_? und wann ist eine funktion _total_?

ich beginne mit dem begriff "total". machen wir uns dazu erstmal klar, von welchen funktionen wir hier reden. es geht um funktionen, die von N*N*...*N nach N abbilden. zu abstrakt? beispiel: die funktion f: N*N*N->N, f(a, b, c) = a*b*c bildet drei natürliche zahlen auf das produkt dieser ab. eine funktion heisst genau dann total, wenn sie für jede mögliche eingabe ein ergebnis liefert.

gibts denn funktionen, bei denen des net so ist?

funktionen gibt es viele, aber wie ich weiter unten ausführen werde, sind alle hier zu betrachtenden funktionen total.
deswegen nur als klitzekleiner ausblick: suchvorgänge führen zu /partiellen/ funktionen (partiel := nicht total), z.b. ist die berechnungsvorschrift m/n (division) für n=0 undefiniert, für n!=0 ist m/n das kleinste z so dass (z+1)*n>m ist; ganzzahldivision! und nicht mal das, denn wir haben nur natürliche zahlen zur verfügung.

puh, na gut, mach mal weiter ...

primitiv rekursive funktionen sind nun eine klasse von funktionen, die auf eine ganz bestimmte art und weise erzeugt werden. hier ist v.a. folgende tatsache interessant: alle primitiv rekursiven funktionen sind aufgrund ihrer konstruktion total. da hilbert gesagt hat, dass alle effektiv berechenbaren funktionen primitiv-rekursiv sind, sagt er also auch, dass alle effektiv berechenbaren funktionen total sind.

und genau in diese kerbe trifft die ackermannfunktion. sie ist zwar einerseits total, andererseits aber nicht primitiv-rekursiv.

:blitz:, widerspruch

die genaueren zusammenhänge und einen beweis erspare ich mir hier. geht definitiv zu weit.
wieder nur ein hinweis: die ackermannfunktion wächst schneller als alle primitiv rekursiven funktionen.
des hab ich selber auch net gepeilt, vielleicht jetzt, durch das erneute nachdenken?!

ich erinnere mich da noch an die µ-rekursivität, die du mal erwähnt hast ...

ach ja. die ackermannfunktion ist µ-rekursiv. diese funktionsklasse ist ziemlich mächtig. zu den konstruktionsvorschriften der primitiv-rekursiven funktionen kommt ein sog. µ-operator dazu mit folgender semantik: (f(x) = µzPxz)

sprich: f an der stelle x ist das kleinste z, so das Pxz wahr ist, falls ein solches z überhaupt existiert, ansonsten 0. Pxz ist dabei ein zweistelliges Prädikat (=Funktion mit Wertebereich {wahr,falsch}). bei prädikaten ist präfix-notation üblich.

[s]so das sagt jetzt keinem was[/s] (jetzt vielleicht schon), Crian hab ich die falsche definition gepostet (grummel, nämlich die des beschränkten µ-operators), und ansonsten bin ich jetzt erstmal "bedient".

ich auch. gute nacht.

[html]<hr />[/html]

UPDATES:
1. den begriff der effektivität rausgeschmissen. da er in der literatur nicht vorkommt, wird er nur verwirren.
komischerweise passt es jetzt auch mit der chuchschen these ...
2. erklärung zum µ-operator ergänzt.
\n\n

<!--EDIT|kabel|1089789434-->