dmitgu

Categories:

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-я статья, посвящённая реализации программы Гильберта для теории алгоритмов – закончена. 

Error

default userpic

Your reply will be screened

Your IP address will be recorded 

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.