Описание одноленточной машины Тьюринга

Техническое устройство, состоящее из:

1. Ленты разделенной на ячейки и бесконечной в обе стороны. В каждой ячейке может быть записан один из символов некоторого множества называемого внешним алфавитом. При этом один из символов будем считать пустым символом

2. Управляющее устройство, которое может находиться в одном из внутренних состояний – внутренний алфавит

3. Считывающая головка, которая всякий раз может обозревать только одну ячейку, может перемещаться вдоль лент и может стирать напечатанные символы и печатать новые

4. Команда. Работа машины Тьюринга проходит потактно в зависимости от внутреннего состояния машины и считываемого символа на ленте машина Тьюринга:

a) Записывает в эту ячейку символ внешнего алфавита;

b) Сдвигает считывающую головку на один шаг влево или один шаг вправо или оставляет её на месте;

c) Переходит в новое внутреннее состояние.

 

Таким образом, работа машины определяется системой команд вида

Где - внутреннее состояние машины, - считываемый символ, - новое внутреннее состояние, - новый записываемый символ, - перемещение головки вдоль ленты: L – влево, R – вправо, E – на месте.
Элементарная операция строго определена и однозначна, таким образом, для каждой пары, где i=1…n, j=0…m имеется только одна команда такого вида. Множество этих команд называется программой машины и в такой программе имеется n(m+1) команд.

Из набора внутренних состояний выделяют которые объявляются и считаются исходным и заключительным состояниями.

Работа начинается с внутреннего состояния , как только машина попадает в состояние машина Тьюринга останавливается, а слово, которое окажется на ленте является результатом.

Работа машины заключается в изменении конфигураций. Конфигурация представляет собой совокупность внутреннего состояния, состояния ленты(т.е. размещения букв или слова внешнего алфавита по ячейкам), положения головки на ленте. a

 

…

…

 

b

 

Конфигурация

Пусть некая конфигурация имеет следующий вид:

a

Тогда после выполнения команды вида новая конфигурация будет иметь вид

 

 

 

Стандартная начальная конфигурация имеет вид

Тогда работу машины Тьюринга можно представить в следующем виде

в зависимости от слова на ленте

…. и набора команд

Если приходит в состояние то машина применима к начальной конфигурации. Если же нет, то неприменима.

Если машина перешла в состояние и при этом считывающая головка находится на первой ячейке, то говорят что машина находится в канонической(стандартной) форме. Если машина не в стандартной форме т.е. находится на произвольной ячейке, то машину всегда можно привести к канонической форме, путём добавления новых команд.

, где - новое заключительное состояние.

При этом новая машина Тьюринга будет применима только к тем конфигурациям к которым применима исходная машина и результат обеих машин будет одинаковый.

Функции, вычислимые по Тьюрингу

 

Пусть имеется некий алфавит

– множество слов этого алфавита

Рассмотрим функцию отображающую множество слов алфавита на саму себя

f:

Пусть существует Машина Тьюринга:

1) Если определено и , то машина Т применима к начальной конфигурации и заключитальной конфигурацией является

2) Если не определена, то машина Т неприменима к начальной конфигурации

Такая машина вычисляет функцию и является функцией вычислимой по Тьюрингу.

 

Чтобы вычислить числовую функцию необходимо договориться о кодировке чисел. Т.е. о способе погружения объектов в заданную сигнатуру.

Простейшей кодировкой является унарная кодировка.

n ∈ N

n = Ι…Ι

n+1 = Ι…ΙΙ

n = Ι соответствует n=0

Рассмотрим машину Т вычисляющую функцию

Набор команд будет следующим

 

Для функций нескольких переменных в алфавит вводится символ разделитель «*»

Рассмотрим машину Т вычисляющую сумму двух переменных в унарной кодировке.

Пример вида ленты

Ι

Ι

*

Ι

Ι

Ι

Набор команд машины Т:

 

Свойства машин Тьюринга

1. Существование суперпозиции МТ. Пусть есть МТ вычисляющая функцию и МТ вычисляющая функцию , тогда существует МТ вычисляющая суперпозицию

Доказательство:

T_f1: А₁, Q₁=

T_f2: А₂, Q₂=

Тогда машину Т можно сконструировать следующим образом:

T_f: А= А₁ А₂, Q=

Конечное состояние первой машины и начальное состояние второй машины объединим в одно состояние.

Переобозначим символы: Q₂= .

Программы машины T_f будут составлены из программ машин и .

Рассмотрим, как будет работать машина T_f:

p

 

2. Машина «ИЛИ»:

f(ε,p) = , где ε – постоянная, которая может принимать значения 0 или 1.

Принцип работы:

, при

, ε*p

, при

Доказательство:

Построим такую МТ:

А= А₁ А₂ , Q= , где , .

МТ необходимо дополнить следующими командами:

0 λR и 1 λR

* λR * λR

Прием может быть применен для любых машин Тьюринга и , поэтому он считается универсальным.

 

3. Машина «И»

f(p)

Принцип работы:

= p *

Машина, которая после работы оставляет на ленте оба результата через разделитель.

Доказательство:

А = , где , А₁ А₂, = .

Тогда машина «И» должна будет проходить через следующие фазы:

Машина Тьюринга «И» - это суперпозиция машин , , и .

 

4. Машина Тьюринга, реализующая цикл:

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

 

Ф(р)=1

: Р Ф()=0

Ф(р)=0

Ф()=1 и т.д.

 

 

Блок-схема алгоритма:

Да

P

Ф(р)*р

Ф(р)=1

нет

Тезис Тьюринга

· Существуют машины, реализующие основные алгоритмические конструкции. Во всех алгоритмах другие конструкции можно представить через эти.

· Любой алгоритм всегда может быть реализован с помощью МТ (на данный момент не нашлось алгоритмической процедуры, которая не может быть реализована с помощью МТ).

Из этого следует тезис Тьюринга: любая вычислимая функция является вычислимой по Тьюрингу (В=Т)

Фактически этот тезис утверждает универсальность машин Тьюринга.