Pád do černé díry: Počítat lépe než Turingův stroj

Pavel Houser , 24. prosinec 2015 12:00 5 komentářů
Rubriky: Zajímavosti, Science
Pád do černé díry: Počítat lépe než Turingův stroj

Fyzikální svět vnímají informatici a matematici vesměs jako překážku – typicky něco lze sice vypočítat (rozlomit šifru apod.), ale trvalo by to třeba déle než doba existence vesmíru. Černé díry však takový pohled na věc ale poněkud komplikují až obracejí.

Celá záležitost je značně bizarní, protože mj. zahrnuje možnost se kvůli řešení určitého problému do černé díry prostě vrhnout – a to už vyžaduje značnou oddanost vědě a touze po poznání, však jde o krok totálně jednosměrný a nevratný. Výklad celého jevu je bohužel poměrně komplikovaný, samozřejmě i hodně hypotetický („pokud pomineme, že...“), nicméně snad dostatečně zajímavý, aby stálo za to číst i trochu delší text.

Boj s nerozhodnutelností

První věcí je, že v matematice překvapivě existují problémy, které jsou standardními prostředky tzv. nerozhodnutelné. Jde přitom stále o normálně definované matematické problémy – fakt, že tímto způsobem nelze odpovědět na otázku po smyslu života, by asi překvapil málokoho. Celá teorie souvisí mj. s možnostmi výpočetních systémů, kterým se říká Turingův stroj, a s objevy rakouského logika a matematika Kurta Gödela. Každopádně Turingův stroj představuje obecný výpočetní koncept, od něhož se odvozují současné výpočetní systémy, ať už jde o počítače klasické nebo kvantové (ty mají být rychlejší; rychlostí se zabývá teorie výpočetní složitosti, teď nám jde o teorii samotné vypočitatelnosti, kde kvantové počítače žádný pokrok nepředstavují). Existuje dokonce tzv. Churchova (Churchova-Turingova) teze, podle níž cokoliv vypočitatelného je vypočitatelné nějakým Turingovým strojem.

Začíná to působit trochu jako definice kruhem, takže to, že existují i úlohy nerozhodnutelné, je nejlépe vzít alespoň provizorně prostě jako fakt. Může jít třeba o problémy, které vyžadují projít nekonečně možností. (Další odbočka: samozřejmě ale ne všechny úlohy, kde nějak figuruje nekonečno, jsou nerozhodnutelné. Třeba to, že prvočísel je nekonečno, se dá dokázat celkem jednoduše bez toho, aby bylo třeba nechávat počítač procházet všechna čísla.)

Nás zde bude zajímat, že některé z klasicky nerozhodnutelných úloh by kupodivu mohly být řešitelné s použitím prostředků relativistické fyziky. Dále popsaný postup kupodivu není výplodem chorého mozku, ale celkem standardní akademickou vědou (Kolektiv autorů: Umělá inteligence 5, Academia 2006, podle části Výpočetní meze kognitivních a inteligentních systémů od prof. Jiřího Wiedermanna).

Pád do černé díry

Takže konečně k věci. Dejme tomu, že vás zajímá, zda platí věta, dle které lze každé sudé číslo větší než 2 vyjádřit jako součet dvou prvočísel (tzv. Goldbachova domněnka). Dejme tomu, že problém nejde řešit jinak než tím, že projdete všechna čísla. To je potíž: sudých čísel je nekonečně, můžete sice odhalit protipříklad, ale platnost domněnky takhle neprokážeme nikdy – vždy bude zůstávat možnost, že někde dále existuje sudé číslo, které takto vyjádřit nepůjde.

Relativistická fyzika se všemi svými dilatacemi a kontrakcemi ale podle všeho připouští konstrukci zvláštního uspořádání, při němž počítač necháme počítat nekonečně dlouhou dobu a sami se přitom uchýlíme do systému, v němž zatím uplyne pouze konečný čas. Jinak řečeno, náš vlastní čas se nekonečně zpomalí a my si tedy budeme moci počkat i na výsledek nekonečně dlouhého výpočtu. Pokud počítač najde řešení (zde protipříklad konkrétního sudého čísla), vyšle nám příslušný signál.

