Efektívne algoritmy a zložitosť - 13 - Univerzálny RAM

Zhrnutie prednášky

Prednáška zavádza univerzálny RAM (simulátor), ktorý simuluje ľubovoľný RAM program P na vstupe X a možno ho implementovať s konštantným malým počtom registrov, pretože obsah všetkých registrov sa dá zakódovať do jedného čísla pomocou mocnín prvočísel. Pomocou neho sa redukciou z problému zastavenia dokazuje nevypočítateľnosť funkcie isbig_10000, ktorá zisťuje, či program použije viac ako 10 000 registrov. Ak sa obmedzí aj veľkosť hodnôt v registroch (funkcia isbig/pretečenie), problém sa stáva vypočítateľným. Program totiž môže mať len konečne veľa nepretečených stavov, takže po viac ako M krokoch sa nutne zacyklí a stačí simulovať M krokov.

• - Univerzálny RAM (sim) simuluje program P na vstupe X, vrátane variantu s obmedzením na T krokov.
• - Všetky registre simulovaného stroja možno zakódovať do jedného registra pomocou súčinu mocnín prvočísel, preto simulátor potrebuje len konštantný počet registrov.
• - Funkcia isbig_10000 (použije program viac ako 10 000 registrov?) je nevypočítateľná, čo sa dokazuje Turingovou redukciou z problému HALT.
• - Redukcia: program Q simuluje P na X a po skončení inkrementuje 10 001 registrov, takže P sa zastaví práve vtedy, keď Q použije veľa registrov.
• - Stav RAMu je určený obsahom nenulových registrov a číslom vykonávaného riadku; opakovanie stavu znamená nekonečný cyklus.
• - Pretečenie (viac ako 10 000 registrov alebo hodnota nad 10 000) je vypočítateľné, lebo nepretečených stavov je najviac M a stačí simulovať M krokov.
• - Obmedzenie veľkosti registrov mení nevypočítateľný problém na vypočítateľný.

Zhrnutie pripravené s pomocou AI z prepisu videa.