Теория вычислений и машины Тьюринга

Теперь понятие алгоритма можно отождествить с машиной Тьюринга, работа которой удовлетворяет требованиям 1-8.

Согласно требованию 7 длина слов конечна, но неограниченна, а для этого требуется разделенная на отдельные ячейки счетная лента неограниченной длины, на которую можно записать как входные, так и выходные слова. Удовлетворить данное требование можно с помощью ограниченной справа, но неограниченной слева разделенной на ячейки ленты. При этом будем считать, что в одну ячейку можно записать не более одного символа, что не принципиально и создает только однозначность восприятия и исполнения предписания алгоритма (требование 4).

Согласно требованию 1 записи должны иметься только в конечном числе ячеек, то есть в подавляющем числе ячеек содержится символ "пусто" ( $$a_{0}$$ ).

Согласно требованию 3 выполнение алгоритма носит последовательный, поэтапный характер и, если оно не обрывается, всегда ведет от одного состояния к другому. Предписание для алгоритма содержит как общие правила, определяющие сами действия над символами, способы выделения результата вычислений и т. д., так и указания, регламентирующие правила перехода от одного состояния к другому, следующему непосредственно за ним. Согласно требованиям 4 и 5 такой переход должен быть определен однозначно. При этом каждое указание требует от вычислителя определенного образа действий типа "изменить содержимое отдельной ячейки ленты", "найти другую ячейку ленты", "прекратить вычисления" и т. п. Действие "найти другую ячейку ленты" можно ограничить действием "найти соседнюю ячейку ленты", то есть машина Тьюринга может работать без перескоков и после выполнения предписания всегда смещаться на соседнюю ячейку, если не выработано условие останова вычислений.

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

Отсюда, в любом состоянии предписание может состоять в следующем: "изменить содержимое рабочей ячейки", "сдвинуть рабочую ячейку вправо, а если возможно, то и влево", "остановиться".

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

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

Согласно требованию 8 у вычислителя может быть только ограниченная память. Поэтому в оценке его состояния может принять участие только ограниченная (содержательная) часть записей на ленте. Но просмотр записи из не более $$\xi$$ ячеек можно осуществить в виде $$\epsilon$$ -кратного просмотра содержимого только одной ячейки и за один раз. Поэтому для оценки текущего состояния вычислителя достаточно содержимого единственной ячейки, которую можно считать текущей информационной ячейкой. В свою очередь, рабочую и информационные ячейки можно совместить в одной, так как предписание всегда можно составить таким образом, чтобы сначала рабочая ячейка сменялась информационной, а затем на основе анализа содержимого последней разыскивалась исходная рабочая ячейка и определялся требуемый порядок действий (в современной терминологии "косвенная адресация").

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

Для наглядности введенных соглашений рассмотрим пример. Пусть рабочий алфавит содержит два символа: $$*$$ и $$|$$, предписание $$\breve{D}$$ содержит $$\rho \ge 3$$ указаний вида:

Если рабочая ячейка содержит символ $$*$$, остановись. Если рабочая ячейка содержит $$|$$, замени его символом $$*$$ и далее действуй согласно второму указанию.

Если рабочая ячейка содержит символ $$*$$, замени его символом $$|$$ в том случае, когда предыдущее действие выполнялось согласно первому указанию, и действуй далее согласно третьему указанию; в противном случае остановись. Если рабочая ячейка содержит символ $$|$$, остановись.

Выделенную курсивом ссылку на предыдущее указание можно устранить следующим образом:

Если рабочая ячейка содержит символ $$*$$, замени его символом $$|$$ и действуй согласно третьему указанию.

Если рабочая ячейка содержит символ $$|$$, остановись.

Введем $$\xi+1$$ состояние. (Здесь $$\xi+1$$ вновь не арифметическое действие, а следующий за $$\xi$$ символ). Тогда:

Если рабочая ячейка содержит символ *, остановись. Если рабочая ячейка содержит $$|$$, замени его символом $$*$$ и далее действуй согласно $$\xi+1$$ указанию.

Если рабочая ячейка содержит символ $$*$$, остановись. Если рабочая ячейка содержит символ $$|$$, остановись. Модифицированное предписание по своему действию совпадает с исходным, но не содержит ссылок на (пред)историю.

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

Таким образом, имеются достаточные основания утверждать, что каждому алгоритму можно поставить в соответствие экстенсионально эквивалентный ему алгоритм, работающий с символами на "бесконечной" ленте по следующим общим правилам.

Рабочее состояние алгоритма в каждый момент его работы определяется текущей рабочей ячейкой и ее содержимым в тот же момент времени. Состояние вычислительного процесса вплоть до данного момента времени полностью определяется текущей рабочей ячейкой, текущим содержимым всей ленты и тем указанием или его номером в заранее оговоренном списке указаний, согласно которому выполняется текущее вычисление. Выбор текущего действия полностью и однозначно определяется содержимым текущей рабочей ячейки. Для реализации любого алгоритма требуется всего три типа действий: изменение содержимого рабочей ячейки; сдвиг рабочей ячейки на одну ячейку вправо или, если возможно, то и влево; останов. Первые два действия содержат также указание, определяющее, к какому следующему указанию надо перейти.

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

"Базовый комплект" машины Тьюринга $$(МТ) Т$$ содержит (рис. 3.1):

операционное устройство, которое может находиться в одном из дискретных состояний, принадлежащих некоторой конечной совокупности $$q_{0}, q_{1}, …, q_{s}$$ ;

комбинированную читающую и пишущую головку;

счетную ленту, обладающую описанными выше свойствами;

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

Начальным состоянием $$Т$$ является $$q_{0}$$, а ячейки ленты считаются пронумерованными начиная с левого края числами $$0, 1, 2, …$$ Читающая и пишущая головка способна выполнять действия (считывать, стирать и записывать) над рабочим алфавитом $$Т: A = \{a_{1}, a_{2}, …, a_{t}\}$$ и буквой $$a_{0}$$, которая символизирует "пусто". Каждая ячейка ленты в каждый момент времени содержит букву из множества $$A\cup a_{0}$$, причем почти все ячейки заняты буквой $$a_{0}.$$

(рис 3.1) Конструкция машины Тьюринга (без лентопротяжного механизма)

Лампочка МО зажигается при выполнении указания "машинный останов", а лампочка ПЛ - в случае когда начальная ячейка ленты находится под считывающей головкой, а затребованное действие состоит в сдвиге рабочей ячейки влево (сигнал "переход за край ленты").

Рассмотрим конкретный пример работы простейшей $$МТ$$, оперирующей с рабочим алфавитом $$\{|\}$$, символом "пусто" вида $$*$$ и тремя рабочими состояниями $$q_{0}$$, $$q_{1}$$ и $$q_{2}.$$

