В 1928 году математик по имени Давид Гильберт бросил вызов математическому сообществу – предложил создать алгоритм, который, взяв логичное утверждение, мог бы ответить «да» или «нет» на вопрос о том, верно ли это утверждение. Если бы такой алгоритм был создан, это означало бы, что неразрешимых проблем не существует. Таким образом, Entscheidungsproblem (сюрприз! По-немецки это слово означает «проблема решения») формулируется так: «Существует ли алгоритм для ответа на вопрос “возможно ли решение математической проблемы”?» Ответ – нет, не существует. Но если вы спросите специалиста по компьютерам, он ответит: «Пока не существует».
