Matematické Fórum

Možná toto záleží na tom, jaká formalizace a jaké zakódování turingova stroje se zvolí. Když se ale budou používat turingovy stroje s jednou pomocnou páskou, tak si jsem jistý, že bude dokonce existovat aditivní konstanta k' tž zakódování turingova troje (včetně pomocné pásky) bude nejvýše o k' větší než posloupnost ke kompresi.

Potřebný turingův stroj bude mít takovýto program:
1. Pokud nejsi na konci přepiš znak z pomocné pásky na výstupní pásku
2. Opakuj

Takovýto turingův stroj zabírá konstantní velikost při libovolném zakódování. Projistotu zvolíme takové zakódování, aby z posloupnosti znaků, která stroj kóduje tak, aby bylo poznat, kde tento kód končí. Délku si označíme k'.

Díky tomu, že máme kódování, které umí rozlišit konec kódu turingova stroje můžeme turingův stroj spolu s obsahem pomocné pásky reprezentovat jen tak, že obsah pomocné pásky připojíme beze změny za kód turingova stroje.

Do pomocné pásky se umístí posloupnost ke kompresi. Jelikož stroj opisuje pomocnou pásku na výstup, tak je to stroj který chceme a navíc jeho délka je odpovídá délce posloupnosti ke kompresi + k'.

V případě, že budeme kódovat jen neprázdné posloupnosti tedy existuje i multiplikativní konstanta k, tak aby byla podmínka splněna.

Jinak si mě málem dostal právě na této prázdné posloupnosti. To bych jedině musel dodefinovat, že prázdný archiv znamená, že i vstupní soubor pro kompresi byl prázdný.

Jinak, ale pokud se mě ptáš, jestli na té podmínce trvám, tak odpověď je ne. Zajímají mě i slabší komprese s podobně zajímavými vlastnostmi.

Nevím, proč by mělo mít zakódování turingova stroje nějakou roli? Navíc už není třeba kód turingova stroje nijak kompresovat. Jsem spokojený s kódováním pomocí všeho daného vedle sebe, odděleného nějakým oddělovačem. Případně překódované do nul a jedniček, když to má být pro počítač.

Hlavní kouzlo a krása této komprese, kterou hledám, je komprese věcí, které mají nějaký vnitřní systém.

Třeba:

3.14159

a další miliardy cifer by má ideální komprese měla dokázat zkomprimovat na minimum. Nejprve by poznala, že se jedná o číslo PI (tzn. vymyslela program pro  libovolně přesnou aproximaci čísla PI) a pak jen uložila kolik cifer má být na výstupu.

Na tom multiplikativní konstantě říkající, jestli to bude 1kB nebo 1GB mi nezáleží. Jde o tu schopnost poznání systému a pravidelností v čemkoli.

Jinak číslo PI je zajímavé tím, že všechny jeho cifry se v limitě vyskytují stejně často a zdají se být náhodné. Proto si s tím běžné komprese moc neporadí.

Neporozuměl jsi vůči čemu konstantu K měřím!!!

Cituji původní dotaz: 'existovala nějaká konstanta K, tak aby zkomprimovaný soubor měl velikost maximálně K krát větší než tolik kolik obsahoval původní vstupní soubor skutečné informace. Teď ale ještě musím vysvětlit co to znamená "množství skutečné informace".'

Množství skutečné informace může splívá s velikostí vstupního souboru, pouze pokud by vstupní soubor obsahoval náhodný bordel.

Ale například pokud bych si ukládal mnoho cifer z čísla PI, tak té skutečné informace je méně než kolik bajtů zabírá nezkomprimovaný zápis.

Konkrétně se dá vstupní posloupnost popsat dvěma fakty:
1. je to číslo PI a je ve formátu textového souboru uloženo v desítkové soustavě. (+ něco technického o tom, že číslice nula je v textovém souboru dnešních počítačů znak s asci kódem 48)
Toto zabírá velikost, která se vejde do další nezajímavé konstanty, třeba c.

2. kolik jeho cifer je třeba uložit
Pokud by bylo potřeba uložit n cifer. Tak tato informace zabírá O(log n) místa.

Tedy chci, aby zkomprimovaný soubor měl velikost maximálně K krát větší než c + log n.