Пусть $$МТ$$ работает следующим образом [45]:

В состоянии $$q_{0}:$$ вне зависимости от содержимого рабочей ячейки ( $$*$$ или $$|$$ ) $$Т$$ сдвигает рабочую ячейку вправо и переходит в состояние $$q_{1}.$$

В состоянии $$q_{1}:$$ $$Т$$ заменяет стоящий в ячейке символ на $$|$$, то есть выполняет подстановку вида $$*\to|$$ или $$|\to|$$, и переходит в состояние $$q_{2}.$$

В состоянии $$q_{2}:$$ $$Т$$ останавливается вне зависимости от содержимого рабочей ячейки.

$$МТ$$, работающая согласно приведенному предписанию, фактически делает следующее. После установки головки над некоторой ячейкой ленты (состояние $$q_{0}$$ ) $$Т$$ сдвигает рабочую ячейку вправо, стирает содержимое этой ячейки, заносит в нее символ $$|$$ и останавливается.

Для наглядности проиллюстрируем работу такой $$МТ$$ с помощью рис. 3.2 -3.7 .

В исходном положении лента содержит только символы "пусто", го ловка размещается над ячейкой, помеченной стрелкой, а $$Т$$ находится в состоянии $$q_{0}$$, обнаруживает символ "пусто", сдвигается вправо на одну ячейку (см. рис. 3.3) и переходит в состояние $$q_{1}$$ (см. рис. 3.4). Затем $$Т$$ заменяет символ "пусто" в текущей рабочей ячейке на символ $$|$$ (см. рис. 3.5) и переходит в состояние $$q_{2}$$ (см. рис. 3.6). В этом положении согласно предписанию $$Т$$ останавливается, о чем сигнализирует лампочка МО (см. рис. 3.7).

(рис 3.2) Исходное положение(рис 3.3) Положение 1(рис 3.4) Положение 2(рис 3.5) Положение 3(рис 3.6) Положение 4(рис 3.7) Положение "останов"

В данном случае не требуется уточнять, что речь идет о вычислимых только по Тьюрингу функций, так как если функция вычислима по Тьюрингу, она вычислима и по Клини, и по Черчу, и по Маркову, и т. д.

Несмотря на кажущийся примитивизм выполняемых МТ "элементарных" действий, с их помощью можно представить алгоритм вычисления практически любой вычислимой функции. В частности, чтобы машина Тьюринга смогла реализовать приведенный ранее алгоритм,а суммирования достаточно, чтобы она имела три состояния: начальное $$q _{0}$$, чтобы выполнить шаг 1, и два рабочих: $$q _{1}$$ если $$e^{+}:=0$$, и $$q _{2}$$, если $$e^{+}:=1.$$

3.2. Машины Тьюринга и вычислимые функции

Приведенных в предыдущем разделе данных достаточно для перехода к общему описанию $$МТ.$$

Работу $$МТ$$ с рабочим алфавитом $$A =A_{t}$$ и состояниями $$(q _{0}, q _{1}, …, q_{s})$$ можно представить таблицей машины $$Т$$, которая представляет собой матрицу с 4 столбцами и $$(s+1)(t+1)$$ строками. Строка матрицы с номером $$(j(t+1)+m+1), (0 \le j \le s, 0\le m \le t) $$ имеет вид: $$q_{j} a_m v_{jm} q_{jm}$$, где действие $$v_ {jm}\inA\cup\{ a _{0}, r , l , s \}$$, а $$q_{jm} \in ( q _{0}, q _{1}, …, q)$$ - следующее состояние. Индексы элементов строки матрицы $$Т$$ в ряде случаев можно опускать, и тогда описание строки принимает вид $$qavq'$$, где действие $$v$$ может представлять собой подстановку символа $$(qaa' q'$$ вида $$v = a \to a'$$, при этом $$v_{jm} \in A\cup{a _{0}})$$, сдвиг вправо на одну ячейку $$(qarq' \text{ вида } v = r)$$, сдвиг влево на одну ячейку, если рабочая ячейка не совпадает с нулевой $$(qalq' \text{ вида } v = l )$$. Если рабочая ячейка совпадает с нулевой и $$v = l$$, то требуемое действие невыполнимо и $$Т$$ останавливается $$v = s$$, что вызвано ее выходом за пределы ленты. Машинный останов $$Т (v = s)$$ может быть и запланированным. Считается также, что пара $$qa$$ однозначно идентифицирует единственную строку матрицы $$Т $$. В нашем примере матрица $$МТ$$ имеет вид:

$$q _{0} * r q_{1} \\ q_{0} | r q_1 \\ q _{1} * | q _{2 } \\ q _{1} | | q _{2 } \\ q_{2} * s q_{2 } \\ q _{2} | s q_2 $$

Строки таблицы $$Т$$ с одинаковыми $$q$$ соответствуют некоторому указанию в смысле требования 1, и наоборот, состояниям $$Т$$ отвечают номера указаний в соответствующем алгоритмическом предписании.

Таблицу 3.1,задающую правила подстановки символов при арифметическом сложении, также можно представить в виде таблицы машины Тьюринга (табл. 3.2), если пару $$(x _{1}, x _{2})$$ считать одним символом, а $$q_1: = e^{+}= 0$$, и $$q_{2}:= e^{+}= 1$$.

В принятых соглашениях запись на ленте или просто запись является функцией $$Y$$ на $$N$$ со значениями в $$A\cup\{a _{0}\}$$, которая каждому $$i$$ ставит в соответствие букву, являющуюся содержимым $$i$$ -й ячейки ленты. При этом неравенство $$Y(i) \ne *$$ выполняется только для конечного числа индексов $$i$$.

Согласно требованию 1 общий итог выполненных вычислений однозначно определяется конфигурацией $$МТ $$, которая задается тройкой $$(\psi , Y, q)$$, где $$\psi$$ - номер текущей рабочей ячейки, $$Y$$ - текущая запись и $$q$$ - текущее состояние $$Т$$. Конфигурации обычно обозначают $$C$$, …, а начальной конфигурации отвечает та, у которой третья компонента есть $$q _{0}$$.

Таблица преобразования символов при сложении по "Тьюрингу"

$$q_j$$	$$(x_1, х_{2})$$	$$\Sigma$$	$$q_{jm}$$	$$q_j$$	$$(x_1, х_{2})$$	$$\Sigma$$	$$q_{jm}$$	$$q_j$$	$$(x_1, х_{2})$$	$$\Sigma$$	$$q_{jm}$$
$$q_1$$	0,0	0	$$q_1$$	.	.	.	.	$$q_1$$	3,3	6	$$q_1$$
$$q_1$$	0,1	1	$$q_1$$	$$q_2$$	1,9	1	$$q_2$$	$$q_1$$	3,4	7	$$q_1$$
				$$q_1$$	2,2	4	$$q_1$$
