Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 16 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

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

Рубрика: 

1) для любых x
1
, x
2
, ..., x
n
, принадлежащих области определения функции, машина
Тьюринга из начальной конфигурации, имея на ленте представление аргументов, переходит
в заключительную конфигурацию, имея на ленте результат (представление функции);
2) для любых x
1
, x
2
, ..., x
n
, не принадлежащих области определения функции, машина
Тьюринга из начальной конфигурации работает бесконечно.
Если начальная и заключительная конфигурации машины Тьюринга являются
стандартными, то говорят, что машина Тьюринга правильно вычисляет функцию f.
Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга,
вычисляющая ее.
Для того чтобы доказать вычислимость функции, а в дальнейшем и существование
алгоритма, необходимо построить машину Тьюринга, реализация которой на практике
зачастую представляет собой трудоемкую задачу. В связи с этим возникает необходимость
разбиения алгоритма на отдельные задачи, каждая из которых будет решаться отдельной
машиной Тьюринга. Если объединить программы этих машин, то получится новая
программа, позволяющая решить исходную задачу.
Машины Тьюринга могут вычислять искомую функцию с восстановлением и без
восстановления. Вычисление функции с восстановлением означает работу машины
Тьюринга с сохранением исходных данных:
p
0
1
X1
* . . *
1
Xn
⇒
*
p
z
1
f(X1, X2, . . . , Xn)
*1
X1
* . . *
1
Xn
.
Приведенное определение позволяет получать на ленте сначала результат, а затем
исходные данные. В отдельных случаях удобно сделать наоборот:
p
0
1
X1
* . . *
1
Xn
⇒
*
1
X1
* . . *
1
Xn
* p
z
1
f(X1, X2, . . . , Xn)
.
Вычисление функции без восстановления означает работу машины Тьюринга без
сохранения исходных данных:
p
0
1
X1
* . . *
1
Xn
⇒
*
p
z
1
f(X1, X2, . . . , Xn)
.
Справедливо утверждение, что всякая правильно вычислимая функция правильно
вычислима с восстановлением.
3.6. Операции над машинами Тьюринга
1. Композиция машин Тьюринга. Пусть машины Т
1
и
Т
2
имеют программы Р
1
и
Р
2
.
Предположим, что внутренние алфавиты этих машин не пересекаются; пусть q
z1
-
заключительное состояние машины Т
1
, а q
02
- начальное состояние машины Т
2
. Заменим
всюду в программе Р
1
заключительное состояние q
z1
на начальное состояние q
02
машины Т
2
и полученную программу объединим с программой Р
2
. Новая программа Р определяет
машину Т, называемую композицией машин Т
1
и
Т
2
по паре состояний (q
z1
, q
02
).
Композиция машин может быть обозначена Т
1
⋅Т
2
или Т
1
Т
2
. Более подробно композиция
машин записывается следующим образом:
Т = Т(Т
1
,
Т
2
, (q
z1
, q
02
)), где
T
1
= (Q
1
, A
1
, δ
1
, p
01
, p
z1
, a
01
, a
11
),
Т
2
= (Q
2
, A
2
, δ
2
, p
02
, p
z2
, a
02
, a
12
).
Пусть a
01
= a
02
= a
0
и a
11
= a
12
= a
1.
Внешний алфавит композиции Т
1
Т
2
является
объединением внешних алфавитов машин Т
1
и
Т
2
:
p
02
Т= (Q
1
∪ Q
2
\ {p
z1
}, A
1
∪A
2
, | (δ
1
,∪ δ
2
), p
01
, p
z2
, a
0
, a
1
).
p
z1
    1) для любых x1, x2, ..., xn, принадлежащих области определения функции, машина
Тьюринга из начальной конфигурации, имея на ленте представление аргументов, переходит
в заключительную конфигурацию, имея на ленте результат (представление функции);
    2) для любых x1, x2, ..., xn, не принадлежащих области определения функции, машина
Тьюринга из начальной конфигурации работает бесконечно.
    Если начальная и заключительная конфигурации машины Тьюринга являются
стандартными, то говорят, что машина Тьюринга правильно вычисляет функцию f.
    Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга,
вычисляющая ее.
    Для того чтобы доказать вычислимость функции, а в дальнейшем и существование
алгоритма, необходимо построить машину Тьюринга, реализация которой на практике
зачастую представляет собой трудоемкую задачу. В связи с этим возникает необходимость
разбиения алгоритма на отдельные задачи, каждая из которых будет решаться отдельной
машиной Тьюринга. Если объединить программы этих машин, то получится новая
программа, позволяющая решить исходную задачу.
    Машины Тьюринга могут вычислять искомую функцию с восстановлением и без
восстановления. Вычисление функции с восстановлением означает работу машины
Тьюринга с сохранением исходных данных:

   p0 1X1* . . * 1Xn   ⇒
                        *
                            p z 1f(X1, X2, . . . , Xn) *1X1* . . * 1Xn.

    Приведенное определение позволяет получать на ленте сначала результат, а затем
исходные данные. В отдельных случаях удобно сделать наоборот:

   p0 1X1* . . * 1Xn   ⇒
                        *
                            1X1* . . * 1Xn * p z 1f(X1, X2, . . . , Xn) .

    Вычисление функции без восстановления означает работу машины Тьюринга без
сохранения исходных данных:
    p0 1X1* . . * 1Xn ⇒* p z 1f(X1, X2, . . . , Xn) .
    Справедливо утверждение, что всякая правильно вычислимая функция правильно
вычислима с восстановлением.

      3.6. Операции над машинами Тьюринга
    1. Композиция машин Тьюринга. Пусть машины Т1 и Т2 имеют программы Р1 и Р2.
Предположим, что внутренние алфавиты этих машин не пересекаются; пусть qz1 -
заключительное состояние машины Т1, а q02 - начальное состояние машины Т2. Заменим
всюду в программе Р1 заключительное состояние qz1 на начальное состояние q02 машины Т2
и полученную программу объединим с программой Р2. Новая программа Р определяет
машину Т, называемую композицией машин Т1          и Т2 по паре состояний (qz1, q02).
Композиция машин может быть обозначена Т1 ⋅Т2 или Т1Т2. Более подробно композиция
машин записывается следующим образом:
   Т = Т(Т1, Т2, (qz1, q02)), где
    T1 = (Q1, A1, δ1, p01, pz1, a01, a11),
    Т2= (Q2, A2, δ2, p02, pz2, a02, a12).
    Пусть a01 = a02 = a0 и a11 = a12 = a1.        Внешний алфавит композиции Т1Т2 является
объединением внешних алфавитов машин Т1 и Т2:
                                     p02
    Т= (Q1 ∪ Q2 \ {pz1}, A1 ∪A2, | (δ1,∪ δ2), p01, pz2, a0, a1).
                                      pz1

Страницы