Введение в схемы, автоматы и алгоритмы



             

Основные определения - часть 3


Пример 9.1.

Выполнение команды q3 0 -> q5 1 П

Рис. 9.1.  Выполнение команды q3 0 -> q5 1 П

Например, ситуации, представленной на рис.9.1 слева соответствует конфигурация K= 1q301

0. Предположим, что программа P содержит команду q30
q51 П. Тогда после выполнения этой команды K перейдет за один шаг в конфигурацию K'= 11q51
0, показанную на этом рисунке справа. Следовательно,
K \vdash K^\prime
.

Определение 9.4.

Вычисление м.Т.

{\cal M}\
на входе w - это конечная или бесконечная последовательность конфигураций
K_0 \vdash K_1 \vdash\ldots \vdash K_t\vdash K_{t+1}\ldots

такая, что K0=q0w - начальная конфигурация. Эта последовательность конечна, когда ее последняя конфигурация Kn= v1 qf v2 - заключительная. В этом случае вычисление назовем результативным, а слово v = v1 v2 - его результатом на входе w (всегда будем предполагать, что v не содержит пустых символов слева и справа).

Определение 9.5. Скажем, что м.Т.

{\cal M}\
вычисляет частичную словарную функцию
f:\ \Sigma^* \rightarrow \Sigma^*,\
если для каждого слова w из области определения f существует результативное вычисление
{\cal M}\
с результатом
f(w),
а если f(w) не определена
(f(w)=\infty),
то вычисление
{\cal M}\
на входе w бесконечно.

Скажем, что две м.Т.

{\cal M}_1
и
{\cal M}_2\
эквивалентны, если они вычисляют одинаковые функции.

Далее мы будем также рассматривать вычисления арифметических функций, т.е. функций с натуральными аргументами, принимающих натуральные значения. Для представления натуральных чисел используем унарное кодирование: число n будет представляться как слово из n палочек |n, а последовательные аргументы будем отделять *.

Определение 9.6. Скажем, что м.Т.

{\cal M}\
вычисляет частичную арифметическую функцию f: Nk
N, если для любого набора чисел (x1,x2, … ,xk), на котором f определена, существует результативное вычисление
{\cal M}\
на входе
|^{x_1}* |^{x_2}*\ldots * |^{x_k}
с результатом
|^{f(x_1,x_2,\ldots ,x_k)},

а если f(x1,x2,… ,xk)=?, то вычисление

{\cal M}\
на соответствующем входе бесконечно.

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




Содержание  Назад  Вперед