flaass' Journal

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.
( Read more... )

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.)