$$q_1$$	0,9	9	$$q_1$$	$$q_1$$	2,3	5	$$q_1$$	$$q_1$$	3,9	2	$$q_2$$
$$q_2$$	0,0	1	$$q_1$$
$$q_2$$	0,1	2	$$q_1$$	$$q_1$$	2,5	7	$$q_1$$	$$q_2$$	3,3	7	$$q_1$$
								$$q_2$$	3,4	8	$$q_1$$
$$q_2$$	0,9	0	$$q_2$$	$$q_1$$	2,9	1	$$q_2$$	$$q_2$$			$$q_2$$
$$q_1$$	1,1	2	$$q_1$$	$$q_1$$	2,2	5	$$q_1$$	$$q_1$$	3,9	3	$$q_1$$
$$q_1$$	1,2	3	$$q_1$$	$$q_1$$	2,3	6	$$q_1$$	$$q_1$$			$$q_1$$
					2,4	7
$$q_1$$	1,9	0	$$q_1$$	$$q_1$$	2,5	8	$$q_1$$	$$q_1$$	7,7	4	$$q_1$$
$$q_2$$	1,1	3	$$q_2$$	$$q_2$$			$$q_2$$	$$q_2$$	7,8	5	$$q_2$$
$$q_2$$	1,2	4	$$q_2$$	$$q_2$$	2,9	2	$$q_2$$	$$q_2$$			$$q_2$$

Пусть $$C = ( \psi , Y, q)$$ - некоторая конфигурация $$Т$$. Если $$qY(\psi)vq'$$ есть некоторая строка таблицы $$Т$$, начинающаяся символами $$qY(\psi)$$, и если $$v \ne s$$ и одновременно не выполняются равенства $$v = l$$ и $$\psi = 0$$, то выполнение действия $$v$$ приводит к новой рабочей ячейке с номером $$\psi$$ (при этом не исключается $$\psi = \psi' $$ ) и к новой записи $$Y$$ (при этом не исключается $$Y = Y'$$ ) и $$Т$$ переходит в состояние $$q ' $$. В этом случае однозначно определенную конфигурацию $$C' = ( \psi' , Y', q')$$ называют следующей за $$C.$$ В противном случае ( $$v = s$$ или одновременно $$v = l$$ и $$\psi = 0$$ ) говорят, что $$C$$ является конечной конфигурацией для $$Т $$.

Говорят, что $$Т$$ применима к записи $$Y$$ в рабочей ячейке $$\psi$$, если в качестве начальной конфигурации выбрана конфигурация $$C _{0} = ( \psi , Y0, q_{0})$$.

Конфигурация $$C _{0}$$ однозначным образом порождает конечную или бес-конечную последовательность конфигураций $$C _{0}, C _{1}, …$$, в которой $$C_{i+1}$$ есть конфигурация, следующая за $$C_{i}$$, и для которой $$C_{i}$$ есть последний член в том и только в том случае, когда $$C_{i}$$ является конечной конфигурацией. Так как $$МТ$$ работает в пошаговом режиме, между номером шага и номером конфигурации существует взаимно однозначное соответствие. Поэтому машина $$Т$$ останавливается через конечное число шагов после применения к записи $$Y$$ в рабочей ячейке $$\psi$$, если последовательность конфигураций, порожденная $$C _{0} = (\psi , Y_0, q _{0})$$, имеет последний член. Если для анализа вычислений после-довательность состояний $$МТ$$ не представляет интереса, то сам вычислительный процесс можно описать двойками $$S = (\psi , Y)$$, которые каждой конфигурации $$C = ( \psi, Y, q)$$ сопоставляют ее позицию, то есть последовательности конфигураций всегда соответствует последовательность позиций, к которым применимы термины "начальная" и "конечная".

Пусть $$C = ( \psi, Y, q)$$ есть некоторая конфигурация и $$Y(i) = a_i$$ для всех $$i \ge 0$$. Тогда для наглядного изображения $$C$$ и отвечающей ей позиции можно использовать:

$$а_{0}..a_{\psi}^0 ..$$. и $$\begin{array}{rrr} a_0... а_{\psi} \\ \uparrow \end{array}$$

Безразличные для анализа участки записи будем обозначать символом $$\sim$$, а если речь идет о содержимом одной ячейки, то символом $$\clubsuit.$$ Это позволяет для записи позиций использовать следующие упрощения.

Выделить только интересующие позиции типа: $$*\sim | \substack{\clubsuit\\\uparrow}*.$$

Обозначить специальным символом $$\bot$$ значимый левый (правый) край ленты типа: $$\bot ** \substack{|\\\uparrow}*\bot$$

Исключить повторяющийся символ правее определенного: $$\bot*|\substack{*\\\uparow}\ldots.$$

Пусть $$S$$ и $$S'$$ возможные позиции для $$Т$$. Тогда запись вида $$S\stackrel{T}{\Rightarrow}S$$ означает: $$Т$$ начала свою работу в начальной позиции $$S$$ и (после конечного числа шагов) остановилась в конечной позиции $$S'$$. Например: $$\bot*w\substack{*\\\uparrow}\ldots\stackrel{T}{\Rightarrow}\bot\sim|\substack{*\\\uparrow}$$.

Применить $$Т$$ к записи после слова $$w$$ или после $$k $$ -членной последовательности слов $$(w_1, w_{2}, …, w_k )$$ над $$А$$ означает взять в качестве начальной позицию: $$\bot\substack{*\\\uparrow}w*\ldots$$, и соответственно $$\bot\substack{*\\\uparrow}w_1*\ldots* w_k*$$.

Применить $$Т$$ к записи перед словом $$w$$ или перед $$k$$ -членной последовательностью слов $$(w_1, w_{2}, …, w_k)$$ над $$А$$ означает взять в качестве начальной позицию: $$\bot^*_{\uparrow} w^*\ldots$$, и соответственно $$\bot^*_{\uparrow} {w_1}^*\ldots^*{w_k}^*$$. Применить $$Т$$ к пустой ленте означает взять в качестве начальной позицию $$\bot^*_{\uparrow}.$$

Говорят, что $$Т$$ остановилась после (перед) словом $$w$$, если $$Т$$ применялась к начальной записи $$Y$$ в начальной ячейке $$S = (\Psi , Y)$$ и $$S \stackrel{T}{\Rightarrow}\bot\sim^*w^*_{\uparrow}$$, $$(S \stackrel{T}{\Rightarrow}\bot\sim^*_{\uparrow}w^*)$$. При этом в конечной позиции после символа $$^*$$ нельзя сказать ничего определенного.

