Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

\ -

А

0

l

<7i

<7i0n

<7оОП

\ ^

А

А

0

1

0

1

Q

^

Q

•

— '

% •

д3\Л

<72 /

д3Ш

д21Л

?4

—

доОЛ

пами единиц, оставляя всего одну незаполненную ячейку.

'

Машина Г9 имеет два

заключительных

состояния — до'

и до":

л

0

1

Q

\

4i

_

<72Ш

92

<?о'ОЛ

<7о"1Л

ки, машина обнаруживает, что записано

в соседней ячейке

слева:

О или 1. В зависимости от этого

она переходит в состояние

до' или

до" и останавливается в исходной ячейке.

Машина Ti0:

А

0

1

Q

/

.

?о1С

дъ\Л

?2

9Х 0Л

?2 1Л

А

0

1

Q

Qi

?2оп

Q2

<7о1Л

<721П

0

1

Qi

q%QJ\

д2 1Л

92

?0 0С

9оОС

ходной

(если там есть «I»).

машины Р из машин Т3, 1\, Те,

Рассмотрим пример построения

Т\и Ti2c

помощью композиций итерации и произведения по следую­

щей формуле:

(1)

7-,

(2)

TuTtT9.

\ .

А

1

А

0

0

1

<э

\

Q

\

Qi

?2 0Л

Qi

<7вОЛ

(?81Л

92

g

in

<?oc

<?90С

2

?9

9

<7з

(?40С

<?71C

?юОЛ

<7Э1Л

. Qi

?Б 0Л-

qtin

-

Qio

<7юОЛ

?ц1Л

Qi

<7Б0Л

9е1Л

Qii

<7120Л

<?и!Л-

<?e

?в 1Л

,

<?12

9о1С

(7121Л

таблицей

соответствия:

\_

А

1

А

1

Q

0

Q

0

^

•

Ql

</20П

«4

qfiU

<7„0Л

Qi

}ъ

—

Qs

(?40Л

<761Л

<7« '

<7о1С

9.1 л

Машина Rm строится из машин Т\, Т3,

Т6, T-j, Т%, Тд, Ti0 по фо

муле

Р — Т

ТтТ

(1)

W

(2) Т7Т?Тв>

где tn — степень соответствующей машины.

В частности,

1 0

1

9 l ( 2 ) W e .

в стандартном положении,

машина Rm печатает

справа

от пред-

t ставления чисел хъ ..., хт

первое из этих чисел

(т. е. Xi)

и оста-"

чисел

(xi, . . . , хт,

Xi). Если же машина Rm

воспринимает в началь­

ный момент

времени в стандартном положении

систему

чисел

хи ...,

хп,

где п>

т, то она отпечатает справа от этой системы чисел

число хп-т+

1 и остановится, воспринимая

систему

(xi, х%,

хп,

Хп—т +

1)

•

•

° т — 1 б ^ т ' 7' 1 1 7' з •

Машина

Sm

делает

почти то же, что и машина Rmm,

т. е. копирует

систему

чисел (xit

xm)

справа,

но не с одним

промежутком,

а с двумя

(т. е. между числами хт

и xi

расположены две пустые

ячейки).

чисел (хи

хг),

где Х\ = 2, х% = 4. Тогда

Пусть

имеется система

1)

машина Т находится в начальном состоянии <?i;

2)

на ленте представлена система п чисел {хи

х п ) , которую

•\

*

3)

все ячейки, расположенные правее той, напротив которой на­

ходится головка, пусты.

функцию х = cp(xi, . . . , хп)

Будем

считать, что Т вычисляет

от п

переменных, если каковы бы ни были числа xit

...,

хп

существует

такой момент времени, в который:

1)

машина

Т достигает заключительного состояния до;

2)

на ленте будет представлена система п +

1 чисел xi,

•.., хп, х,

где x~cp(xi,

х п ) , которую головка

машины

воспринимает в

стандартном положении;

3)

все ячейки, расположенные правее той, напротив которой на­

ходится головка, пусты.

Если же для какой-либо системы чисел (х\,

..., хп)

машина ни­

когда не останавливается

или останавливается, но при этом не вы­

полнено 2 или 3 условие, то такая машина не вычисляет

значения

функции ф при этих значениях

аргументов.

ХЪ Х3) = * i + хг + х%.

Рассмотрим

пример.

Пусть п = 3,

ф(лсь

Тогда

при Xi = 3, хг = 3, х3 — 4 начальная конфигурация

на ленте

будет

иметь вид 00 111 0 11 0 1111 0, а заключительная

ситуация

запишется

.так 00 111 0 11 0 1111 0 1111111110.

Считывающая

го­

ловка при этом расположена

над крайней правой единицей.

Рассмотрим

машины

Тьюринга,

вычисляющие

элементарные

мент число х в стандартном положении, машина запишет

S (х) = ,

— х + 1 правее числа х и остановится в стандартном

положении

(х,

х+ Г), т. е. вычислит функцию

непосредственного

следования.

Константную функцию Он(хи

хп) — q

вычисляет

машина

Т = ТыТвЧ, которая правее системы чисел (хь

хп)

записывает q

и останавливается.

хп) = Хг вычисляет

Тождественную функцию Iin{xu

маши­

на

Т = Rn-i+i.

Действительно, эта машина

правее системы

чисел

(xi,

...., хп)

записывает (п — i + 1)-е число, т. е. х%.

может быть

Можно доказать, что любая рекурсивная

функция

Имеет, место следующая теорема Тьюринга

(1). Для

каждой

частично рекурсивной словарной функции f(xi,

xg),

определен­

ной в некотором алфавите а\, ...,

ат, существует

машина

Тьюрин­

га с символами ао, а ь . . . , ат и подходящими

внутренними

состоя­

ниями, которая вычисляет функцию f(xi,

xg).

из простей­

Каждая частично рекурсивная

функция получается

га будет доказана, если нам удастся решить следующие

частичные

задачи:

\ 1

1. Построить

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

простейшие

арифметические

функции.

41