Теория алгоритмов и формальных языков. Мелихов А.Н - 34 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Пусть заданы некоторая МТ Z с состояниями q
0
, q
1
, …, q
m
и
натуральный ряд чисел N (включая ноль). Поставим в соответствие каждой n-
ке (а
1
, а
2
, …, а
n
), где Nа
i
∈ ,
ni ,...,2,1
=
, конфигурацию
n
aaaq ...
2101
=
α
. Если для
Z существует вычисление, начинающееся в конфигурации
α
1
и доходящее до
заключительной конфигурации
α
р
:
α
1
α
2
…
α
р
, то число Nр
∈
, сопоставляемое
α
р
, есть значение функции от Z и начальной n-ки, т.е. ),...,,(
21 nz
ааар
ψ
=
. Если
не существует такого числа р, что конфигурация
α
р
является
заключительной, то функция
ψ
z
не определена для рассматриваемой n-ки и Z
работает вечно. Таким образом, исходя из Z, мы пришли к функции с
областью определения на множестве N
n
(или, быть может, на некоторои
подмножестве N
n
), где N
n
- множество всевозможных упорядоченных n-ок из
N.
Будем исходить теперь из функций, определенных на N
n
или его
подмножестве. Функция f, определенная на некотором подмножестве
множества N
n
, является частично вычислимой, если существует МТ Z, такая,
что для всякой n-ки (х
1
, х
2
, …, х
n
), которой отвечает некоторое значение f,
выполняется равенство
),...,,(),...,,(
2121 nzn
xxxxxxf
ψ
=
.
Функция f называется вычислимой, если она определена на N
n
и является
частично вычислимой.
Примером вычислимой функции является функция
yxyxf
+
=
),( ,
поскольку в разделе 2.2 для нее мы построили МТ, исчисляющую значения
),( yxf
для любых х, y.
Пример 2.2. Покажем, что функция
2121
),( хxхxf ×= является
вычислимой. Доказательство заключается в построении МТ, заданной
диаграммой. Пусть на ленте записано сначала
1
х , а через пробел -
2
х . Будем
считать, что результат получен, если на ленте осталось столько подряд
стоящих палочек, чему равно истинное значение произведения
21
хx × . Итак,
первоначально на ленте записано следующее:

Страницы