Если $$Т$$ в результате применения к записи $$Y$$ в рабочей ячейке $$\Psi$$ остановилась после слова $$w$$ над $$А$$, то последняя рабочая ячейка не может быть нулевой, даже если $$w = \#$$, так как фактически произошел машинный останов $$Т$$.

Для строгого определения вычислимых по Тьюрингу функций используется экстенсиональная точка зрения, которая исходит из следующего:

Две функции равны, если совпадают их области определения и если их значения во всех общих точках определения равны.

Два алгоритма $$\ddot{U}$$ и $$\ddot{U}'$$ экстенсионально равны (равны по конечному эффекту), если равны вычисляемые ими функции $$f_{\ddot{U}} = f_{\ddot{U}'}$$.

Функцию $$f$$ называют функцией из $$\Omega^{k}(E)$$ в $$\Omega (B)$$, если область определения $$f (\Def{f})$$ содержится в $$\Omega^{k}(E)$$, а множество образов при ото-бражении $$f (\Bild{f} )$$, содержится в $$\Omega(B)$$. В предельном случае $$\Def {f} = \Omega^{k}(E)$$, и тогда $$f$$ называют функцией на $$\Omega^{k}(E)$$ со значениями в $$Q(B)$$. В общем случае $$\Def{ f}\subset \Omega^{k}(E)$$, и тогда $$f$$ называют частичной функцией на $$\Omega^{k}(E)$$ со значениями в $$\Omega(B)$$.

Алгоритм $$\ddot{U}< \breve{D} , E, A, D, k>$$ определяет функцию $$f_{\ddot{U}}$$ из $$\Omega^{k}(E)$$ в $$\Omega(B)$$, если выполнены следующие условия:

Функция $$f_{\ddot{U}}$$ определена для $$w\in\Omega^k(E)$$ в том и только в том случае, когда применение $$\ddot{U}$$ к $$w$$ приводит к некоторому результату, который и является значением $$f_{\ddot{U}}$$ от $$w$$.

Функция $$f_{\ddot{U}}$$ обладает тем свойством, что для всех $$w\in\Def{ f_{\ddot{U}}}$$ значение $$f_{\ddot{U}}(w)$$ можно вычислить, исполнив предписание $$\breve{D} $$.

Отсюда, функция $$f$$ из $$\Omega^{k}(E)$$ в $$\Omega (B)$$ называется вычислимой тогда и только тогда, когда существует алгоритм $$\ddot{U}<\breve{D} , E, A, D, k>$$, для которого $$f = f_{\ddot{U}}$$. В этом случае $$\ddot{U}$$ называют вычислительной процедурой для $$f$$.

В терминах МТ те же определения имеют следующий вид. Пусть $$Т$$ есть МТ с рабочим алфавитом $$А$$, таким, что $$E, B \subset А$$. Тогда $$Т$$ определяет некоторую $$k $$ -местную функцию $$(k \ge 0)$$ из $$\Omega^{k}(E)$$ в $$\Omega (B) $$ по следующему правилу: $$w\in\Omega^{k}(E)$$ принадлежит области $$\Def{f}$$ тогда и только тогда, когда $$Т$$, примененная к записи $$w$$, останавливается после слова из $$\Omega (B)$$, а это слово является значением $$f$$ от $$w$$.

Таким образом, для $$(w_1,w_2... w_k)\in\Omega^{k}(E)$$ имеем:

$$\bot * w_{1}*, w_{2}, \ldots, w_{k}\substack{*\\\uparrow}\ldots\stackrel{T}{\Rightarrow} \bot\sim *f(w_1\ldots w_k) \substack{*\\\uparrow},$$

когда $$(w_1…w_k )\in\Def{ f}$$, и наоборот, если $$(w_1, w_{2}, …, w_k )\notin\Def{ f}$$, то $$Т $$, примененная к записи $$(w_1, w_{2}, …, w_k)$$, не останавливается после слова из $$\Omega (B)$$.

Приведенных данных достаточно для определения 3.1: функция $$f$$ из $$\Omega^{k}(E)$$ в $$\Omega (B)$$ называется вычислимой по Тьюрингу ( ФВТ ), если существует МТ с рабочим алфавитом $$А$$, содержащим $$E$$ и $$B$$, такая, что $$k $$ -местная функция из $$\Omega^{k}(E)$$ в $$\Omega (B)$$, определяемая машиной $$Т $$, совпадает с $$f $$.

О любой такой МТ говорят, что она вычисляет $$f $$.

Из приведенного определения следует, если $$f$$ есть ФВТ из $$\Omega^{k}(E)$$ в $$\Omega (B)$$ и $$Т$$ есть МТ, вычисляющая $$f$$, то, применив $$Т$$ к $$w\in\Omega^{k}(E)$$, можно получить следующие результаты: либо $$Т$$ не остановится вовсе, либо $$Т$$ уйдет за пределы ленты, либо произойдет машинный останов $$Т $$. Если в последнем случае $$Т$$ остановилась после слова $$w'\in\Omega(B)$$, то $$w'\in\Def{f}$$ и $$f(w) = w'$$. Во всех остальных случаях $$w\notin\Def{f}.$$

Введенное описание применения $$Т$$ к аргументу ФВТ, вычисляемой $$Т $$, и нахождение значения функции способом, указанным в определении 3.1, вместе образуют общее предписание для всех алгоритмов. Это позволяет говорить, что функция, вычислимая по Тьюрингу ( ФВТ ), является адекватной формализацией интуитивного понятия "вычислимая функция".

3.3. Машины Тьюринга и перечислимые множества

В математике кроме вычислительных алгоритмов, описывающих последовательности преобразований конструктивных объектов, существуют еще и процедуры перечисления таких объектов. Традиционно к таким процедурам относят перечисление простых чисел до некоторой заранее заданной границы. (К простым относят те числа, которые делятся только сами на себя и на единицу.) При этом считается известной процедура выделения простых чисел из натурального ряда (тест на делимость по отношению ко всем предшественникам) и занесения их в список в порядке возрастания, а временные и прочие трудности реализации перечислительной процедуры в расчет не принимаются. В результате все множество простых чисел считается перечислимым, а метод выделения и записи простых чисел называется перечислительной процедурой.

Приведенных соображений достаточно для введения интуитивно понимаемого определения 3.2 [50]: множество $$\Re k$$ -членных последовательностей слов над некоторым алфавитом называется перечислимым, если существует общая процедура, с помощью которой можно систематическим образом получить все элементы $$\Re$$.

