сновные сведения из теории
1.1. Определение машины Тьюринга
Содержательно Машина Тьюринга (МТ) как абстрактный автомат, реализующий алгоритм вычисления некоторой вычислимой функции, состоит из трех компонентов:
1. Управляющее устройство (УУ), которое может находиться в одном из состояний, образующих конечное множество — внутренний алфавит машины Тьюринга;
2. Бесконечная лента, разбитая на ячейки, в каждой из которых может быть записан один из символов конечного алфавита — внешний алфавит машины Тьюринга;
3. Устройство обращения к ленте — считывающая и записывающая головка, которая в текущий момент времени считывает или записывает значение одной (текущей) ячейки ленты;
Рисунок 1 Схема машины Тьюринга
1.2. Принцип функционирования машины Тьюринга
В каждый дискретный момент времени (момент работы машины Тьюринга)
· Машина находится в одном из внутренних состояний;
· Головка обозревает одну из ячеек ленты.
При переходе к следующему такту выполняются следующие действия:
· Машина переходит в некоторое другое состояние (или остается в текущем состоянии).
· В обозреваемую ячейку записывается некоторый символ (или содержимое ячейки не изменяется).
· Головка передвигается на одну ячейку вправо(R), влево(L), или остается в том же положении (E).
Шаг машины представляет собой считывание символа из обозреваемой ячейки; определение состояния, в котором находится управляющее устройство и в зависимости от этого перевод управляющего устройства в новое состояние, запись на ленту нового символа и, перемещение головки вправо (R) или влево (L) или оставление головки на месте (E).
Формальная команда машины Тьюринга может быть задана в следующем виде:
(1)
где:
и
- состояние машины до и после выполнения команды
и
;
и
- обозреваемый символ в ячейке до и после выполнения
команды и
;
– символ, указывающий направление сдвига головки
.
Совокупность команд (программа) образует множество P;
Среди символов внутреннего алфавита машины Тьюринга Q можно выделить:
· — начальное состояние МТ,
· — конечное состояние МТ
Машина начинает функционировать, находясь в состоянии ; и заканчивает (останавливается) в состоянии
.
Среди символов внешнего алфавита машины Тьюринга выделяют символ – пустой символ,
. Запись символа
в ячейку ленты означает очистку этой ячейки.
Полным состоянием или конфигурацией машины Тьюринга называется такая совокупность символов из A и Q, которая однозначно определяет дальнейшее поведение машины.
Полное состояние (конфигурация) имеет следующий вид:
,
где:
— слово, находящееся на ленте слева от головки;
— текущее внутренне состояние
;
— слово, образованное символом, обозреваемым головкой и всеми символами справа от него.
Стандартной начальной конфигурацией называется конфигурация вида
,
т.е. конфигурацию, при которой головка обозревает крайний левый символ записанного на ленте слова a, а внутренними состоянием является .
Стандартной конечной конфигурацией называется конфигурация следующего вида:
,
где и
любые слова во внешнем алфавите А (в т.ч. и пустые). Внутренним состоянием является заключительное состояние
.
Машина Тьюринга – абстрактный автомат задаваемый кортежем следующего вида:
– внутренний алфавит;
– внешний алфавит;
– начальная конфигурация;
– совокупность команд машины.
1.3. Способы задания МТ
Задать вычислительный алгоритм в алгоритмической системе Тьюринга - это значит задать поведение МТ по любым внешним (входным) данным.
Поведение (или функционирование МТ) как и любой другой вычислительной машины (неабстрактной) может быть задано программой, составленной как минимум 3 различными способами:
1) Совокупностью команд МТ, прямым их перечислением;
2) Таблицей переходов МТ;
3) Блок-схемой или диаграммой переходов МТ.
Рассмотрим перечисленные способы на примере:
M = <Q, A, K0 , P>,
где
Q = { q0 , q1 , q2 , q z } ,
A = {a, b, c, },
K0 = q0 a b c .
1) Совокупность команд:
P = {q0 a q1 R ; q1 b q2 R ; q2 c q z E }
2) Таблица переходов:
3) Диаграмма переходов:
1.4. Вычисления на МТ
Рассмотрим, каким образом производятся вычисления на МТ.
В общем случае внешний алфавит (A) представляет собой
,
где
Aисх – алфавит, на котором могут быть записаны исходные слова на ленте перед началом работы МТ,
Aрез – множество символов (алфавит), на котором могут быть записаны все слова на ленте после остановки МТ,
Aпромеж – алфавит, символы которого могут появляться во время функционирования МТ.
Замечание: будем рассматривать простейший случай, когда все алфавиты совпадают.
В соответствии с определением стандартной начальной конфигурации (K0) ко всякой незаключительной конфигурации (Ki) применима некоторая команда МТ. После такого применения МТ переходит в новое полное состояние (или конфигурацию) Ki+1 . Этот переход принято обозначать
.
Если для некоторых Ki , Kj существует такая последовательность конфигураций
,
то это принято обозначать
.
Определение:
Дана f-функция, отображающая множество слов из алфавита во множество слов из
. Машина Тьюринга М вычисляет (правильно) функцию f, если:
1) f(V)=W и , для
– множество слов в алфавите
и
соответственно.
2) Существует V такое, что f(V) – не определено. Тогда и МТ, запущенная в стандартной начальной конфигурации q0 V, работает бесконечно долго или зацикливается.
Определение:
Если для f существует МТ М, которая ее вычисляет (правильно), то функция f называется (правильно) вычислимой по Тьюрингу.
Замечание: Две МТ, M1 и M2 , с одинаковыми алфавитами являются эквивалентными, если они правильно вычисляют одну и ту же функцию.
1.5. Примеры МТ
Построить МТ, которая бы умножала два натуральных числа.
Условимся обозначать натуральное число a словом, состоящим из такого количества единиц, количество которых равно численному значению a, а разделительный символ между числами будем обозначать «*».
Построить МТ для
1a * 1b 1a+b .
,
,
,
.
Решение:
P = { ,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
}.
1.6. Тезис Тьюринга
Для каждой ли вычислимой функции можно построить реализующий её на МТ алгоритм?
Ответом служит тезис Тьюринга: «Всякий алгоритм может быть реализован на МТ». Доказательства у этого утверждения нет, и не может быть, поскольку само понятие алгоритма является неточным.
Подтверждением тезиса Тьюринга могут служить следующие обстоятельства (неформальные):
- практика создания программ для МТ по всем вычислительным функциям;
- совокупность описания алгоритма в любой алгоритмической системе к МТ.
Этот тезис позволяет утверждать, что если невозможно создать МТ для вычисления какой-либо функции, то алгоритма вычисления этой функции не существует вообще!
В частности, это относится к:
· решению проблемы остановки для произвольной МТ
· проблеме определения выводимости в любой теории и т.д.
· проблеме существования М-транслятора: любой программы на алгоритмическом языке , которая определяет зацикливание
Проблема остановки для произвольной МТ:
- по некоторому алгоритму (?? А и Д ) определить, существует ли результат вычислений по алгоритму А?
- построить МТ М0 так, что любые М и любые и Д
T0(T,) = «Истина», если М – останавливается.
T0(T,) = «Ложь», если М - не останавливается.