Ask Your Question
3

Ackermannova fce iterativně, třídy jazyků

asked 2016-06-09 15:00:38 +0100

smolijar gravatar image

updated 2016-06-15 00:06:08 +0100

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í       | 
+--------------------------------+
  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 formální jazyk

Video

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

Edit: Opraveno špatné zaměnění pojmů nerozhodnutelný a neřešitelný

edit retag flag offensive close delete

2 Answers

Sort by » oldest newest most voted
1

answered 2016-06-09 23:28:31 +0100

Greg gravatar image

updated 2016-06-16 08:56:00 +0100

Miro Hrončok gravatar image

Samozřejmě, že to jde. Kód máš třeba zde. Pokud se jedná o koncovou rekurzi, není dokonce ani potřeba zásobník. Tady je když tak postup, jak to obecně převádět ;-).

edit flag offensive delete publish link more

Comments

Ano, nevnorenou rekurzi umim prevadet, ze neni treba zasobnik u koncove jsem si vedom. Dekuji za odkaz. Jen tedy nevim, jestli spatne chapu, co je rece no v uvedenem videu, nebo jestli to je zkratka spatne. Jak jsem ale psal, nejde mi tolik o iterativni kod, ale spise o podstatu tech problemu a analogii k jazykum z AAG, jestli takova je.

smolijar ( 2016-06-09 23:47:38 +0100 )edit
1

Já si myslím, že to není špatně. Rekurzivní algoritmus je v podstatě stále rekurzivní (z teoretického hlediska), ať už je zásobník implicitní (systémový stack spravovaný instrukcemi push, pop) nebo explicitní. Iterativní v pravém slova smyslu je potom asi jedině algoritmus, který zásobník nepotřebuje. Takhle bych to chápal já...

nohajan ( 2016-06-18 12:45:17 +0100 )edit
2

answered 2016-06-28 17:35:26 +0100

PeterBocan gravatar image

updated 2016-06-28 17:48:52 +0100

Odkážem na predmet MI-VYC (Vyčísliteľnosť, Computability Theory, Mgr. Jan Starý, Ph.D.). Materiály k predmetu MI-VYC (http://users.fit.cvut.cz/~staryja2/MIVYC/) a EDUX.

Špeciálne odkazujem na materiál http://users.fit.cvut.cz/~staryja2/MIVYC/kucera-vycislitelnost-a-slozitost.pdf a kapitoly 1 a 2.

edit flag offensive delete publish link more

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

Asked: 2016-06-09 15:00:38 +0100

Seen: 210 times

Last updated: Jun 28