Ackermannova fce iterativně, třídy jazyků
asked Jun 9 '16
Je možné napsat Ackermannovu funkci iterativně? (nejde mi k kód, ale o obecny vztah mezi problemy)
Měl jsem za to, že každý algoritmus, který obsahuje rekurzi je možné přepsat iterativně, ev. se zásobníkem simulujujícím zanoření rekurze.
Jestli ale chápu dobře, co se kreslí a povídá na videu (The Most Difficult Program to Compute? - Computerphile, link dole), tak jsou fce, které není možné vyjádřit iterativně, ze své podstaty a problémy je možno rozdělit do této hierarchie, podle jejich řešení -- vyšší skupiny obsahují nižší (podobné jako ve videu).
| 4. neřešitelné |
+--------------------------------+
| 3. rekurzivně spočetný |
+--------------------------------+
| 2. rekurzivní |
+--------------------------------+
| 1. primitivně rekurzivní |
+--------------------------------+- Možno napsat rekurzí i iterací
- Možno napsat pouze rekurzí
- Možno napsat pouze rekurzí, program se nemusí zastavit nad některými vstupy
- Není možné algoritmicky vyřešit
Platí dále ekvivalence těchto skupin k členění jazyků z AAG? Tj. platá pro ty samé skupiny také:
- Je kontextovým jazykem, rozpozná lin. omezený TS
- Je rekurzivní jazyk, TS jej rozhoduje
- Je rekurzivně spočetný jazyk, TS nerozhoduje
- Je formální jazyk
Video
https://www.youtube.com/watch?v=i7sm9dzFtEI
Edit: Opraveno špatné zaměnění pojmů nerozhodnutelný a neřešitelný