Jak experiment uspořádat? Počítač provádějící výpočet by prý mohl obíhat kolem černé díry, zatímco zvídavý matematik by do ní padal. Podle všeho by přitom mělo (teoreticky!) jít zařídit i to, aby počítač předal padajícímu pozorovateli výsledek svého výpočtu. Samozřejmě zůstává i tak celá řada sporných míst, počítač počítající nekonečný čas by spotřebovával stále více paměti, vyžadoval stále více energie atd. To ale všechno pomiňme, nejde nám primárně o nic jiného než o bizarní myšlenkový experiment.

Teď se na věc podívejme očima padajícího pozorovatele. Pokud stroj najde protipříklad, pozorovatel se dozví, že Goldbachova domněnka neplatí – ne že by s tou informací mohl dále zvlášť pracovat, pro něj samotného už není návratu a nikomu o svém objevu neřekne (signál může zachytit, ale on sám už žádný signál z černé díry ven vyslat nemůže), kvůli časovému efektu jeho civilizace mezitím už nejspíš stejně dávno zanikla atd.

V opačném případě, když stroj protipříklad nenajde, padající pozorovatel dosáhne vnitřního horizontu černé díry a v tu chvíli nahlédne jakoby celou minulost vesmíru. Jeho poslední myšlenka může být: stroj výpočet nikdy nedokončil, nevyslal signál. Neexistuje tedy žádné sudé číslo větší než 2, které by nešlo vyjádřit jako součet dvou prvočísel, Goldbachova domněnka tudíž platí. To bude závěrečné hnutí zvědavcovy mysli a pak přijde konec.

Obětovat život vědě

Znovu: nejde teď o to, zda lze skutečně zařídit, aby pozorovatel padající do černé díry nezhynul dávno před tím atd. Evidentních námitek se hned nabízí celá řada. Třeba: v extrémním gravitačním poli se natolik liší gravitační síla působící na různé části pozorovatele, že ho ihned roztrhá. Navíc samotná teorie černých děr je stále jen model, bezprostřední zkušenost s nimi nemáme. Experiment je to myšlenkový, někomu na něm může přijít nejzajímavější ne matematika či fyzika, ale i psychologie: pozorovatel, který by byl toto vše ochoten podstoupit, by prokázal neuvěřitelný zájem o řešení daného problému. Vědomí o výsledku by mohlo být jeho skutečně poslední myšlenkou, o níž by se přitom nemohl s nikým podělit.

Na rozdíl od jedince upáleného inkvizicí by se nemohl utěšovat ani tím, že mu budoucnost dá za pravdu, neobjevil by se v žádné učebnici a nakonec by si nemohl užít ani vlastní proces řešení – výpočet by prováděl počítač bez jeho přispění. Jedinou odměnou za to všechno by byl vlastní výsledek: teď vím, jak to je.

Když ponecháme stranou psychologii, subjektivně se mi na tom zdá nejzajímavější věc zmíněná v úvodu: fyziku při počítání většinou vnímáme jako překážku. Zde je to naopak. Matematika, respektive informatika, prohlašují úlohu za nerozhodnutelnou, ale fyzika alespoň teoreticky nabízí řešení. Náhle není v roli někoho, kdo jen překáží, ale naopak otevírá cestu. Churchova teze, o níž se všude v učebnicích informatiky píše, že samozřejmě platí, ale formálně to bohužel nejde dokázat, je tak možná prostě chybná!

Mimochodem, kvůli čemu byste se do černé díry byli ochotni vrhnout vy?

Co přidat dvojníky?

Australský matematik a autor sci-fi Greg Egan v jedné ze svých povídek dokonce experiment ještě vyostřuje (Greg Egan: Luminous, Talpress 2011, povídka Planckův skok). Hrdinové si nechají pořídit své kopie a experiment s černou dírou provedou až ony. Pak si lidé můžou říct: odpověď neznám, ale někde žil můj dvojník (druhé já), který ví, jak to je (a já tuto svou kopii kvůli řešení problému nechal zemřít). Velmi sofistikované uspokojení a povolení experimentu by byla jistě skutečná výzva pro všemožné etické komise.

