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


           

слева соответствует конфигурация K=


Пример 9.1.


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

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

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

Вычисление м.Т.
на входе w - это конечная или бесконечная последовательность конфигураций


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

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

Скажем, что две м.Т.
и
эквивалентны, если они вычисляют одинаковые функции.

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

Определение 9.6. Скажем, что м.Т.
вычисляет частичную арифметическую функцию f: Nk
N, если для любого набора чисел (x1,x2, … ,xk), на котором f определена, существует результативное вычисление
на входе
с результатом


а если f(x1,x2,… ,xk)=?, то вычисление
на соответствующем входе бесконечно.

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


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