Невычислимые функции

Программа выполняет единственное действие: управляет преобразованием некоторого исходного набора двоичных разрядов, который будем называть входным, в другой набор двоичных разрядов, именуемый выходным. Связь, существующая между этими наборами, называется функцией.

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

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

Например, невычислимой по Тьюрингу является функция, которая сопоставляет геделевскому номеру программы значение переменной X равное 0 или 1, в зависимости от того, является данная программа самоостанавливающейся или нет. Геделевским номером программы называется связанное с данной программой число, а самоостанавливающейся называется программа, если она обязательно остановится в случае ее запуска с исходным значением в первой переменной, равным значению геделевского номера этой программы, а все ее остальные переменные будут иметь исходное значение 0. Любая программа является либо самоостанавливающейся, либо не самоостанавливающейся.

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

while (X< >0) do {}

В результате будет получена новая программа, которая должна быть или самоостанавливающейся, или не самоостанавливающейся. Однако в действительности, как мы скоро увидим, она не может быть ни той ни другой. В частности, если эта новая программа самоостанавливающаяся и мы запустим ее с ее собственным геделевским номером в качестве входного значения, то выполнение этой программы дойдет до добавленной нами команды while со значением переменной X, равным 1. До этого момента новая версия программы идентична исходной программе, которая выдавала 1 в том случае, если в качестве входного значения ей указывался геделевский номер любой самоостанавливающейся программы. Но в этой точке выполнение программы зациклится, поскольку структура while-do не позволяет уменьшать значение переменной X в теле цикла. Однако это противоречит нашему исходному предположению о том, что новая программа является самоостанавливающейся. Следовательно, мы приходим к заключению, что данная программа не является таковой.

В то же время, если новая версия программы не является самоостанавливающейся и мы начнем ее выполнение с ввода ее собственного геделевского номера, она подойдет к добавленному нами оператору while со значением переменной X, равным 0. Это произойдет вследствие того, что команды, предшествующие оператору while, составляют исходную программу, которая даст на выходе 0 только в том случае, если данная программа не является самоостанавливающейся. В этом случае цикл while будет просто проигнорирован, и программа завершит свое выполнение. Но это является свойством самоостанавливающихся программ, и мы вынуждены заключить, что наша новая программа самоостанавливающаяся, подобно тому, как ранее мы были вынуждены признать ее не самоостанавливающейся.

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