Revision history [back]

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. nerozhodnutelné             |  
+--------------------------------+
| 3. rekurzivně spočetný         |  
+--------------------------------+
| 2. rekurzivní                  |  
+--------------------------------+
| 1. primitivně rekurzivní       | 
+--------------------------------+

1. Možno napsat rekurzí i iterací
2. Možno napsat pouze rekurzí
3. Možno napsat pouze rekurzí, program se nemusí zastavit nad některými vstupy
4. 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é:

1. Je kontextovým jazykem, rozpozná lin. omezený TS
2. Je rekurzivní jazyk, TS jej rozhoduje
3. Je rekurzivně spočetný jazyk, TS nerozhoduje
4. Je např. hlating problem.

youtube.com watch?v=i7sm9dzFtEI (insufficient karma to publish links)

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. nerozhodnutelné             |  
+--------------------------------+
| 3. rekurzivně spočetný         |  
+--------------------------------+
| 2. rekurzivní                  |  
+--------------------------------+
| 1. primitivně rekurzivní       | 
+--------------------------------+

1. Možno napsat rekurzí i iterací
2. Možno napsat pouze rekurzí
3. Možno napsat pouze rekurzí, program se nemusí zastavit nad některými vstupy
4. 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é:

1. Je kontextovým jazykem, rozpozná lin. omezený TS
2. Je rekurzivní jazyk, TS jej rozhoduje
3. Je rekurzivně spočetný jazyk, TS nerozhoduje
4. Je např. hlating problem.

youtube.comVideo watch?v=i7sm9dzFtEI (insufficient karma to publish links) https://www.youtube.com/watch?v=i7sm9dzFtEI

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. nerozhodnutelné             |  
+--------------------------------+
| 3. rekurzivně spočetný         |  
+--------------------------------+
| 2. rekurzivní                  |  
+--------------------------------+
| 1. primitivně rekurzivní       | 
+--------------------------------+

1. Možno napsat rekurzí i iterací
2. Možno napsat pouze rekurzí
3. Možno napsat pouze rekurzí, program se nemusí zastavit nad některými vstupy
4. 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é:

1. Je kontextovým jazykem, rozpozná lin. omezený TS
2. Je rekurzivní jazyk, TS jej rozhoduje
3. Je rekurzivně spočetný jazyk, TS nerozhoduje
4. Je např. hlating problem.

Video

https://www.youtube.com/watch?v=i7sm9dzFtEI

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. nerozhodnutelné neřešitelné                 |  
+--------------------------------+
| 3. rekurzivně spočetný         |  
+--------------------------------+
| 2. rekurzivní                  |  
+--------------------------------+
| 1. primitivně rekurzivní       | 
+--------------------------------+

1. Možno napsat rekurzí i iterací
2. Možno napsat pouze rekurzí
3. Možno napsat pouze rekurzí, program se nemusí zastavit nad některými vstupy
4. 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é:

1. Je kontextovým jazykem, rozpozná lin. omezený TS
2. Je rekurzivní jazyk, TS jej rozhoduje
3. Je rekurzivně spočetný jazyk, TS nerozhoduje
4. Je např. hlating problem.formální jazyk

Video

https://www.youtube.com/watch?v=i7sm9dzFtEI