Об асимптотике сложности машин Тьюринга, вычисляющих некоторые бесконечные семейства функций Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Джабаров Роман Рафикович, Ефремов Николай Михайлович

Сложность устройства машины Тьюринга, очевидно, связана с мощностью внутреннего алфавита, т. к. чем больше количество внутренних состояний, тем более сложную программу может иметь машина Тьюринга, и может, следовательно, вычислить более сложную функцию. Сложностью машины Тьюринга Т = (Q, A, П) будем называть мощность внутреннего алфавита |Q|. Множество машин Тьюринга сложности k обозначим τ(k). Множество функций, для которых существует машина Тьюринга сложности k, вычисляющая её, обозначим F(k). Минимальную сложность машины Тьюринга, вычисляющей функцию, обозначим, т. е. =. Назовем её сложностью описания функции с помощью машины Тьюринга. Пусть вычислимая функция. Рассмотрим однопараметрическое семейство функций. Обозначим сложность описания функции. В частности, получен следующий результат: Теорема 6. Пусть вычислимая функция и существуют такие, что, причем существует машина Тьюринга, для которой длина активной зоны влево от начального физического адреса равна k и. Тогда, где обозначает некоторое число z такое, что. Библиогр. 1.

Похожие темы научных работ по математике , автор научной работы — Джабаров Роман Рафикович, Ефремов Николай Михайлович

ON ASYMPTOTIC OF COMPLEXITY OF TURING MACHINE WHICH COMPUTES SOME INFINITE SETS OF FUNCTIONS

Complexity of Turing machine description depends on power of internal alphabet, because the more internal states machine has, the more complex program Turing machine can have and therefore it can compute the more complex function. Exactly such way is used in this article. Let's define power of internal alphabet |Q| as complexity of Turing machine Т = (Q, A, П). Let's denote sets of Turing machine k-complexity τ(k). Sets of functions that can be computed by means of Turing machine k-complexity are F(k). is minimal Turing machine complexity which can compute function, so =. Let's denote it as complexity of function description by means of Turing machine. Let's assume computable function so we will view one-parameter collection of functions. is complexity of function description. Specifically, we have got the following result: Theorem 6. Let computable function and there are such as and there is Turing machine for which the length of active zone left of initial physical address equals k and, so, where is number z such as.

Текст научной работы на тему «Об асимптотике сложности машин Тьюринга, вычисляющих некоторые бесконечные семейства функций»

Р. Р. Джабаров, Н. М. Ефремов Астраханский государственный технический университет

ОБ АСИМПТОТИКЕ СЛОЖНОСТИ МАШИН ТЬЮРИНГА, ВЫЧИСЛЯЮЩИХ НЕКОТОРЫЕ БЕСКОНЕЧНЫЕ СЕМЕЙСТВА ФУНКЦИЙ

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

В работе мы придерживаемся обозначений, принятых в [1].

Под машиной Тьюринга Т будем понимать тройку (<2, А, П), где Q = - внутренний алфавит; ч0 - заключительное состояние; ч1 - начальное состояние;

А = - внешний алфавит; а0 - пустой символ;

П - программа машины, представляющая собой множество команд таких, что для любой пары ЧО/, где 1 = 1 . п, / = 0 . т, имеется точно одна команда вида ча ^ чай, где 1 = 1 . п; к = 0 . п;/, I = 0 . т;

й е , где Ь - сдвиг влево; Я - сдвиг вправо; Е - остановка на месте;

А - множество конечных слов внешнего алфавита.

Активная зона - минимальная связная часть ленты, содержащая обозреваемую ячейку, а также все ячейки, в которых записаны непустые символы.

В дальнейшем мы считаем, что все ячейки на ленте пронумерованы стандартным образом целыми числами; этот номер назовем физическим адресом ячейки. Предположим так же, что в начале работы головка машины считывает ячейку с адресом 0.

Конфигурация - машинное слово вида ача2, где ч, - внутреннее состояние; а1 - слово из алфавита А, находящееся в левой части активной зоны от считывающей головки; а2 - слово в правой части ленты от головки.

Стандартная начальная конфигурация - конфигурация вида К0 = ч1а.

Стандартная заключительная конфигурация - конфигурация вида д0а.

Машина реализует процесс изменения конфигураций в следующем смысле. Если К0 = ч1а и а = ага , где а, е А и а е А , то в программе машины имеется только одна команда вида Ча ^ чай. Тогда следующая конфигурация К1 определяется так:

1. К1 = чаа , если й = Е.

2. К1 = а\Чка , если й = Я.

3. К1 = чааа , если й = Ь.

Это обстоятельство записывается в виде К0 ^ К1. Если теперь конфигурация К1 не является заключительной, то в соответствии с системой команд, аналогично вышеописанному переходу, определима однозначно следующая конфигурация - К2. Таким образом, начальная конфигурация К0 порождает последовательность конфигураций К0 ^ К1 ^ . ^ К ^ . .

Если последовательность смены конфигураций конечна, т. е. обрывается в заключительной конфигурации, то говорят, что машина применима к конфигурации К0, в противном случае -неприменима к К0.

Машина Тьюринга Т правильно вычисляет частичную функцию/, если для любого Р е А* выполнено:

1. Если ДР) определено и _ДР) = S, то машина Т применима к начальной конфигурации ч1Р и заключительной конфигурацией является Кг = ч0&

2. ЕслиА(Р) не определено, то машина Т неприменима к начальной конфигурации ч1Р.

Здесь и далее будем рассматривать только машины, правильно вычисляющие функции.

Щ - суперпозиция машин Т, и Т/, причем первой в работу вступает машина Т, затем Т/.

Будем считать, что алфавит А машины Т содержит элементы 0, 1. Условимся произвольное число п е Ы0 кодировать п + 1 единицей (N0 - множество целых неотрицательных чисел).

Определение 1. Сложностью машины Тьюринга Т = (Q, А, П) будем называть мощность внутреннего алфавита \Q\ = п + 1.

Определение 2. Множество машин Тьюринга сложности к обозначим т(к) (к > 2), а множество всех машин Тьюринга т. Очевидно, что 1 = У 1(к), причем т(к) П т(;) = ф, если к Ф ;.

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

Определение 3. Множество функций, для которых существует машина Тьюринга сложности к, вычисляющая её, обозначим Р(к). Тогда множество всех вычислимых функций

Предложение 1. Нетрудно видеть, что мощность множества т(к) равна \т(к)\ = = (3(п + 1)(т + 1))п(т+1).

Так как множество т(к) конечно и \Р(к)\ < \т(к)\, то множество Р(к) конечно.

Очевидно, что семейство множеств к является неубывающим, т. е. Р(к) с Р(к + 1).

Более сильное утверждение содержится в теореме 2.

Теорема 2. Семейство множеств ^_2 является строго возрастающим.

Доказательство. Зафиксируем начальную конфигурацию К0 = чД. Для любого к > 2 в множестве р(к) найдется хотя бы одна функция, машина для которой применима к конфигурации К0. Среди данных машин выберем машину Тт, для которой вычислимая функция принимает максимальное значение в точке 0. Рассмотрим машину Т