чуть-чуть об алгоритмах (англ.)
(может быть интересно читателям со склонностью к математике, компьютерам итп.)
Тьюринг доказал в 1936-м году, что невозможно решить проблему остановки: невозможно написать такую программу, которая сможет, получив на входе описание алгоритма, определить безошибочно, остановится этот алгоритм когда-нибудь, если его запустить, или нет. Эта задача принципиально неразрешима.
В одном обсуждении один из участников написал, что ему не нравится в доказательстве неразрешимости тот факт, что гипотетическая программа, которая может решить проблему остановки, запускает в некотором смысле "сама себя", и противоречие получается от того, что она не может решить проблему остановки для себя самой (или, точнее, немного расширенную версию себя самой). Ведь вообще-то нас интересуют реальные программы; если бы у нас была программа, умеющая решать проблему остановки, мы бы запускали ее на реальных программах, а не на "ней самой"; если бы она вдруг на себе самой не работала, это бы нам и не мешало. Т.е. доказательство верно, конечно, но остается ощущение, что это такая техническая победа, а не настоящая. В ответ я написал нижеследующий длинный комментарий по-английски, о природе алгоритмов и доказательствах неразрешимости проблем.
Algorithms are clever ways to pack up an infinity of data into a finite description.
Say there’s an infinite (here and below “infinite” means “countably infinite”; if you don’t know what that means, ignore this remark) binary string of zeroes and ones, some 010010101101111… Suppose I come up to you and I say: “I am the keeper of this infinite string of data. People come to me and ask: what is at the 13th place in this string, 0 or 1? How about 23523238th place? For any query they ask, I think for a while and then give them the correct answer. But I’ve been doing this for a long time and could use a vacation. Could you take over for me for a while? The job pays well.”
You might reply to me: ( Collapse )
Тьюринг доказал в 1936-м году, что невозможно решить проблему остановки: невозможно написать такую программу, которая сможет, получив на входе описание алгоритма, определить безошибочно, остановится этот алгоритм когда-нибудь, если его запустить, или нет. Эта задача принципиально неразрешима.
В одном обсуждении один из участников написал, что ему не нравится в доказательстве неразрешимости тот факт, что гипотетическая программа, которая может решить проблему остановки, запускает в некотором смысле "сама себя", и противоречие получается от того, что она не может решить проблему остановки для себя самой (или, точнее, немного расширенную версию себя самой). Ведь вообще-то нас интересуют реальные программы; если бы у нас была программа, умеющая решать проблему остановки, мы бы запускали ее на реальных программах, а не на "ней самой"; если бы она вдруг на себе самой не работала, это бы нам и не мешало. Т.е. доказательство верно, конечно, но остается ощущение, что это такая техническая победа, а не настоящая. В ответ я написал нижеследующий длинный комментарий по-английски, о природе алгоритмов и доказательствах неразрешимости проблем.
Algorithms are clever ways to pack up an infinity of data into a finite description.
Say there’s an infinite (here and below “infinite” means “countably infinite”; if you don’t know what that means, ignore this remark) binary string of zeroes and ones, some 010010101101111… Suppose I come up to you and I say: “I am the keeper of this infinite string of data. People come to me and ask: what is at the 13th place in this string, 0 or 1? How about 23523238th place? For any query they ask, I think for a while and then give them the correct answer. But I’ve been doing this for a long time and could use a vacation. Could you take over for me for a while? The job pays well.”
You might reply to me: ( Collapse )
