Приветствия. Дейкстра писал, что даже несколько строк, казалось бы, простого кода могут быть безнадежно неоднозначными. По крайней мере, в одной работе, которую я не могу найти сейчас, чтобы спасти мою жизнь, он привел небольшой пример программы, чтобы продемонстрировать эту двусмысленность. Кто-нибудь может указать мне на его статью, где он включает один из этих примеров?
Прочитайте это:
http://en.wikipedia.org/wiki/Halting_problem#Recognizing_partial_solutions
http://www.cs.ucsb.edu/~pconrad/cs40/08S/notes/ имеет хороший охват; поиск "проблема остановки"
Существует несколько форм существенного противоречия.
def halts( code_block ):
# Some magical code
def whistler():
while halts(whistler):
sys.whistle( 1 )
Свисток "свистит" ноль, один раз или бесконечное количество раз?
Если halts()функция определяет, что функция, whistlerкажется, останавливается, функция whistlerне может остановиться.
Если halts()функция определяет, что функция whistlerне появляется как остановка, функция whistlerостанавливается.
Следовательно, halts()функция не может существовать.
FILE_NOT_FOUND;)Вы уверены, что статья была написана Дейкстрой? Размышления о доверии доверию Кена Томпсона звучат так, как будто это то, о чем вы подумали. Он демонстрирует, как абсолютно простые, понятные и правильные программы могут в итоге сделать что-то совершенно неожиданное, чего вообще не видно в источнике. Даже если это не то, о чем вы думали, это стоит прочитать статью.
Если вам нужны отличные примеры коротких программ с удивительным поведением, то закулисный конкурс на Си - это здорово. Например, посмотрите на победителя 2008 года . Задача состояла в том, чтобы написать программу командной строки, чтобы убрать часть изображения таким образом, чтобы изображение было визуально очищено, но в файле сохранена некоторая информация об отредактированной части изображения. И таким образом, чтобы ваш код мог пройти проверку кода. (Вы можете выбрать формат, в котором хранится изображение.)
источник