Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 78 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
124
ложенная английским математиком А .Тьюрингом в тридцатых годах XX
века , связана с его попыткой дать точное математическое определение по -
нятия алгоритма.
Машина Тьюринга (МТ) состоит из четырех частей: ленты,
считывающей головки, устройства управления и внутренней памяти.
1. Лента (внешняя память МТ) — бесконечная в обе стороны полоска ,
разбитая на ячейки (равные клетки). В каждую ячейку в дискретный
момент времени может быть записан только один символ (буква ) из
внешнего алфавита
{
}
2
121
≥
Λ
=
−
n,a,,a,a,A
n
K . Пустая ячейка обо -
значается символом
Λ
. В этом алфавите
A
в виде слова (конечного
упорядоченного набора символов) кодируется та информация, которая
подается в МТ. Машина перерабатывает информацию , поданную в виде
слова , в новое слово.
2. Считывающая головка (некий считывающий элемент) перемещается
вдоль ленты так, что в каждый момент времени она обозревает ровно
одну ячейку ленты. Головка может считывать содержимое ячейки и
записывать в нее новый символ из алфавита
A
. В одном такте работы
она может сдвигаться только на одну ячейку вправо (
П
), влево (
Л
)
или оставаться на месте (
Н
). Обозначим множество перемещений
(сдвига ) головки
{
Н,Л,ПD
=
.
3. Память машины представляет собой некоторое конечное множество
внутренних состояний
{
}
1
1210
≥
=
−
m,q,,q,q,qQ
m
K . Будем считать,
что мощность
2≥Q
. Два состояния машины имеют особое назначе-
ние:
1
q — начальное внутреннее состояние,
0
q — заключительное
внутреннее состояние (стоп-состояние). Машина работает во времени,
которое считается дискретным и его моменты занумерованы: 1, 2, 3, … .
В каждый момент времени МТ характеризуется положением головки и
внутренним состоянием. Например, под ячейкой, над которой находит-
ся головка , указывается внутреннее состояние машины.
↓
Λ
2
a
1
a
Λ
2
a
3
a
Λ
1
q
4. Устройство управления (УУ) в каждый момент времени
t
в зависимо-
сти от внутреннего состояния машины и считывающего в этот момент
символа на ленте, над которым находится головка , выполняет следую-
щие действия:
a) «считывает» символ
i
a
— заменяет на новый символ
j
a (может быть
ij
aa
=
); 
                                           124
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
ложенная английским математиком А.Тьюрингом в тридцатых годах XX
века, связана с его попыткой дать точное математическое определение по-
нятия алгоритма.
      Машина Тьюринга (МТ) состоит из четырех частей: ленты,
считывающей головки, устройства управления и внутренней памяти.
1. Лента (внешняя память МТ) — бесконечная в обе стороны полоска,
   разбитая на ячейки (равные клетки). В каждую ячейку в дискретный
   момент времени может быть записан только один символ (буква) из
   внешнего алфавита A ={Λ , a1 , a 2 , , a n −1 }, n ≥2 . Пустая ячейка обо-
   значается символом Λ . В этом алфавите A в виде слова (конечного
   упорядоченного набора символов) кодируется та информация, которая
   подается в МТ. Машина перерабатывает информацию, поданную в виде
   слова, в новое слово.
2. Считывающая головка (некий считывающий элемент) перемещается
   вдоль ленты так, что в каждый момент времени она обозревает ровно
   одну ячейку ленты. Головка может считывать содержимое ячейки и
   записывать в нее новый символ из алфавита A . В одном такте работы
   она может сдвигаться только на одну ячейку вправо ( П ), влево ( Л )
   или оставаться на месте ( Н ). Обозначим множество перемещений
   (сдвига) головки D ={П , Л , Н }.
3. Память машины представляет собой некоторое конечное множество
   внутренних состояний Q ={q0 , q1 , q 2 ,  , q m −1 }, m ≥1. Будем считать,
   что мощность Q ≥2 . Два состояния машины имеют особое назначе-
   ние: q1 — начальное внутреннее состояние, q0 — заключительное
   внутреннее состояние (стоп-состояние). Машина работает во времени,
   которое считается дискретным и его моменты занумерованы: 1, 2, 3, … .
   В каждый момент времени МТ характеризуется положением головки и
   внутренним состоянием. Например, под ячейкой, над которой находит-
   ся головка, указывается внутреннее состояние машины.
                      ↓
                 Λ    a2     a1      Λ     a2      a3     Λ
                      q1
4. Устройство управления (УУ) в каждый момент времени t в зависимо-
   сти от внутреннего состояния машины и считывающего в этот момент
   символа на ленте, над которым находится головка, выполняет следую-
   щие действия:
a) «считывает» символ a i — заменяет на новый символ a j (может быть
   a j =a i );

Страницы