Теория алгоритмов. Зюзысов В.М. - 12 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

абстрактного к конкретному: фон Нейман был знаком с работой Тьюринга, и сам Тьюринг
позднее сыграл вдохновляющую роль в развитии вычислительных машин.
На неформальном уровне мы можем описывать машину Тьюринга как некий
черный ящик с лентой. Лента разбита на ячейки, и каждая ячейка может содержать пустой
символ 0 либо непустой символ 1. Лента
потенциально бесконечна в обе стороны в том
смысле, что мы никогда не придем к ее концу, но в любое время лишь конечное число
ячеек может быть непустым. В начале лента содержит числа входа, в конце – число–
выход. В промежуточное время лента используется как пространство памяти для
вычисления.
Если мы откроем черный
ящик, то обнаружим, что он
устроен очень просто. В любой момент времени он может
обозревать лишь одну ячейку памяти. Устройство содержит
конечный список инструкций (или состояний) q
0
, q
1
,..., q
n
.
Каждая инструкция может указать два возможных направления
действий; одного нужно придерживаться, если на обозреваемой
ячейке ленты находится 0, а другого – если там находится 1. В
любом случае следующее действие может состоять из таких
трех типов элементарных шагов:
Алан Тью
р
инг
символ (возможно, такой же, как старый) пишется на
обозреваемой ячейке ленты, при этом предыдущий
символ
стирается;
•
•
•
лента сдвигается на одну ячейку влево или вправо;
указывается следующая инструкция.
Таким образом, список инструкций определяет некоторую функцию перехода,
которая по данной инструкции и обозреваемому символу указывает три компоненты того,
что нужно делать. Мы можем формализовать эти идеи, взяв в качестве машины Тьюринга
эту функцию перехода.
Машина Тьюринга
Машина Тьюринга – это функция M такая, что для некоторого натурального числа n
область определения этой функции есть подмножество множества {0, 1,..., n}×{0, 1}, а
область значений есть подмножество множества {0, 1}×{Л, П}×{0, 1, ..., n}.
Например, пусть M(3,1) = <0, Л, 2>. Подразумеваемый смысл этого состоит в том,
что как только машина дойдет до инструкции q
3
, а на обозреваемой ячейке написан
символ 1, она должна стереть 1 (оставляя на ячейке 0), передвинуть ленту так, чтобы
обозреваемой ячейкой стала левая соседняя ячейка от той, которая обозревалась, и
перейти к следующей инструкции q
2
. Если M(3,1) не определено, тогда как только машина
дойдет до инструкции q
3
, а на обозреваемой ячейке написан символ 1, то машина
останавливается. (Это единственный путь остановки вычисления.)
Такая подразумеваемая интерпретация не включена в формальное определение
машины Тьюринга, но она мотивирует и подсказывает формулировки всех следующих
определений. В частности, можно определить, что означает для машины M передвижение
(за один шаг) от одной конфигурации до
другой. Нам не нужно здесь давать формальных
определений, так как они являются простыми переводами наших неформальных идей.
Входные и выходные данные – это строчки из 1, разделенные 0. Пусть <n> будет
строчкой из 1 длины n+1. Тогда
<n
1
> 0 <n
2
> 0 ... 0 <n
k
>
получено комбинацией k строчек из 1, каждая отделена от другой 0.
Наконец, мы можем определить вычислимость.
Вычислимость по Тьюрингу

Страницы