Entscheidungsproblem
Вопрос о том, может ли механическая процедура решать, какие математические утверждения следуют из аксиом, — и отрицательный ответ, по случайности изобретший компьютер.
Давид Гильберт и Вильгельм Аккерман поставили его в учебнике логики 1928 года: существует ли процедура, которая для любого утверждения логики предикатов определяет, общезначимо ли оно? Гильберт ждал ответа «да». Его программа должна была сделать математику полной, непротиворечивой и разрешимой, причём третий пункт был самым осязаемым. Алгоритм, выносящий вердикт по теоремам, закрыл бы математику как область исследований и превратил её в вращение ручки.
Ответ пришёл в 1936 году сразу с двух сторон. Алонзо Чёрч использовал лямбда-исчисление, Алан Тьюринг — воображаемую машину с бесконечной бумажной лентой. Оба сказали «нет». Части логики разрешимы — например, пропозициональная, через таблицы истинности, — но логика предикатов в целом нет.
Для истории вычислений важно, что Тьюрингу пришлось сделать сначала. Чтобы доказать, что никакая механическая процедура не подойдёт, нужно сказать, что это такое. Его определение — лента, головка, таблица состояний — стало машиной Тьюринга и первым точным описанием того, что такое компьютер. Компьютер появился как побочный эффект отрицательного результата.