ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.02.2021
Просмотров: 186
Скачиваний: 1
Машина
Тьюринга
.
Концепция
этой
машины
возникла
в
середине
30-
х
гг
. 20
в
.
у
А
.
Тьюринга
в
результате
произведенного
им
анализа
действий
человека
,
выполняющего
в
соответствии
с
заранее
разработанным
планом
те
или
иные
вычисления
,
т
.
е
.
последовательные
преобразования
знаковых
комплексов
.
Например
,
производя
вычисления
согласно
избранному
плану
,
математик
,
рассматривая
к
.-
л
.
место
в
своих
записях
и
находясь
в
определенном
“
умонастроении
”,
делает
необходимые
изменения
в
написанном
,
проникается
новым
“
умонастроением
”
и
переходит
к
рассмотрению
дальнейших
записей
.
Машина
Тьюринга
состоит
из
:
1)
управляющего
устройства
,
которое
может
находиться
в
одном
из
состояний
,
образующих
конечное
множество
Q
= {
q
1
, q
2
,…, q
n
}; 2)
ленты
,
разбитой
на
ячейки
,
в
каждой
из
которых
может
быть
записан
один
из
символов
конечного
алфавита
А
= {
а
1
, …, a
m
};
3)
устройства
обращения
к
ленте
,
т
.
е
.
считывающей
и
пишущей
головки
,
которая
в
каждый
момент
времени
обозревает
ячейку
ленты
,
в
зависимости
от
символа
в
этой
ячейке
и
состояния
управляющего
устройства
записывает
в
ячейку
символ
(
быть
может
,
совпадающий
с
прежним
или
пустой
,
т
.
е
.
стирает
символ
),
сдвигается
на
ячейку
влево
или
вправо
или
остается
на
месте
;
при
этом
управляющее
устройство
переходит
в
новое
состояние
(
или
остается
в
старом
).
Среди
состояний
управляющего
устройства
выделены
начальное
состояние
q
1
и
заключительное
состояние
,
которое
будем
обозначать
q
z
(z
здесь
понимается
не
как
числовая
переменная
,
а
как
мнемонический
знак
конца
).
В
начальном
состоянии
машина
находится
перед
началом
работы
;
попав
в
заключительное
состояние
,
машина
останавливается
.
Таким
образом
,
память
машины
Тьюринга
-
это
конечное
множество
состояний
(
внутренняя
память
)
и
лента
(
внешняя
память
).
Лента
бесконечна
в
обе
стороны
,
однако
в
начальный
момент
времени
только
конечное
число
ячеек
ленты
заполнено
непустыми
символами
,
остальные
ячейки
пусты
,
т
.
е
.
содержат
пустой
символ
λ
(
пробел
).
Из
характера
работы
машины
следует
,
что
и
в
любой
последующий
момент
времени
лишь
конечный
отрезок
ленты
будет
заполнен
символами
.
Поэтому
важна
не
фактическая
(
как
говорят
в
математике
,
актуальная
)
бесконечность
ленты
,
а
ее
неограниченность
,
т
.
е
.
возможность
писать
на
ней
сколь
угодно
длинные
,
но
конечные
слова
.
Данные
машины
Тьюринга
-
это
слова
в
алфавите
ленты
;
на
ленте
записываются
и
исходные
данные
,
и
окончательные
результаты
.
Элементарные
шаги
машины
—
это
считы
-
вание
и
запись
символов
,
сдвиг
головки
на
ячейку
влево
и
вправо
,
а
также
переход
управляющего
устройства
в
следующее
состояние
.
Детерминированность
машины
,
т
.
е
.
последовательность
ее
шагов
,
определяется
следующим
образом
:
для
любого
внутреннего
состояния
q
i
и
символа
а
j
однозначно
заданы
:
а
)
следующее
состояние
q
i
’
,
б
)
символ
a
j
'
,
который
нужно
записать
вместо
а
j
в
ту
же
ячейку
(
стирание
символа
будем
понимать
как
запись
пустого
символа
λ
);
в
)
направление
сдвига
головки
d
k
,
обозначаемое
одним
из
трех
символов
:
L
(
влево
),
R
(
вправо
),
Е
(
на
месте
).
Это
задание
может
описываться
либо
системой
правил
(
команд
),
имеющих
вид
d
a
q
a
q
k
j
i
j
i
'
'
→
(1)
либо
таблицей
,
строкам
которой
соответствуют
состояния
,
столбцам
—
входные
символы
,
а
на
пересечении
строки
q
i
и
столбца
а
j
,
записана
тройка
символов
d
a
q
k
j
i
'
'
,
и
,
наконец
,
блок
-
схемой
,
которую
будем
называть
диаграммой
пере
-
ходов
.
В
этой
диаграмме
состояниям
соответствуют
вершины
,
а
правилу
вида
(1)
—
ребро
,
ведущее
из
q
i
в
q
i
'
,
на
котором
написано
d
a
a
k
j
j
'
→
.
Условие
однозначности
требует
,
чтобы
для
любого
j
и
любого
z
i
≠
в
системе
команд
имелась
одна
команда
,
аналогичная
(1),
с
левой
частью
a
q
j
i
состояние
q
z
в
левых
частях
команд
не
встречается
.
На
диаграмме
переходов
это
выражается
условием
,
что
из
каждой
вершины
,
кроме
q
z
,
выходят
ровно
т
ребер
,
причем
на
разных
ребрах
левые
части
различны
;
в
вершине
q
z
нет
выходящих
ребер
.
Возможно
ли
для
всех
процедур
,
претендующих
на
алгоритмичность
,
т
.
е
.
конструктивных
процедур
,
строить
реализующие
их
машины
Тьюринга
?
Согласно
тезису
Тьюринга
всякий
алгоритм
может
быть
реализован
машиной
Тьюринга
.
Доказать
тезис
Тьюринга
невозможно
,
поскольку
само
понятие
алгоритма
(
или
эффективной
процедуры
)
является
неточным
.
Подтверждением
тезиса
Тьюринга
является
,
во
-
первых
,
математическая
практика
,
а
во
-
вторых
,
то
обстоятельство
,
что
описание
алгоритма
в
терминах
любой
другой
известной
алгоритмической
проблемы
может
быть
сведено
к
его
описанию
в
виде
машины
Тьюринга
.
Тезис
Тьюринга
позволяет
,
с
одной
стороны
,
заменить
неточные
утверждения
о
существовании
эффективных
процедур
(
алгоритмов
)
точными
утверждениями
о
существовании
машин
Тьюринга
,
а
с
другой
стороны
,
утверждениям
о
несуществовании
машин
Тьюринга
истолковать
как
утверждения
о
несуществовании
алгоритмов
вообще
.
Большой
теоретический
интерес
представляет
задача
о
построении
универсальной
машины
,
которая
для
любого
алгоритма
и
любых
исходных
данных
может
определить
,
приведет
ли
работа
этого
алгоритма
к
результату
или
нет
(
проблема
остановки
).
Можно
доказать
теорему
,
что
не
существует
машины
Тьюринга
T
0
,
решающей
проблему
остановки
для
произвольной
машины
Тьюринга
T
.
Поэтому
данная
теорема
дает
первый
пример
алгоритмически
неразрешимой
проблемы
.
Речь
здесь
идет
об
отсутствии
единого
алгоритма
,
решающего
некоторую
проблему
;
при
этом
вовсе
не
исключается
возможность
решения
этой
проблемы
в
частных
случаях
,
но
различными
средствами
для
каждого
случая
.
Т
.
е
.
поиск
доказательства
сходимости
предлагаемых
алгоритмов
нельзя
полностью
автоматизировать
.
Неразрешимость
проблемы
остановки
можно
интерпретировать
как
несуществование
общего
алгоритма
для
отладки
программ
,
точнее
,
алгоритма
,
который
по
тексту
любой
программы
и
данным
для
нее
определял
бы
,
зациклится
ли
программа
на
этих
данных
или
нет
.
Тем
не
менее
,
благодаря
опыту
и
искусству
программиста
большинство
программ
в
конце
концов
удается
отладить
.
