Matematické Fórum

Zdravím,
lámu si hlavu s přesnějším specifikováním a odůvodněním něčeho, co vypadá na první pohled zřejmé: když umíme sadu přepisovacích pravidel stručně definovat obecnou funkcí, tak bychom měli být schopni sekvenci odpovídajících znaků stejně stručně definovat nějakým odpovídajícím programem.


Mějme zobrazení P: N->N. Dále mějme funkci-program p v univerzálním jazyce, který toto zobrazení generuje tak, že na vstupu dostane číslo a vyhodí množinu jeho obrazů podle P. Nechť je tento program "stručný", to znamená, že nemá větší počet znaků, než je součet všech dvojic <vzor-obraz> v P.

Zajímá mě, jestli dojde k nějaké významné změně, když zobrazení i program převedeme na jejich "kolmogorovskou verzi", tzn. že
-jednotlivé dvojice <vzor-obraz> dostanou svůj kód
-zobrazení P se změní na Q: sekvenci kódů pro jednotlivé dvojice v arbitrárním pořadí
-a program p se změní na q: program, generující kódy pro všechny definované dvojice v arbitrárním pořadí.

Jak moc se může složitost programu p lišit od kolmogorovské složitosti programu q? Prosím o vysvětlení.