4. «Физика» используемой модели работы алгоритмов. Сравнение с машиной Тьюринга

. К оглавлению . Показать весь текст .

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

Во-первых, не одна «лента», а множество «полулент» Тьюринга, которые все своим началом сходятся в одной точке к «процессору». Это – строки (и числа, которые представлены в виде строк). Каждой переменной соответствует своя «полулента» Тьюринга, начало которой соответствует 1-му символу данной строки (если строка не пустая).

Во-вторых, в данной модели нет «тележки», которая может как угодно долго «блуждать» вдали от начальной точки. 

Чтобы получить информацию из нужного места строки – надо каждый раз «дойти» до нужного места строки, забрать нужную информацию и доставить её обратно к «процессору». 

Чтобы сохранить (записать) информацию в нужном месте строки – надо забрать её у «процессора» (полагаем, что она уже доставлена и есть в «нулевой» точке), доставить в нужное место строки и записать там вместо имеющейся там информации. 

Чем дальше от начала строки находятся нужные нам символы – тем дольше (прямо пропорционально дольше) до них добираться. Добираемся мы с целью чтения этих данных или замены этих данных на нужные данные.

В некотором смысле в используемой тут модели алгоритмов тоже есть «тележка» – но она каждый раз возвращается в исходное положение. Это вполне соответствует физике доступа к данным в современных компьютерах – данные находятся на некотором удалении от процессора и скорость доступа к ним зависит от расстояния до них – потому что быстрее скорости света сигнал не передаётся. 

Всякие идеи о «произвольном доступе», когда время зависит как логарифм от количества данных – ошибочны в реальном мире. В лучшем случае скорость доступа пропорциональна кубическому корню от количества данных – если мы располагаем всю информацию в 3-х измерениях. 

Хотя для реальных компьютеров с ограниченной памятью и временем доступа до любого байта в пределах малого времени t – вполне можно использовать в качестве приближения модель «произвольного доступа», конечно. И тогда время работы будет приблизительно пропорционально количеству операций процессора – независимо от того, где в компьютерной памяти расположены используемые данные.

Но в используемой тут модели мы располагаем данные на «лучах» данных – когда каждая переменная имеет своё начало в самом «быстром» для доступа месте, а для символов, которые дальше – время доступа растёт прямо пропорционально удалённости. 

Есть ситуация, когда время работы машины Тьюринга оказывается неполиномиально больше, чем время работы реальной вычислительной машины. Например, на «вход» для вычисления поданы 3 переменных:

X_1 X_2 X_3

При этом размер переменных X_2 и X_3 неполиномиально велик относительно размера переменной X_1, а требуются из этих X_2 и X_3 для вычислений только данные, расположенные в их началах, с размером не большем, чем 100 * len(X_1), например. При этом время на обработку этих данных для обычной вычислительной машины составило бы 10000 * len(X_1) шагов работы. 

Как при помощи машины Тьюринга обеспечить вычисление с такой же скоростью? Никак, если символы этих переменных расположены на ленте Тьюринга последовательно друг за другом. Потому что для доступа к последней «большой» переменной X_3 «тележка» должна была бы «проехать» всю длину переменной X_2, которая неполиномиально велика относительно размера переменой X_1 и, следовательно, сколь угодно больше, чем 10000 * len(X_1) при достаточно большом len(X_1). 

Разумеется, можно принять такое соглашение о кодировании «входа» на ленте, что сначала идут первые три символа каждой из трёх переменных, затем – вторые три символа каждой из трёх переменных и т.д. Но это получается иное программирование – куда менее удобное, чем в случае использования предложенной в данной статье модели для работы алгоритмов. 

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

Оппонента удалось убедить лишь сославшись на «соглашение о способе кодирования на ленте в момент остановки» в книге Дж. Булос, R Джеффри – «Вычислимость и логика», Глава 3. Машины Тьюринга, текст в разделе решения для упражнения 3.2.

В используемой тут модели алгоритмов вопрос с очисткой переменной решается за один шаг – при помощи, например, установки некоторого «специального символа» в то место на «луче данных», начиная с которого символы на данном «луче данных» считаются отсутствующими. И этот символ не входит в набор символов, используемых алгоритмами. Об этом уже упоминалось в разделе 1, когда обсуждался текст программы и операция присваивания – в частности. 

В-третьих, программа (текст программы) в разбираемой модели – такая же строка, что и все остальные данные. Это принципиальный момент, потому что эти данные (текст самой программы) имеется всегда у программы при её работе – наряду с данными «входа». И наличие таких данных будет играть принципиальную роль для дальнейшего исследования в следующих статьях. 

В модели Тьюринга время тратится только на саму операцию с данными, но не учитывается время на доступ к нужной команде, которая должна исполняться в данный момент. В используемой же тут модели время доступа к команде тоже учитывается, потому что между программой и данными нет разницы с точки зрения доступа к ним. И переход по команде goto, например, будет тем дольше, чем дальше от «процессора» находится метка в той строке, которая содержит текст программы.

Но ничто не мешает считать, что подпрограммы располагаются на специальных «лучах данных» или точнее «лучах подпрограмм» (каждый – на своём) и оператор goto способен совершать переход и в начало этих вспомогательных «лучей подпрограмм». Тогда время работы подпрограмм оказывается таким же, как и в том случае, когда они используются отдельно от данной основной программы – с минимальной корректировкой в программном тексте – заменой оператора goto возврата в основную программу на оператор остановки «.». 

Кстати, напоминаю, что время на возврат к исполнению основной программы мы условились считать временем работы не подпрограммы, но частью времени работы основной программы – см. пункт 3 в конце предыдущего раздела.

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

На этом 2-я статья, посвящённая реализации программы Гильберта для теории алгоритмов – закончена.