ВУЗ:
Составители:
Рубрика:
69
11. МАШИНА ТЬЮРИНГА
Машина Тьюринга — это математическая модель идеализиро-
ванной цифровой вычислительной машины. Идея такой машины, пред-
ложенная английским математиком А.Тьюрингом в тридцатых годах
XX века, связана с его попыткой дать точное математическое определение
понятия алгоритма.
Машина Тьюринга (МТ) состоит из четырех частей: ленты, считы-
вающей головки, устройства управления и внутренней памяти.
1. Лента (внешняя память МТ) — бесконечная в обе стороны полоска,
разбитая на ячейки (равные клетки). В каждую ячейку в дискретный
момент времени может быть записан только один символ (буква) из
внешнего алфавита
{
}
2
121
³
L
=
-
n,a,,a,a,A
n
K
. Пустая ячейка обо-
значается символом
L
. В этом алфавите
A
в виде слова (конечного
упорядоченного набора символов) кодируется та информация, которая
подается в МТ. Машина перерабатывает информацию, поданную в виде
слова, в новое слово.
2. Считывающая головка (некий считывающий элемент) перемещается
вдоль ленты так, что в каждый момент времени она обозревает ровно
одну ячейку ленты. Головка может считывать содержимое ячейки и
записывать в нее новый символ из алфавита
A
. В одном такте работы
она может сдвигаться только на одну ячейку вправо (
П
), влево (
Л
)
или оставаться на месте (
Н
). Обозначим множество перемещений
(сдвига) головки
{
}
Н,Л,ПD
=
.
3. Память машины представляет собой некоторое конечное множество
внутренних состояний
{
}
1
1210
³
=
-
m,q,,q,q,qQ
m
K
. Будем считать,
что мощность 2
³
Q . Два состояния машины имеют особое назначе-
ние:
1
q — начальное внутреннее состояние,
0
q — заключительное
внутреннее состояние (стоп-состояние). Машина работает во времени,
которое считается дискретным и его моменты занумерованы: 1, 2, 3, … .
В каждый момент времени МТ характеризуется положением головки и
внутренним состоянием. Например, под ячейкой, над которой находит-
ся головка, указывается внутреннее состояние машины.
¯
L
2
a
1
a
L
2
a
3
a
L
1
q
4. Устройство управления (УУ) в каждый момент времени
t
в зависимо-
сти от внутреннего состояния машины и считывающего в этот момент
11. МАШИНА ТЬЮРИНГА Машина Тьюринга — это математическая модель идеализиро- ванной цифровой вычислительной машины. Идея такой машины, пред- ложенная английским математиком А.Тьюрингом в тридцатых годах XX века, связана с его попыткой дать точное математическое определение понятия алгоритма. Машина Тьюринга (МТ) состоит из четырех частей: ленты, считы- вающей головки, устройства управления и внутренней памяти. 1. Лента (внешняя память МТ) — бесконечная в обе стороны полоска, разбитая на ячейки (равные клетки). В каждую ячейку в дискретный момент времени может быть записан только один символ (буква) из внешнего алфавита A � �� , a1 , a 2 ,� , a n�1 �, n � 2 . Пустая ячейка обо- значается символом � . В этом алфавите A в виде слова (конечного упорядоченного набора символов) кодируется та информация, которая подается в МТ. Машина перерабатывает информацию, поданную в виде слова, в новое слово. 2. Считывающая головка (некий считывающий элемент) перемещается вдоль ленты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. Головка может считывать содержимое ячейки и записывать в нее новый символ из алфавита A . В одном такте работы она может сдвигаться только на одну ячейку вправо ( П ), влево ( Л ) или оставаться на месте ( Н ). Обозначим множество перемещений (сдвига) головки D � �П , Л , Н �. 3. Память машины представляет собой некоторое конечное множество внутренних состояний Q � �q 0 , q1 , q 2 , � , q m �1 �, m � 1. Будем считать, что мощность Q � 2 . Два состояния машины имеют особое назначе- ние: q1 — начальное внутреннее состояние, q0 — заключительное внутреннее состояние (стоп-состояние). Машина работает во времени, которое считается дискретным и его моменты занумерованы: 1, 2, 3, … . В каждый момент времени МТ характеризуется положением головки и внутренним состоянием. Например, под ячейкой, над которой находит- ся головка, указывается внутреннее состояние машины. � � a2 a1 � a2 a3 � q1 4. Устройство управления (УУ) в каждый момент времени t в зависимо- сти от внутреннего состояния машины и считывающего в этот момент 69
Страницы
- « первая
- ‹ предыдущая
- …
- 67
- 68
- 69
- 70
- 71
- …
- следующая ›
- последняя »