Gordievskij i problema ostanovki
Probegaja cherez arxiv "Besedy ob osnovanijax matematiki", nashel tam zabavnyj vopros, zadannyj nekiim Anatoliem Vorobeem:
esli vam dali chernyj jashhichek, i skazali, chto on reshaet problemu ostanovki, to kak vy eto proverite?
(Problema ostanovki - eto vot chto: dana programma dlja mashiny Tjuringa, opredelit', ostanovitsa li ona. Legko dokazat', chto problema algoritmicheski nerazreshima, t.e. nikakaja programma dlja mashiny Tjuringa ee ne reshaet.)

A vot analogichnyj vopros, iz shpionskogo byta:
k vam prishel perebezhchik, s polnoj golovoj vrazheskix sekretov. Kak uznat', ne podoslan li on dlja dezinformacii?
(Tipichnyj primer - Gordievskij v Anglii.)

I otvety na eti dva voprosa tozhe prakticheski sovpadajut.

Ochevidno, chto poluchit' polnuju garantiju ni tam, ni tam v principe nevozmozhno. No zato mozhno poluchit' mnogo pol'zy.
Perebezhchika nado rassprashivat' o tom, chto bez nego uznat' ochen' trudno, zato legko proverit', veren li otvet. I togda vse vremja, poka on ne "prokoletsa", ty budesh' poluchat' pervoklassnuju i poleznuju informaciju.

Tak zhe i s jashhichkom.
Vvedja v nego programmu MT, poluchaesh' v otvet vsego odin bit (ostanovitsa/ne ostanovitsa). Zato poluchaesh' ego za konechnoe, zaranee izvestnoe i ne ochen' bol'shoe vremja! (A inache voobshhe ne o chem govorit'; bez etogo uslovija o vremeni tam mogla by, naprimer, prosto stojat' mashina Tjuringa:) )
I ja by srazu nachal chitat' dokazatel'stva Boga (znamenitaja ideja Erdos'a). Zapuskaesh' v jashhik programmy vida: "If the n-th symbol in the lexicographically minimal among shortest proofs of such-and-such theorem is 0(1) then stop; otherwise never stop".

O, dajte, dajte mne skoree takoj jashhichek!


Update: i tut zhe, lazaja po ssylkam iz frend-lenty, nashel chudnuju illjustraciju po teme:

"It may be perpetual motion, but it will take forever to test it."
(Cartoon by Donald Simanek.)