В частности, для перечисления множества слов над некоторым алфавитом $$А$$ подходят две процедуры со следующими предписаниями [50]:

Сначала пишется пустое слово. Если выписанное слово $$w$$ имеет длину $$\rho$$, то далее пишется слово длины $$\rho$$ над $$А$$, которое следует лексикографически непосредственно за $$w$$, и при условии, что $$w$$ не лексикографически последнее слово длины $$\rho$$ над $$А$$. В противном случае пишут лексикографически первое слово длины $$\rho + 1$$ над $$А$$.

Сначала пишется пустое слово. Далее пишется слово, полученное из какого-то уже выписанного слова, добавлением одной буквы из $$А$$.

Очевидно, что первое предписание однозначно задает последовательность слов над $$А$$, в то время как во втором предписании допускается произвол в выборе как "уже выписанного слова", так и дописываемой буквы. В первом случае можно установить соответствие между вычислимостью и перечислимостью по Тьюрингу, в то время как во втором случае нарушается требование 4 для вычислимых по Тьюрингу алгоритмов, что вынуждает говорить о перечислимости через так называемые исчисления или системы правил вывода [50]. В результате в неоднозначных перечислительных процедурах на передний план выходят не проблемы перечисления элементов некоторого множества, а креативный (познавательный) аспект этой процедуры и порождаемых ею креативных множеств.

Отсюда, получить точное определение перечислимости по Тьюрингу можно только для тех процедур, которые удовлетворяют не только требованию однозначности, но и всей совокупности требований 1-8, предъявляемых к вычислимым по Тьюрингу алгоритмам. При таких условиях тезис Черча распространяется и на перечислительные процедуры, что позволяет говорить об адекватном уточнении интуитивных представлений о перечислимости с помощью понятия перечислимости по Тьюрингу. Существенно, что ограничения 1-8 не только не выхолащивают, но и практически не ограничивают класс перечислимых множеств и процедур перечисления их элементов.

Покажем, что понятие вычислимости можно свести к понятию перечислимости, и наоборот, что и позволяет формализовать перечислимость с помощью уже имеющегося понятия вычислимости по Тьюрингу.

Сведем понятие вычислимости к понятию перечислимости, используя график функции $$f$$, который представляет собой множество $$\Graph {f}:= \{(m, f(m)): m \in\Def{f}\}$$. Справедлива теорема [50]: Пусть $$k \ge 1$$ и $$f$$ есть некоторая функция из $$\Omega^{k}(E)$$ в $$\Omega(B)$$. Функция $$f$$ вычислима в том и только в том случае, когда множество $$\Graph {f}$$ перечислимо. Доказательство прямого утверждения данной теоремы исходит из того, что если $$f$$ вычислима, то для нее существует вычислительная процедура $$\breve{D}_f$$ Всегда можно упорядочить лексикографически и пронумеровать числами натурального ряда элементы множества $$\Omega^{k}(E)$$. Тогда элементы множества $$\Graph {f}$$ можно также пронумеровать числами натурального ряда, отвечающими числу шагов в процедуре $$\breve{D}_f$$. Доказательство обратного утверждения строится на том, что процедуру $$\breve{D}_f$$, вычисляющую $$f ( m )$$, всегда можно остановить по "счетчику", в котором содержится лексикографический номер $$m$$ из $$\Graph {f}.$$

Понятие перечислимости можно свести к понятию вычислимости с помощью следующей теоремы [50]: Пусть $$k \ge 1$$ и $$\Re\subset\Omega^{k}(А)$$. Множество $$\Re$$ перечислимо тогда и только тогда, когда существует алфавит $$E$$ и вычислимые функции $$f_1, f_2,\ldots, f_k$$ из $$\Omega (E)$$ в $$\Omega (А)$$, такие, что $$\Re=\{(f _{1}(w), f _{2}(w), …, f_k(w),):w\in\cap\Def{f_{i}}\}$$, где теоретико-множественное пере-сечение берется по индексу $$i (i = \overline{l,k})$$.

В частности, при $$k = 1 \Re$$ перечислимо в том и только в том случае, когда $$\Re$$ есть область значений некоторой вычислимой функции.

Доказательство прямого утверждения данной теоремы исходит из того, что если $$\Re$$ перечислимо, то для него существует некоторая перечислительная процедура $$\breve{D} $$, которая упорядочивает элементы $$\Re$$ в виде однозначно определенной последовательности, геделезация которой приводит к ряду натуральных чисел $$N$$. Поэтому искомые вычислительные функции $$f_1, f_2\ldots f_k$$ можно определить из $$N$$ в $$\Omega(А)$$, для которых вычис-лительная процедура останавливается, когда получен элемент $$m\in\Re$$, что и позволяет считать $$i $$ -ю компоненту $$m$$ значением $$f_{i} ( m)$$. Доказательство обратного утверждения строится на том, что если имеется алфавит $$E$$ и вычислимые функции $$f_1, f_2\ldots f_k$$ из $$\Omega (E)$$ в $$\Omega (А)$$, такие, что $$\Re=\{ (f _{1}(w), f _{2}(w), …, f_k(w),):w\in\Def{f_{i}}\}$$, то всегда можно перечислить множество $$\Graph {f}$$ с помощью некоторой перечислительной процедуры $$\breve{D}_{i} $$. Эта процедура останавливается тогда, когда получена последовательность $$(w_1,w_2\ldots, w_k)$$, которая является элементом $$\Re$$.

Теперь можно перейти от интуитивного к формальному определению перечислимости и условий ее реализации.

Определение 3.3: Множество $$\Re$$ называется перечислимым по Тьюрингу ( ПТМ ) в том и только в том случае, когда существует алфавит $$E$$ и вычислимые по Тьюрингу функции $$f_1, f_2,\ldots, f_k$$ из $$\Omega (E)$$ в $$\Omega (А)$$, такие, что $$\Re=\{(f_1(w),f _{2}(w), …,f_k(w),):w\in\cap\Def{f_{i}}\}$$.

Теорема: Множество $$\Re$$ перечислимо по Тьюрингу тогда и только тогда, когда существует алфавит $$E$$ и вычислимые по Тьюрингу функции $$f_1, f_2,\ldots, f_k$$ из $$\Omega (E)$$ в $$\Omega (А)$$ с общей областью определения $$\beta$$, такие, что $$\Re=\{(f_1(w),f _{2}(w), …,f_k(w),):w\in\cap\beta\}$$.

Для технических нужд больше подходит следующее описание : множество $$\Re$$ перечислимо по Тьюрингу тогда и только тогда, когда $$\Re$$ есть область определения некоторой ВТФ из $$\Omega ^{k}(А)$$.

