[МУЗЫКА] [МУЗЫКА] Однако физические ограничения реального мира — не единственное препятствие безграничному росту нашим вычислительным возможностям. Для того, чтобы разобраться с этим вопросом, давайте попробуем понять, что такое цель вычислений. Цель вычислений — это всегда определение значений некоторой функции. Если вы минуту подумаете над этим вопросом, вы поймете, что любой алгоритм вычисляет какую-то функцию, преобразующую множество входных данных алгоритма в множество его выходных данных. А что такое алгоритм? Ответ на этот вопрос наиболее полно сформулировал в 1936 году английский ученый Алан Тьюринг: «Алгоритм — это детерминированная машина Тьюринга». Ну, вы помните — бесконечная лента с символами из конечного алфавита, конечный набор состояний, конечный набор правил для смены этих состояний. Тогда же, в то же время, многие исследователи задавались вопросом, существует ли физическое устройство с репертуаром больше, чем у машины Тьюринга? Ответ на это вопрос известен как Тезис Чёрча-Тьюринга, и ответ этот отрицательный. Тезис Чёрча-Тьюринга утверждает, что не существует даже гипотетического устройства с репертуаром больше, чем у детерминированной машины Тьюринга. Давайте попробуем понять, что это значит. Например, это значит, что даже вычислительные возможности человека подвергаются тем же ограничениям, которым подвергается машина Тьюринга. Что это за ограничения? Давайте для начала попробуем понять, сколько всего возможно разных машин Тьюринга. Каждая машина Тьюринга, каждый алгоритм может быть в какой-то кодировке, сформулированной как строка конечное длины — например, строка конечной длины из нулей и единичек. Мы также знаем, что строка конечной длины из нулей и единичек кодирует какое-то натуральное число, причем разные строки кодируют разные натуральные числа. Получается, что разных машин Тьюринга, разных алгоритмов столько же, сколько натуральных чисел, то есть счетная бесконечность. А сколько разных функций, для которых нам могут потребоваться алгоритмы? Итак, сколько всего функций из N в N? Для ответа на это вопрос давайте рассмотрим произвольное число a из отрезка [0, 1]. Запишем это число, например, в двоичной системе исчисления. [БЕЗ_ЗВУКА] Получается такая вот бесконечная строка из нулей и единиц. Определим теперь функцию f(a), которая от любого натурального числа k будет возвращать a k-тое. Эта функция из натурального ряда в один бит. И понятно, что разные значения a задают для нас разные функции. Поскольку разные значения a на отрезке {0, 1} континуум, то и функция такого вида получается минимум континуум. Ну и такого, соответственно, вида тоже минимум континуум. На самом деле ровно континуум. Можно обратную процедуру провести и каждой функции сопоставить вещественное число. Получается, что множество функций больше, чем множество алгоритмов. Причем не просто больше. Если мы, например, вот так вот нарисуем весь континуум функций, то множество вычислимых функций на этой картинке будет (я сейчас нарисую) выглядеть как-то вот так. Вычислимые функции, те функции, которые можно вычислить на машине Тьюринга, имеют меру нуль по сравнению с общим функций. Получается, что в этом богатом разнообразном мире мы не можем вычислить практически ничего. А может быть, и не надо? Может быть, все эти невычислимые функции нам не интересны? Оказывается, нет. В той же самой работе, в которой Тьюринг определил математическую модель вычислений, он привел пример невычислимой функции, которая могла бы быть полезна. Он показал, что не существует алгоритма A, который мог бы в некотором смысле анализировать другие алгоритмы. То есть принимая на вход, например, двоичное представление алгоритма x и входные данные для него y, он возвращал бы нолик если x от y зависает и единичку, если нет. Чтобы показать, что подобный алгоритм нельзя написать в общем виде, давайте определим алгоритм A' (назовем его «анализатор»), который тоже принимает на вход двоичные представления алгоритма и входные данные к нему, но возвращает нолик, если x от y зависает, а в противном случае зависает сам. Ясно, что имея алгоритм А мы можем легко реализовать алгоритм А'. Далее Тьюринг воспользовался довольно остроумной модификацией диагонального аргумента Кантора. Он предложил ввести алгоритм «диагонализатор», действующий следующим образом: [БЕЗ_ЗВУКА] Диагонализатор вызывает наш анализатор, подавая ему на вход двоичное представление алгоритма x, и алгоритм x тоже подает на вход двоичное представление алгоритма x. Давайте посмотрим, чему будет равен вызов диагонализатора от него самого. [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] Далее по определению A' диагонализатор должен вернуть 0 если он зависает или зависнуть в обратном случае. Мы имеем противоречие «диагонализатор должен вернуть 0» и «диагонализатор должен зависнуть», которое приводит нас к выводу, что изначальная предпосылка неверна. Изначальной предпосылкой было существование алгоритма А. Кстати говоря, генерация последовательности случайных чисел также не входит в репертуар детерминированной машины Тьюринга, поскольку она детерминирована, а для квантового компьютера такая задача легко выполнима. [БЕЗ_ЗВУКА]
