2.VI. Алгоритмы, не сводимые к (частично) рекурсивным функциям и арифметике
. К оглавлению . Показать весь текст .
За неимением теории строк, теория первого порядка, в которой «представимы» алгоритмы в современных книгах по теории алгоритмов - это арифметика, а представимость алгоритмов в арифметике - это представимость частично рекурсивных функций (ЧРФ далее в этом подразделе). Но множество ЧРФ не включает в себя все необходимые для исследования в теории алгоритмов алгоритмы.
Дело в том, что примитивно рекурсивные функции (ПРФ далее в этом подразделе) используют только такие базовые функции, и такие операторы подстановки и примитивной рекурсии, которые имеют дело только с целостными значениями переменных. Ничего в этом плане не меняет и оператор минимизации - расширяющий множество примитивно рекурсивных функций до множества ЧРФ.
Напомню базовые функции и способы создания из них всех остальных функций данного множества, взятые из Википедии (на начало дня 25.02.2020):
Начало цитаты
К числу базовых ПРФ относятся функции следующих трёх видов:
1. Нулевая функция 0 - функция без аргументов, всегда возвращающая 0.
2. Функция следования S одного переменного, сопоставляющая любому натуральному числу непосредственно следующее за ним натуральное число x+1.
3. Функции I_n^m, где 0 < m ≤ n, от n переменных, сопоставляющие любому упорядоченному набору x_1, … , x_n натуральных чисел число x_m из этого набора.
Операторы подстановки и примитивной рекурсии определяются следующим образом:
Оператор суперпозиции (иногда - оператор подстановки). Пусть f - функция от m переменных, а g_1, … , g_m - упорядоченный набор функций от n переменных каждая. Тогда результатом суперпозиции функций g_k в функцию f называется функция h от n переменных, сопоставляющая любому упорядоченному набору x_1, … , x_n натуральных чисел число
h(x_1, … , x_n) = f(g_1(x_1, … , x_n), … , g_m(x_1, … , x_n)).
Оператор примитивной рекурсии. Пусть f - функция от n переменных, а g - функция от n+2 переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций f и g называется функция h от n+1 переменной вида
h(x_1, … , x_n, 0) = f(x_1, … , x_n),
h(x_1, … , x_n, y + 1) = g(x_1, … , x_n, y, h(x_1, … , x_n, y)).
В данном определении переменную y можно понимать как счётчик итераций, f - как исходную функцию в начале итерационного процесса, выдающего некую последовательность функций n переменных, начинающуюся с f, и g - как оператор, принимающий на вход n переменных x_1, … , x_n, номер шага итерации (y), функцию h(x_1, … , x_n, y) на данном шаге итерации, и возвращающий функцию на следующем шаге итерации.
…
ЧРФ определяется аналогично ПРФ, только к двум операторам суперпозиции и примитивной рекурсии добавляется ещё третий оператор - минимизации аргумента.
Оператор минимизации аргумента. Пусть f - функция от n натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции f называется функция h от n-1 переменной, задаваемая следующим определением:
h(x_1, … , x_{n-1}, 0) = min y, при условии f(x_1, … , {n-1}, y) = 0
То есть функция h возвращает минимальное значение последнего аргумента функции f, при котором её значение равно 0.
…
Общерекурсивная функция - частично рекурсивная функция, определённая для всех значений аргументов.
Конец цитаты
Как видим, никакая базовая функция не может работать с какой-то частью своего входного аргумента, не зная его «хвоста». И любая производная от базовых функций функция на базе указанных выше правил - тоже не может оказаться функцией, использующей свой аргумент частично, не «читая» его целиком. Действительно:
Нулевая функция не имеет аргументов, Функции I_n^m использует только готовые аргументы, никак не получая из аргумента часть его значения, функция следования - увеличивает аргумент на 1. Чтобы это сделать - необходимо прочитать аргумент целиком.
Итак, базовые функции работают только, используя (читая, в частности) аргумент целиком.
Теперь разберем методы построения новых функций из базовых функций.
Оператор суперпозиции никак не меняет того, как составляющие его функции работают с аргументами, и сводится к ним в плане работы с аргументами. Оператор примитивной рекурсии - уменьшает аргумент при своем построении на 1. Но для получения значения, которое меньше входного аргумента на 1 надо прочитать входной аргумент целиком.
Таким образом, ПРФ могут работать только с целыми значениями входных аргументов. Потому что они строятся на основе базовых функций, которые работают с целостными значениями входных аргументов. А методы построения ПРФ сохраняют тот же метод работы со значениями входных аргументов - читая и используя эти значения целиком.
Меняет ли что-то в этой ситуации оператор минимизации? В смысле входных аргументов он всего лишь сокращает их число.
Таким образом, ЧРФ работают со значениями входных аргументов только целостно - используя (читая, в частности) все входные данные в каждом используемом ими аргументе. «Используемые» аргументы не следует путать с переданными функции аргументами: функция I_n^m, например, использует только один аргумент, но тоже целиком.
Это значит, что в рамках множества ЧРФ невозможно отличить алгоритм, использующий только первый символ в своём входном аргументе от алгоритма, который работает со всем своим входным аргументом. Поэтому решать вопрос об эффективности (скорости) работы алгоритмов, находясь в рамках ЧРФ невозможно в общем случае:
Ведь разница между размерами одного символа (или любого ограниченного их числа) и возможным размером входного аргумента, не может быть ограничена не то, что каким-либо полиномом от этого ограниченного числа, но вообще никакой функцией.
Вот в теории строк 1-я же аксиома сообщает о возможности разбиения строки в позиции с произвольным номером i с выделением начальной части beg(a, i):
(1) a = beg(a, i) ⋅ end(a, i ′ )
Мало того, что строка a в теории строк может быть представлена как
a = b ⋅ Unknown
Но и работать со строкой a = b ⋅ Unknown в теории строк можно - при определенных условиях - так, словно вместо всей строки a есть только её начало b. Эти условия видны в следствии (с.9.2) для работы со строкой при помощи функции Comp(), эти условия представлены функциями IsIns(q_a, i, q_b) и IsStr(q_a, i, j), как будет доказано в следующем подразделе.
Но помимо теории строк - ещё и в реальном мире у нас есть возможность «локальной» работы со строкой. Например: я могу прочитать только начало книги и решить, что она мне не годится. И для принятия такого решения мне нет нужды читать книгу до конца, потому что начало книги несёт такую информацию, которая никак не меняется от дальнейшего текста. И время на чтение этого начала я трачу одинаково вне зависимости от того - целая книга у меня в руках, или только вырванный из книги блок её первых страниц.
Но для того, чтобы в теории я мог воспользоваться возможностями «локальной работы» со строками из реального мира, мне нужно иметь в теории соответствующие инструменты. А таких инструментов нет в формализме частично рекурсивных функций.
Проблема ЧРФ при работе с входными данными чрезмерно (сколь угодно «чрезмерно») большого размера, которые не используются алгоритмом в своей работе, кроме некоторой начальной части этих данных, порождает формулировки вроде:
«Подтверждающий сертификат должен иметь размер, ограниченный полиномом от размера проверяемого слова» и «Если среди сертификатов допустимого размера нет сертификата, который является подтверждающим для данного слова, то данное слово не принадлежит языку».
Возникает вопрос: а кто/что проверяет - является ли допустимым размер у проверяемого сертификата? Разве проверка такого рода не является вычислением? И разве время на эту проверку не столь же уместно учитывать в качестве времени работы алгоритма проверки, как и время после того, когда недопустимые по своим размерам сертификаты отброшены?
Разумеется, время на проверку размеров сертификатов учитывать надо. И правильная формулировка состоит в том, что время работы алгоритма проверки не должно зависеть от размера чрезмерного по своим размерам сертификата. Но контроль размера и выбраковку сертификатов с чрезмерно большими размерами алгоритм проверки осуществляет самостоятельно.
И выбраковка чрезмерно больших сертификатов должна осуществляться за время, полиномиальное от критического («граничного») размера сертификата - при чтении первого символа, находящегося вне допустимых - для размера входных данных - пределов. А вовсе не в результате обработки всего «входа».
Но в рамках ЧРФ решить подобную задачу невозможно. Однако одной заменой ЧРФ на что-то более выразительное для теории алгоритмов обойтись не удастся, как мы увидим чуть ниже в данном подразделе - арифметика тоже не обладает необходимой для теории алгоритмов выразительностью.
Поэтому необходимо создать такую теорию (теорию строк, например) и такую модель исполнения алгоритмов (2-я статья, которая будет после данной), которая устраняла бы неразрешимую в рамках ЧРФ проблему работы с «входными данными», которые используются алгоритмами лишь в незначительной начальной части этих данных.
К данному подразделу мы уже в достаточной степени построили теорию строк для того, чтобы доказать, что арифметика (не только теория Пеано, но и её любые возможные арифметические расширения) недостаточно выразительна для решения вопросов теории алгоритмов в общем случае.
(м.9.1) В теории строк с односимвольным алфавитом (l_ChrLim = 0) невозможно в общем случае представить работу алгоритмов со строками многосимвольного алфавита таким образом, чтобы размер логического вывода для результата работы такого алгоритма был в полиномиальных (или любых иных) пределах относительно времени работы этого алгоритма.
Доказательство.
Пусть у нас есть алгоритм проверки русского правописания, который должен отвергать (возвращая в качестве результата своей работы ноль, например) предложенный для проверки текст сразу, как только обнаружит ошибку в этом тексте. Пусть на вход данному алгоритму подан роман, первое же слово в котором начинается на «Ъ».
Разумеется, наш алгоритм отвергнет данный роман как неграмотно написанный по первой же его букве. Потому что в русском языке нет слов, которые начинаются на «Ъ». Замечу, что тут речь идёт о работе алгоритма со строкой, составленной на базе многосимвольного алфавита. И для простоты будем считать, что на любую другую букву русское слово начинаться может, что проще реального русского языка, где есть ещё буква «Ь».
Вопрос: можно ли в односимвольной теории строк построить такое представление для данного алгоритма проверки (сопоставив как-то многосимвольным строкам строки из символов односимвольного алфавита), что логический вывод данного результата (доказательство истинности результата, равного нулю) имел бы размер, не выходящий за некие полиномиальные ограничения относительно времени работы данного алгоритма?
Если бы это было так, то в логическом выводе не мог бы присутствовать весь роман, вообще говоря. Потому что размер романа может быть сколь угодно велик по сравнению с «Ъ» и временем работы алгоритма проверки.
Если же предположить, что в логическом выводе теории строк с односимвольным алфавитом присутствует лишь часть строки, то эта часть состоит из одних и тех же символов - будем считать «0», например. А размер всей строки, которая соответствует роману - неизвестен.
Допустим, логический вывод дает нужный нам результат 0 (отвергая роман как ошибочный) на основании подстроки «000…0» длиной в фиксированное количество n символов «0». Количество символов, представляющих весь роман - неизвестно. Это значит, что про роман, который представлен строкой, в которой есть фиксированное число n символов «0» заранее известно, что он начинается на «Ъ». Я тут упрощаю (это напоминание), потому что при реальном русском языке ошибка будет и при «Ь», но разбираемая модель понятна.
А это означает, что все романы, которые представлены строками односимвольного алфавита длиной от n символов начинаются на символ «Ъ». А это означает, что все романы, которые не начинаются на символ «Ъ» должны соответствовать конечному числу вариантов, которые могут выразить строки (из символа односимвольного алфавита) длиной меньше, чем фиксированное число n символов «0».
Но таких романов - бесконечное количество, а вариантов разных строк, длина которых меньше n - конечное количество. Поэтому случай из предыдущего абзаца невозможен.
Полученное противоречие доказывает, что предположение о том, что:
В односимвольной теории строк логический вывод о том, что многосимвольный текст начинается на некий «запрещённый» символ может обойтись лишь частью строки, которая содержится в строке односимвольного алфавита, соответствующей данному тексту многосимвольного алфавита -
Является ошибочным.
Поскольку размер текста в сравнении с размером одного символа может быть как угодно велик, то мы доказали, что размер логического вывода и время на его проверку в односимвольной теории строк может быть сколь угодно велики в сравнении со временем работы алгоритма проверки. Метатеорема доказана.
(м.9.2) В арифметике невозможно в общем случае представить работу алгоритмов со строками многосимвольного алфавита таким образом, чтобы размер логического вывода для результата работы такого алгоритма был в полиномиальных (или любых иных) пределах относительно времени работы этого алгоритма.
Доказательство.
Выразительность арифметики не превосходит выразительности теории строк с односимвольным алфавитом, потому что арифметика является частью теории строк. Поэтому то, что невозможно логически вывести в теории строк с односимвольным алфавитом - невозможно вывести и в арифметике. Теорема доказана.
Как видим, благодаря теории строк удаётся понять недостаточную выразительность арифметики для того, чтобы пытаться решать в её рамках вопросы теории алгоритмов. И это понимание возникает за счёт «взгляда со стороны» на саму теорию строк, а уже поняв разницу между разными её вариантами - удаётся понять и в чём недостаточная выразительность арифметики для теории алгоритмов. И, разумеется, приведённые доказательства метатеорем не являются формальными и не могут быть формализованы в рамках теории строк - потому что это информация не теории строк, а про теорию строк.
Из метатеоремы (м.9.2) следует, что гёделевы номера - которые определяются в арифметике в качестве способа представить тексты логических формул, логических выводов, функций арифметики и т.п. - являются недостаточно выразительными для задач теории алгоритмов, как и сама арифметика.
А почему нельзя считать нужным представлением формулу, выражающую то, что нужная строка начинается на «Ъ»?
Просто потому, что мы в реальности не можем сказать - есть ли «Ъ» в многосимвольной строке, соответствующей данной «односимвольный» строке - не прочитав данную строку односимвольного алфавита до конца. А раз это невозможно в реальности, то невозможно и в теории - если эта теория непротиворечива и, если соответствующие ей функции мы строим в нашей реальности в возможных в этой реальности интерпретациях.
Но в любом случае мы опираемся на реальность в доказательстве метатеорем. В частности - не можем себе представить, как можно было бы решить вопрос с «Ъ» в начале, не прочитав всю строку из символа односимвольного алфавита.
В следующем разделе мы разберем связь между теорией строк и теорией Пеано (или любым расширением теории Пеано). И там будут представлен и вариант аксиоматизации для «односимвольной» связи строк и числе.
Для арифметики, получается, совершенно закономерно иметь интерпретацию, в которой необходимо читать число до конца. Потому что то, как «зашифровано» число - это никак не задано в самой арифметике. И поэтому ЧРФ никак не «портят» арифметику тем, что работают с входным аргументом только целиком - потому что арифметика «поступает» точно так же.
А в чём разница с многосимвольным алфавитом? В том, что в любой строке данной длины n из символов многосимвольного алфавита есть ещё варианты, кроме одного данного. И «клинча» - «тогда и остальные такие же» - не возникает. А вот при односимвольном алфавите логический вывод, сделанный на основании части длинной n от всей строки (произвольного размера), будет «таким же» для любых строк, имеющих длину больше или равную n.
Кстати, даже «частичное чтение» не позволило бы в арифметике сделать вывод, что число больше или равно числу прочитанных «символов». Действительно, ведь на базе арифметики можно аксиоматизировать следующую связь между числами и строками при односимвольном алфавите:
Если n - чётное число, но не степень 2, то число записано в виде строки из символов «0» длиной n+1: «00…0». Если n - нечётное число, то число n записано как строка из символов «0»: «00…0». И количество символов «0» в этой строке (длина строки) будет 2^{n}+1. А вот число 2^n будет записана тоже как строка из «0», но длина строки в этой записи будет n+1.
И тогда нет возможности в общем случае по чтению нескольких начальных символов утверждать, что число больше некоторого числа - в общем случае. Потому что оно может быть равно нечётному числу, хотя символов ты уже прочитал больше, чем данное нечётное число, но прочитал их пока меньше, чем до конца.
Заметим, что в реальности строки обладают свойством доступности для частичного чтения. Теперь недостаточная выразительность арифметики стала обоснованной в результате доказательства метатеоремы (м.9.2).
Если мы посмотрим в современные учебники теории алгоритмов, то увидим, что вычислимость на машине Тьюринга рассматривается в духе стандартной интерпретации, то есть, когда «входные аргументы» представлены последовательностью «счётных палочек», разделённых пустой клеткой (условно скажем «символом нуля»), например. Для нуля (речь про обозначение числа, а не про пустую клетку-разделитель) используется «1», для 1 - «11», для 2 - «111» и т.д.
Я проверил по книгам:
«Теория алгоритмов» В.И. Игошин, «Курс математической логики и теории вычислимости» А.С. Герасимов, «Вычислимость и логика» Дж. Булос, Р. Джеффри.
То есть, не идёт речь о позиционном представлении чисел, хотя все реальные компьютеры работают именно с позиционным представлением чисел.
Понятно, что такое содержание учебников связано с отсутствием теории строк во время их написания. А в рамках арифметики (теории Пеано, например) просто нет средств для того, чтобы представить строки и записать числа в позиционном виде.
И представимость алгоритмов машины Тьюринга в арифметике доказывается не напрямую, а через ЧРФ. При этом машина Тьюринга работает со «стандартной интерпретацией» когда числа представлены блоками единиц. Про время работы вопрос не ставился. «Представимость» алгоритмов доказывалась в первой половине 20 века, в период великих логических открытий (неполнота, неразрешимость, теории первого и второго порядка, программа Гильберта и т.д. и т.п.). И всех интересовал вопрос возможности или невозможности тех или иных «вычислений» в принципе, независимо от времени этого вычисления - важно лишь, чтобы это время было конечным.
Тезис Чёрча понимался как возможность свести произвольное вычисление (которое завершается за конечное время) к некоторой ЧРФ, чтобы в итоге вычисления получить правильный результат - независимо от того времени, которое потребуется для этого - если время конечно. И независимо от размера логического вывода для доказательства того, что будет получен правильный результат - если размер логического вывода конечный.
И тезис Чёрча оказывается ошибочным, если понимать его как возможность свести произвольное вычисление к некоторой ЧРФ, без потери важных для теории алгоритмов свойств вычисления.
Что же теперь будет построено вместо ЧРФ? Будет построена - в статье номер 2 - «машина компьютерных алгоритмов» (МКА далее), и в ней будет реализована возможность частичного чтения входного аргумента.
Можно ли в качестве замены ЧРФ взять машину Тьюринга? Возможно - но это не удобно. И если в рамках прежнего построения «представимости» сопоставление между работой машины Тьюринга и теорией Пеано шло через ЧРФ и касалось только ЧРФ, то заменяя ЧРФ на МКА мы только упростим ситуацию и сделаем необходимое исправление - взяв верный метод с учётом задач теории алгоритмов, вместо неверного метода - в рамках указанных задач - который использовал ЧРФ.