При этом следует помнить, что в природе существуют и не перечислимые по Тьюрингу множества, так как натуральный ряд $$N$$ содержит только счетную совокупность перечислимых по Тьюрингу подмножеств. Однако в большинстве современных вычислительных задач оперируют с конечными множествами, где данное ограничение не работает.

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

"Системотехнический" подтекст этого утверждения сводится к тому, что любую функцию можно вычислить только один раз, а полученные результаты представить некоторой таблицей соответствия, которая хранится в ОЗУ и может быть использована многократно. Такое разделение функций характерно для нейрокомпьютерных технологий, где первый этап ( вычислить таблицу соответствия) выполняется "материнской" нейро-ЭВМ, а второй - "дочерней" с тем отличием, что таблица реализуемой функции хранится не в ОЗУ, а представлена в некотором сжатом виде нейросетью, "перечисляющей" строки этой таблицы под воздействием входных сигналов.

3.4. Машины Тьюринга и "количество информации"

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

Интуитивно ясно, что для объективного сравнения сначала необходимо "измерить" количество информации, затраченной на предписание, которое задает вычислительный и перечислительный алгоритм, и только после этого сравнить его с количеством "производимой" ими информацией.

Существует три подхода к определению понятия "количество информации" [50], которые совпадают только по единице измерения.

Комбинаторный подход дает ответ на вопрос о количестве бит, которое надо затратить на представление (кодирование) конкретного сообщения. Он основан на следующих соображениях [51]. Имеется переменная $$x$$, которая принимает значения, принадлежащие конечному множеству $$X $$, которое состоит из $$N$$ элементов. "Комбинаторная" неопределенность состоит в том, что заранее неизвестно, какое конкретное значение принимает $$x \in X $$, и эта неопределенность оценивается "энтропией" $$H (x ) = log_{2}N $$. Присвоив $$x := a$$ конкретное значение, мы снимаем эту неопределенность, сообщив информацию $$I = log_{2}N $$. Когда переменные $$x _{1}, x _{2}, …, x_{k}$$ независимо принимают значения из множеств $$X _{1}, X _{2}, …, X_{k}$$ с количеством элементов $$N _{1}, N _{2}, …, N_{k}$$ соответственно, выражение для "энтропии" принимает вид:

$$H (x_{1}, x_{2}, …, x_{k} ) = H (x _{1}) + H (x _{2}) +…+ H (x_{k} ).$$

Отсюда, в рамках комбинаторного подхода:

Приходится абстрагироваться от вероятностных и тем более содержательных характеристик кодируемой информации, так как в этом случае можно задать только "информационный объем", необходимый для взаимно однозначного кодирования, но не эффективность (коэффициент) его использования с учетом частотных и содержательных характеристик кодируемого сообщения.

