Transcomputační problém je úloha v teorii výpočetní složitosti , která vyžaduje zpracování více než 10 93 bitů informace [1] . Číslo 10 93 , nazývané " Bremermannův limit ", je celkový počet bitů zpracovaných hypotetickým počítačem velikosti Země běžícím maximální možnou rychlostí za časové období rovnající se celkové době života Země [1] [2 ] . Termín „transcomputing“ navrhl Bremermann [3] .
Úkolem obchodního cestujícího je najít způsob, jak obejít daný seznam měst s minimálními náklady. Traverzová cesta musí navštívit všechna města právě jednou a vrátit se do výchozího města. Pokud je v seznamu n měst , pak je počet možných objízdných tras n ! . Protože 66! se přibližně rovná 5,443449391 × 10 92 a 67! ≈ 3,647111092×10 94 , problém kontroly všech možných cest se pro n > 66 stává transpočítačovým .
Kompletní test všech kombinací integrovaného obvodu s 308 vstupy a 1 výstupem vyžaduje testování 2 308 kombinací vstupů. Protože číslo 2308 je transcomputational , úkol testování takového systému integrovaných obvodů je transcomputational problém. To znamená, že neexistuje způsob, jak brutálně vynutit schéma pro všechny vstupy [1] [4] .
Uvažujme pole q × q představující šachovnicový vzor, ve kterém každý čtverec může mít jednu z k barev. Celkový počet možných vzorů je k n , kde n = q 2 . Úkol určit nejlepší klasifikaci vzorů podle libovolného zvoleného kritéria lze vyřešit výčtem všech možných barevných vzorů. Pro 2 barvy se takové hledání stane transpočítačovým, když je velikost pole 18×18 nebo více. Pro pole 10×10 se problém stává transpočítačovým, když je počet barev 9 nebo více [1] .
Tento úkol souvisí se studiem fyziologie sítnice . Sítnici tvoří asi milion buněk citlivých na světlo. I když má buňka pouze 2 možné stavy, zpracování stavu sítnice jako celku vyžaduje zpracování více než 10 300 000 bitů informací. To daleko překračuje Bremermannův limit [1] .
Systém n proměnných, z nichž každá může nabývat k možných stavů, může mít k n možných stavů. Analýza takového systému vyžaduje zpracování alespoň kn bitů informací. Úloha se stává transpočítačovou, pokud k n > 10 93 . To se děje pro následující hodnoty k an [ 1] :
k | 2 | 3 | čtyři | 5 | 6 | 7 | osm | 9 | deset |
n | 308 | 194 | 154 | 133 | 119 | 110 | 102 | 97 | 93 |
Existence skutečných transcomputingových problémů má za následek omezení počítačů jako prostředků zpracování dat. Pouhým zvýšením výpočetního výkonu nebude možné vyřešit problémy, které vyžadují zpracování velkého množství možných situací [2] .
V knize Stopařův průvodce po galaxii od Douglase Adamse byl vyřešen transcomputační problém, který odpovídá na „Hlavní otázku života, vesmíru a vůbec“ (odpověď je známá jako 42 ).