Доказательство того, что существует, по крайней мере, одна тривиальная компьютерная программа, которая не может существовать

Самые красивые математические доказательства, вып. 2, Максим Кутт.

На прошлой неделе была статья «Неужели одни бесконечности больше других?» и диагональный аргумент Кантора. На этой неделе я хочу поделиться одной из моих любимых проблем теоретической информатики.

«Детали четырех ранних компьютеров, 1962 год. Слева направо: плата ENIAC, плата EDVAC, плата ORDVAC и плата BRLESC-I, демонстрирующие тенденцию к миниатюризации».

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

Определение H, Невозможная компьютерная программа

Мы определяем компьютерную программу P (i) как список инструкций P, которые при выполнении с входом i дают выход o.

Например,

это программа, которая суммирует два числа, которые вы даете в качестве входных данных, и,

это программа, которая использует другую программу - P_add - в качестве входных данных и передает эту программу двум другим входным данным. Это делает то, что делает P_add (a, b) и удваивает это.

Когда программа выполняется, она может застрять, работать вечно и никогда ничего не выводить, например, программа P_sum, которая переходит к сумме всех натуральных чисел, будет продолжать добавлять натуральные числа вечно, даже не заканчивая работу (то есть останавливаться) и вывод результата.

Теперь предположим, что существует программа H (P, i), которая принимает в качестве входных данных список инструкций P программы P (i), а i - ввод P (i) и выводит 1, если P (i) остановитесь в некоторой точке и 0, если P (i) застрянет и будет работать вечно. Проще говоря,

Почему список логических инструкций H не может существовать

На основании доказательства Алана Тьюринга в статье «О вычислимых числах с приложением к проблеме Энтшайдунгса» -1937 мы докажем, что H не может существовать.

Исходя из предположения о существовании H, мы создаем программу X (P), которая выполняется вечно тогда и только тогда, когда H (P, P) = 1, и останавливается тогда и только тогда, когда H (P, P) = 0. Другими словами,

Теперь мы можем рассмотреть возможность предоставления X (i) своего собственного списка инструкций X в качестве ввода: X (X).

Следовательно, X (X) работает вечно тогда и только тогда, когда H (X, X) = 1 и X (X) останавливаются тогда и только тогда, когда H (X, X) = 0. Другими словами,

У нас есть противоречие! Мы показали в Reductio ad absurdum, что H не может существовать, поскольку его существование приводит к абсурдным выводам.

Следовательно, компьютерная программа, которая может определить, будет ли любая компьютерная программа, заданная для какого-либо ввода, зависать и работать вечно или завершить работу, невозможна. Существует по крайней мере одна компьютерная программа, решающая логическую проблему, которая не может существовать.

Ссылки, Алан Тьюринг. «О вычислимых числах с приложением к проблеме Entscheidungs». 1937.

Я Макс Кутте, соучредитель Relativty.com, VR-гарнитуры, которую я разработал с нуля, из которой я открыл исходный код и аппаратное обеспечение. Следуй за мной по щебетать @maxcoutte.