Stroje a oracula

Ovšem pozor, třebaže něco „za Turingův stroj“ by takhle spočítat jít mohlo, nelze z toho vyvodit, že tímto způsobem (samozřejmě, znovu: kdyby to tak vůbec fungovalo) lze řešit veškeré problémy, v nichž vystupují nekonečna. Černá díra není univerzální kouzelnou hůlkou.

Představte si třeba domněnku, že existuje nekonečně prvočíselných dvojic, tedy takových prvočísel, která se od sebe liší o 2 (3 a 5, 17 a 19...). Teď se vraťme do černé díry. Zjistíme, že vlastně vůbec nevíme, kdy má počítač vyslat signál. Prohledává nekonečně čísel, tu najde dvojici, běží dál, zase najde nějakou...

V jakém okamžiku by měl signálem hypotézu falzifikovat? Tohle přirozeně nejsou žádné objevné postřehy, v logice a počítačové vědě tomu odpovídá celá teorie o různých typech Turingových strojů, které mají k dispozici tzv. oracula atd. Každopádně to ukazuje, že i výroky o nekonečnech mohou být různě složité. Jaké gödelovsky nerozhodnutelné věty lze řešit „přes nekonečno“ a jaké odolají i takto extrémním prostředkům, diskutuje trochu z jiné strany např. John Barrow v knize Pí na nebesích (Mladá fronta 2000). (Další dodatek: Barrow pak začal až příliš trapně vykrádat sám sebe, psát čím dál větší hrůzy, získal Templetonovu cenu atd. Nicméně Pí na nebesích je kniha před touto érou.)

Goldbachova domněnka či věta o prvočíselných dvojicích budou nejspíš časem nějak rozhodnuty prostředky klasické matematiky, nebude třeba prohledávat nekonečna. Oba problémy zde sloužily jen jako celkem dobře představitelné příklady.

Pro zájemce: Celkem srozumitelný výklad fungování Turingova stroje viz např. kniha David Leavitt: Muž, který věděl příliš mnoho, Argo a Dokořán 2008

Populárním úvodem do Gödelových objevů je např. Rebecca Goldsteinová: Neúplnost, Argo a Dokořán 2006, techničtější, ale stále populární, je Gödelův důkaz (autoři James Roy Newman a Ernest Nagel, Vutium 2006).


Komentáře

hodbozak #0
hodbozak 25. prosinec 2015 10:51

Dik autorovi! :)

smrt skolsky akreditovane reprodukci monetarniho otroctvi #1
smrt skolsky akreditovane reprodukci monetarniho otroctvi 27. prosinec 2015 01:42

Hezky :)

Tak to mám jen 8 let zpoždění proti našim teoretikům sokolíkům...
Viz: 28. 06. 2014, 23:18:24
presne twin experiment mam na mysli. jenze automatem. vpodstate te chci dostrkat at mi popises automat schopny verifikovat obe teorie relativity.

Mam za to, ze nic zalozeno na experimentech se neda verifikovat - my umime jenom vyvracet na nejake hladine vyznamnosti a konstatovat, ze se nam to nepovedlo na dane hladine vyznamnosti vyvratit. To nerika nic o platnosti nebo neplatnosti tvrzeni, jenom to neco napovida.

a vo tom to je. zacnes spravne a pak popres vlastni existenci :D

.

Docela by mě zajímalo, kterým směrem se teď vydala ta pracovní skupinka z AV, už jenom proto, že kognitivku co předváděla další skupinka sokolíků odjinud jsem stihl odvodit zhruba ve stejnou dobu, kdy na ní pracovali :-)

smrt skolsky akreditovane reprodukci monetarniho otroctvi #2
smrt skolsky akreditovane reprodukci monetarniho otroctvi 27. prosinec 2015 01:54

