?

Log in

No account? Create an account

Previous Entry | Next Entry

The Halting Problem

Учила алгоритмы. Замечательный курс. Впрочем, экзамен провалю нафик.

Да, так вот. Есть там такая теорема (в моём вольном переводе с английского):
Не существует программы*, которая сможет, получив как параметры другую программу* P и входные данные x, определить, остановится ли программа P с вводом x.

Доказывается очень просто и очень смешно.

Для начала мы предположим, что вышеописанная программа есть. И оптимистично назовём её... ну, скажем, HALT_CHECKER. HALT_CHECKER нам скажет всю правду: если программа P c вводом x остановится, true. Если нет, false. И будет нам щастье.

А потом мы напишем другую программу, которую наш профессор назвал FIDO и мне совершенно непонятно, почему 8). But FIDO will make a trick. Итак,

FIDO(P)

1. if HALT_CHECKER(P, P) is true, go into an eternal loop
2. else halt

Заметьте, как ловко программа дублирует свой ввод, отсылая его в HALT_CHECKER и как программу для проверки, и как входные данные. Уже наводит на определённые подозрения, что следующим шагом...

...КОНЕЧНО! А теперь мы скормим FIDO как параметр FIDO! 8)

Да, как я говорю, очень смешно получается.

*Имеется ввиду RAM-программа

Comments

( 14 comments — Leave a comment )
ariena
Jul. 31st, 2005 03:00 am (UTC)
Как хорошо, что я беру алгоритмы в Швеции. :) Надеюсь, меня там это не заставят учить :)
be_unafraid
Jul. 31st, 2005 03:07 am (UTC)
Да ладно, я же говорю - смешно-о-о-о =) По-моему, это плюс вне зависимости от того, заставляют тебя учить *это* или алгоритмы четвёртого года =)
ariena
Jul. 31st, 2005 03:12 am (UTC)
В Швеции я беру 341, кстати :)

ну да, смешно :)) мы это еще в 360 проходили тоже :) готовься! :)
be_unafraid
Jul. 31st, 2005 03:15 am (UTC)
Так я знаю =) *пророческим шёпотом* После своих алгоритмов ты умрёшь там со скуки! *закончила говорить пророческим шёпотом* А 360 я ещё не брала =) Но да, меня морально готовят. Ещё на меня морально давят, чтобы я взяла 365, но я ещё в своём уме =)
ariena
Jul. 31st, 2005 03:19 am (UTC)
Я тоже давлю. :) Возьми. :) Тем более, что все равно "забеллкервят" :)
be_unafraid
Jul. 31st, 2005 03:35 am (UTC)
*взвизгивает* Вы все сговорились! 8)
indeyets
Jul. 31st, 2005 05:46 am (UTC)
в условии отсутствует важное дополнение - "программа" и "другая программа" находятся в равных условиях по возможностям запуска друг-друга, что в жизни встречается нечасто.

как минимум, "другая программа" обычно не осведомлена о том, что "программа" существует :)
be_unafraid
Jul. 31st, 2005 02:09 pm (UTC)
Шо-то я не вижу важности дополнения =P
cyberguss
Aug. 7th, 2005 01:16 am (UTC)
машина Тюринга не может проверить машину Тюринга 8))
be_unafraid
Aug. 7th, 2005 04:40 pm (UTC)
А теперь слайды! (с) =)
zhuc
Nov. 15th, 2005 02:23 am (UTC)
Кто бы мне объяснил глубинный смысл вот этого доказательства
http://en.wikipedia.org/wiki/Halting_problem
Еще есть через diagonalization, там все тоже понятно, но я не могу постигнуть, почему это доказывает именно halting problem.
ex_neo_is_fl156
Dec. 3rd, 2005 07:03 am (UTC)
А что именно не понятно?
ex_neo_is_fl156
Dec. 3rd, 2005 07:07 am (UTC)
Классная теорема :) Правда, она больше нравится в такой формулировке: "Существует рекурсивно перечислимое, но нерекурсивное множество" :)
ex_neo_is_fl156
Dec. 3rd, 2005 07:07 am (UTC)
Вообще, теория алгоритмов - мой любимый предмет, после алгебры.
( 14 comments — Leave a comment )