Достаточно просто, зная наиболее общие характеристики сообщения, определить требуемый для кодирования "информационный объем" $$\hat{I} =]I[$$ двоичных символов (бит). Здесь $$] [$$ - "старшее целое".

Установить связь между переменными $$x$$ и $$y $$, принадлежащими соответственно $$X$$ и $$Y $$, если под связью понимать, что не все пары $$(x , y )$$ являются "возможными" и принадлежат прямому произведению множеств $$X * Y$$.

В последнем случае считается, что по множеству "возможных" пар $$U$$ можно (при любом $$a \in x $$ ) определить множества $$Y_{a}$$ тех $$y$$, для которых $$(a,y ) \in U $$. Поэтому условную энтропию естественно определить соотношением:

$$H (y /a ) = log_{2}N (Y_{a} ); (H (x /x ) = 0),$$

где $$N (Y_{x} )$$ - число элементов в множестве $$Y_{x} $$ ; а информацию в $$x$$ относительно $$y$$ соотношением:

$$I (x : y ) = H (y ) - H (y /x ); (I (x : x ) = H (x )).$$

В (3.2) и (3.3) $$x$$ входит как "свободная переменная" функций $$H (y /x )$$ и $$I (x : y )$$, в то время как $$y$$ является "связанной переменной". Например, согласно данным табл. 3.3 имеем [51]: $$I (x = 1 : y ) = 0; I (x = 2 : y ) = 1; I (x = 3 : y ) = 2$$.

"Возможные" пары (x, y)

$$х$$ \ $$у$$	1	2	3	4
1	+	+	+	+
2	+	-	+	-
3	-	+	-	-

Вероятностный подход к определению понятия "количество информации" исходит из следующих соотношений:

$$H_W(x) = -\sum_x{p(x)log_{2}p(x),$$ $$H_{W}(y/x) = -\sum_y{p(y/x)log_{2} p(y/x)} ,$$ $$I_{W} (x : y) = H_{W} (y) - H_{W} (y/x),$$

которые учитывают тот факт, что в этом случае переменные $$x$$ и $$y$$ являются "случайными" и обладают совместным распределением вероятностей.

В рамках этого подхода по-прежнему $$H_{W} (y/x)$$ и $$I_{W} (x : y)$$ являются функциями от $$x $$, справедливы неравенства $$H_{W} ( x) \le H ( x)$$ и $$H_{W} (y/x) \le H ( y/x)$$, где равенство наступает при равномерном законе распределения (на $$X$$ и на $$Y_x$$ ), $$H_{W} (x/x) = 0$$ и $$I_{W} (x : x) = H_{W} (x)$$, а величины $$I_{W} (x : y )$$ и $$I ( x : y )$$ не связаны неравенством определенного знака.

Главное отличие вероятностного от комбинаторного подхода состоит в том, что "теснота связи" между $$x$$ и $$y$$ характеризуется симметричным соотношением:

$$I_{W} (x, y ) = M [ I_{W} (x : y )] = M [ I_{W} (y : x )],$$

где $$M [I_{W} (x : y)]$$ и энтропия $$M [ H_{W} (y /x))]$$ являются математическими ожиданиями.

Переход от $$I (x : y )$$ к $$M [I_{W} (x : y)]$$ обусловлен тем обстоятельством, что только в комбинаторном подходе всегда $$I(x : y ) \ge 0$$, что хорошо согласуется с интуитивным пониманием термина "количество информации". В вероятностном подходе $$I_{W} (x, y)$$ может быть и отрицательной, что интуи-тивно должно восприниматься как "дезинформация". Поэтому в вероятностном подходе подлинной мерой "количества информации" становится осредненная $$I_{W} (x : y)$$, то есть $$M [I_{W} (x : y )]$$.

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

Но вероятностный подход теряет смысл при оценке количества информации, содержащейся в тексте "Войны и мира" [51], потому что он требует включить этот роман в совокупность "всевозможных романов" и постулировать в этой совокупности некоторое распределение вероятностей. В этом случае придется рассматривать отдельные сцены "Войны и мира" как некоторую случайную последовательность с быстро затухающими в пределах нескольких страниц "стохастическими связями". Аналогичная ситуация складывается и при оценке количества наследственной информации в генетике, где в результате естественного отбора возникает система согласованных между собой характеристических признаков определенного вида животных или растений.

[51]. В такой постановке можно дать только асимптотическую оценку количества информации, содержащейся в одной относительно большой последовательности символов относительно другой. В рамках такого подхода нет смысла говорить о количестве информации в последовательности 1010 относительно последовательности 0111. Но если взять конкретную таблицу случайных чисел достаточно большого объема и выписать для каждой ее цифры цифру, отвечающую количеству единиц в ее квадрате по правилу [51]:

0	1	2	3	4	5	6	7	8	9
0	1	4	9	6	5	6	9	4	1

то новая таблица случайных чисел будет содержать примерно $$(log_{2}10-8/10) N$$ информации о первоначальной, где $$N$$ - число цифр в каждой таблице. Для алгоритмической меры информации $$I_{A} ( x : y)$$ характерно, что равноценные варианты ее определения могут привести к значениям, отличающимся на константу $$| I_{A(1)} - I_{A(2)} | \le C_{A(1),A(2)}$$. Данная константа зависит от выбора универсального метода программирования, положенного в основу каждого из вариантов ( $$A(1)$$ и $$A(2)$$ ) определения меры, то есть в рамках алгоритмического подхода максимум чего можно достичь: $$I_{A(1)}\approx I_{A(2)} $$

Следуя [51], будем рассматривать счетное множество "нумерованных объектов" $$X=\{x\}$$, каждому элементу которого поставлен в соответствие его номер $$n(x)$$ в виде конечной двоичной последовательности, начинающейся с единицы.

Считается:

Соответствие между $$X$$ и множеством двоичных последовательностей $$(\breve{N})$$ описанного вида взаимно однозначно.

$$\breve{N} \subset X$$, функция $$n(x)$$ на $$\breve{N}$$ общерекурсивна, причем для $$x \in \breve{N} l(n(x)) \le l(x)+C$$, где $$l(x)$$ - длина двоичной последовательности $$n(x)$$, а $$C$$ - некоторая константа.

Вместе с $$x$$ и $$y$$ в $$X$$ входит упорядоченная пара $$(x, y)$$, номер этой пары есть общерекурсивная функция номеров $$x$$ и $$y$$, а $$l (x , y ) \le C_{x} +l ( y )$$, где $$C_{x}$$ зависит только от $$x$$.

При таких условиях все результаты оценки "сложности" … и количества информации эквивалентны в смысле = при следующих преобразованиях:

переход к новой нумерации $$n'(x)$$, которая обладает теми же свойствами, что и $$n(x)$$, и выражается общерекурсивно через $$n(x)$$ ;

включения системы $$X$$ в более обширную систему $$X$$ и в предположении, что номера $$n'$$ в расширенной системе для элементов первоначальной системы общерекурсивно выражаются через первоначальные номера $$n.$$

Определение (А.Н. Колмогоров [51]): "относительной сложностью" объекта $$y$$ при заданном $$x$$ будем считать минимальную длину $$l(p)$$ "программы" $$p$$ получения $$y$$ из $$x$$.

Длина $$l(p)$$ "программы" $$p$$ зависит от "метода программирования", что можно выразить функцией $$\varphi (p, x)$$, которая ставит в соответствие программе $$p$$ и объекту $$x$$ объект $$y$$. Такая функция является частично рекурсивной и для нее:

$$K_{\varphi}(y/x) = \begin{cases} \min\limits_{\varphi(p,x)=y}{l(p)}\\ \infty,\text{если нет такого }p, \text{ что }\varphi(p,x)=y \end{cases}$$

Функция $$v = \varphi (u )$$ от $$u \in X$$ со значениями $$v \in X$$ называется частично рекурсивной, если она порождается частично рекурсивной функцией преобразования номеров $$n(v) = \Psi[n(u)]$$.

Частично рекурсивные функции, вообще говоря, не являются всюду определенными, и поэтому нет регулярного процесса для выяснения того, приведет ли программа $$p $$, примененная к объекту $$x$$, вообще к какому-либо результату. По этой причине функция $$K_{\varphi}(y/x)$$ не обязана быть эффективно вычислимой (общерекурсивной) даже в случае, когда она заведомо конечна при любых $$x$$ и $$y$$.

Теорема (А.Н. Колмогоров [51]): существует такая частично рекурсивная функция $$A(p, x)$$, что для любой другой частично рекурсивной функции $$w (p, x)$$ выполнено неравенство $$K_{A} (y/x) < K_{\varphi}(y/x)+C $$, где константа $$C_{\varphi}$$ не зависит от $$x$$ и $$y$$.

Доказательство этой теоремы опирается на существование универсальной частично рекурсивной функции $$Ф(n , u )$$, которая обладает тем свойством, что, фиксируя надлежащим образом номер $$n$$, можно получить любую другую частично рекурсивную функцию по формуле $${\varphi}(u ) = Ф(n , u )$$, где $$Ф(n , u )$$ определена только в случае $$n \in\breve{N}$$. Такая универсальная частично рекурсивная функция определяется соотношением:

$$A((n, q), x) = Ф(n, (q, x)),$$

где $$A(p, x)$$ определена только в случае, когда $$p$$ имеет вид $$(n, q), n \in \breve{N}$$.

Функции $$A(p, x)$$, удовлетворяющие теореме Колмогорова, а вместе с ней и определяемые ими методы программирования, принято называть асимптотически оптимальными, и для них "сложность" $$K_{A} (y/x)$$ конечна при любых $$x$$ и $$y$$. Поэтому для двух таких функций $$A$$ и $$A'$$: $$|K_{A}(y/x) - K_{A'} (y/x) | \le C_{A ,A'}$$, где $$C_{A, A'} $$, не зависит от $$x$$ и $$y$$, то есть $$K_{A}(y/x) \approx K_{A'} (y /x )$$.

С учетом, что "сложность объекта $$y$$ " $$K_{A} (y) = K_{A} (y/1)$$, "количество информации в $$x$$ относительно $$y$$ " определяется соотношением $$I_{A} ( x : y) = [ K_{A}(y) - K_{A}(y/x)] \stackrel{\sim}{\succ} 0$$, где символ $$\stackrel{\sim}{\succ}$$ понимается в том смысле, что $$I_A (x : y )$$ не меньше некоторой отрицательной константы $$C $$, зависящей только от условностей выбранного метода программирования. В результате в рамках алгоритмического подхода под "большим" понимается количество информации, для которого $$\ C \$$ пренебрежимо мал, а $$K_{A} (x / x) = 0$$ и $$I_{A} ( x : x ) \approx K_{A} ( x)$$, как это имеет место в комбинаторном и вероятностном подходах.

Из приведенных данных видно, что в рамках алгоритмического подхода избавиться от неопределенностей в оценке количества информации, связанных с константами $$C_{\varphi} $$, можно только для определенных классов объектов $$X$$, фиксированных нумераций и фиксированных функций $$A$$ (методов программирования). Такие условия характерны для алгоритмически ориентированных вычислителей и "дочерних" нейро-ЭВМ, при выборе архитектуры которых имеет смысл дать ответ на вопрос о том, по какой схеме их строить: вычислительной или перечислительной.

Все использованные А.Н. Колмогоровым частично рекурсивные функции вычислимы на машине Тьюринга, работающей с двузначным алфавитом и реализующей отображение [52] $$A(* | *): (n, p)\to A(p, n)$$, где $$(n, p)$$ - введенная в МТ программа, порождающая 0-1-слова $$(w_1, w _{2}, …, w_k)$$ длины $$n$$. Такой формализм позволяет решить центральную для теории вероятности проблему, связанную с определением "случайное событие". Традиционно с этим термином связывали бросание монеты в опыте Бернулли, что не корректно с точки зрения строгой математики, так как в этом случае к определению центрального понятия математической теории привлекается чисто физический процесс, с помощью которого невозможно определить никакое математическое свойство.

Отсюда и встает задача математического определения "случайной 0-1-последовательности", и сделать это надо так, чтобы основанная на этом определении математическая теория давала результаты, полностью согласованные с эмпирическими.

Первые попытки такой формализации "случайности" были предприняты фон Мизесом [53], который исходил из понятия "беспорядочной последовательности", считая, что "беспорядочность" является основным признаком "случайности". С этой целью он предложил называть бесконечную 0-1-последовательность случайной, если в ней относительная частота появления "единиц" стремится к $$1/2$$ и это свойство сохраняется при переходе к произвольной подпоследовательности с использованием любого правила выбора. При таком подходе главная трудность состояла в строгом определении термина "правило выбора". Такое уточнение было получено А. Вальдом, но вскоре вся программа фон Мизеса было опровергнута Д. Виллем [52], который построил 0-1-последовательность, удовлетворяющую требованиям фон Мизеса с частотой "единиц" не менее $$1/2$$.

Затем в теории вероятности наступил "колмогоровский" период, когда ее стали рассматривать как прикладную теорию меры. В этом случае речь может идти только о множествах последовательностей, а не об индивидуальных последовательностях. Несмотря на успехи своей теории, А.Н. Колмогоров все же вернулся к логическим основам теории вероятности [54] и предложил использовать (3.8) для оценки энтропии:

$$H(y/x) = \min\limits_{A(p,x)=y}{l(p)}.$$

Отсюда, существуют 0-1-последовательности, для которых энтропия не меньше их длины $$Н(х) \ge l(х)$$. По здравому смыслу такие последовательности и следует относить к "случайным", так как в них отсутствуют закономерности, сокращающие длину программы для машин Тьюринга.

Таким образом, если программа $$p$$ "сложнее", чем порождаемая ею последовательность $$х$$, то, по Колмогорову, такую последовательность следует считать "случайной".

Системотехнические выводы по лекции 3

Традиционно считается, что нейрокомпьютерные технологии вторичны по отношению к классическим фон-неймановским технологиям, так как в формальных нейронах логические преобразования реализуются через арифметические. В реальности для работы любого вычислителя достаточно двух традиционных для нейрокомпьютерной техники "элементарных" операций: "ассоциативная выборка" и "подстановка" (замещение) символов. Этот вывод парадоксален только на первый взгляд, так как реальные нейроны появились задолго до того, как человек стал использовать понятие "число". Поэтому для обеспечения жизнедеятельности реальных нейронов можно было привлечь только "нечисленные" методы и средства "ассоциативной выборки" и "подстановки" (замещения) символов. Отсюда, имеются достаточные основания считать первичными нейрокомпьютерные технологии, а вторичными - традиционные вычислительные технологии, на схемотехническом уровне которых в неявном виде для каждой арифметико-логической операции используется "схемотехнически сжатые" таблицы ассоциативной выборки и подстановки символов $$\{0,1\}$$.

Первичность нейрокомпьютерных технологий по отношению к компьютерным предопределяет сама логика формализации: от эмпирической таблицы к аналитическому или алгоритмическому представлению. Поэтому разница между компьютерными и нейрокомпьютер-ными технологиями в конечном счете состоит в уровне доступности пользователя к операционному базису. В нейрокомпьютерных технологиях пользователю доступен сетевой уровень управления и "элементарные операции", реализуемые отдельными элементами сети. В традиционных вычислительных технологиях с помощью "элементарных операций" (микрокоманд) производитель процессора формирует ассемблерные команды, которые для пользователя уже являются "неделимой единицей проекта". В итоге задание пользователя в нейрокомпьютерных технологиях можно представить тривиальной таблицей соответствия между входными воздействиями и требуемыми реакциями. В традиционных вычислительных технологиях требуется не только формализованное представление задания, но и алгори тм, регламентирующий в конечном счете последовательность выполнения ассемблерных команд.

Само понятие "алгоритм" уже предполагает некоторую последовательность информационно связанных преобразований конструктивных объектов. Это ограничивает реально реализуемые схемы распараллеливания вычислений векторизацией и конвейеризацией соответственно информационно независимых и информационно зависимых подпоследовательностей преобразований, а также их комбинациями типа векторно-конвейерная или конвейерно-векторная.

Контекстным системотехническим обоснованием экстенсиональной эквивалентности традиционных и нейроподобных ЭВМ служит сводимость вычислительных по Тьюрингу процедур к перечислимым по Тьюрингу процедурам, первые из которых составляют операционный базис ЭВМ одной из традиционных архитектур, а вторые - одной из ней-рокомпьютерных архитектур. Поэтому имеются достаточные основания утверждать, что любой нейро-ЭВМ можно поставить в соответствие классическую ЭВМ, эквивалентную по вычисляемой функции, и наоборот.

Оценку алгоритмической сложности реальных (нейро)компьютерных реализаций можно провести только с определенной погрешностью и при достаточно жестких ограничениях на используемые вычислительные и/или перечислительные алгоритмы, что характерно для алгоритмически ориентированных областей применения традиционных вычислителей и "дочерних" нейро-ЭВМ, а не для машин общего назначения.