mimochodem koncept cerne diry uz byl zpochybnen.
uz se pokusili lidi nahradit ten problem se ztratou entropie pouzitim gravitacni hvezdy (gravastar).
z pohledu kosmologa/fyzika naprosta zbytecne puntickareni, ktere nicemu neprispiva a ke kteremu jeste prisli s paradoxem nekonecneho uloziste - zachovani entropie na horizontu, kdy je vracena zpatky do systemu skrz radiaci ktera se z horizontu uvolni a soucasne do nej provede zaznam.

ale to uz jsou jen takove technikalie jak precist vysledek nebo zda je vysledek vypoctu ziskatelny zkopirovatelny i mimo svou topologii existence.

smrt skolsky akreditovane reprodukci monetarniho otroctvi #3
smrt skolsky akreditovane reprodukci monetarniho otroctvi 27. prosinec 2015 01:56

ps: a uz vubec nekdo prisel na to co znamena ten nesmysl co se jeste nepodarilo vysvetlit - jmenem cas? kdyz uz se tu resi otazky konecnosti rozhodnuti?

smrt skolsky akreditovane reprodukci monetarniho otroctvi #4
smrt skolsky akreditovane reprodukci monetarniho otroctvi 27. prosinec 2015 14:49

pro korektnost je potreba dodat, ze takova diskuse nasich akademiku je uz v zakladu chybna.

kvantovka totiz nabizi funkci casu jako paradoxni kruh, ktery ma kontradiktorni charakter k principu uziti casu v teorii rozhodnutelnosti.

z takove kontradikce pak jde dokazat cokoliv. a o kvantovce se na rozdil od rozhodnutelnost vi, ze je na 99% chybna ve smyslu neuplna ve smyslu lziva a zavadejici a bude casem snad nahrazena, rozsirena proste korigovana.


RSS 

Komentujeme

Chatbot mluví za mrtvého – od nápadu k realizaci

Pavel Houser , 30. listopad 2016 13:00
Pavel Houser

Na webu The Verge popsala Casey Newton příběh dvou přátel (Eugenia Kuyda a Roman Mazurenko). Peripet...

Více





Kalendář

RSS 

Zprávičky

Za vzněcováním smartphonu iPhone 6 jsou vnější vlivy, tvrdí Apple

ČTK , 08. prosinec 2016 11:30

Firma Apple odmítla podezření čínských uživatelů svého chytrého telefonu iPhone 6, že za problémy s ...

Více 0 komentářů

Verizon prodá firmě Equinix datová centra za 3,6 miliardy USD

ČTK , 08. prosinec 2016 10:00

Největší americký mobilní operátor Verizon Communications prodá specializované společnosti Equinix 2...

Více 0 komentářů

Tchajwanský Foxconn jedná o rozšíření svých aktivit v USA

ČTK , 07. prosinec 2016 15:00

Tchajwanská společnost Foxconn jedná o rozšíření svých aktivit ve Spojených státech. Oznámila to dne...

Více 0 komentářů

Starší zprávičky

Nejvyšší soud USA se postavil na stranu Samsungu proti Applu

ČTK , 07. prosinec 2016 12:30

Americký nejvyšší soud se v mnohaletém patentovém sporu mezi výrobci chytrých telefonů Apple a Samsu...

Více 0 komentářů

Evropská komise Microsoftu schválila převzetí sítě LinkedIn

ČTK , 07. prosinec 2016 10:30

Evropská komise schválila americké softwarové společnosti Microsoft záměr koupit za 26 miliard dolar...

Více 0 komentářů

Porozumění větám, konkurence pro Turingův test

Pavel Houser , 06. prosinec 2016 18:00

Konverzační roboti mají stále problémy pochopit věty, kde smysl nelze vyvodit ze samotné gramatické ...

Více 0 komentářů

Americká GoDaddy koupí evropský webhosting Host Europe

ČTK , 06. prosinec 2016 16:00

Americký registrátor internetových domén GoDaddy, který je ve svém oboru největší na světě, se dohod...

Více 0 komentářů