Вычислимость по Тьюрингу.

С помощью машины Тьюринга формализуется интуитивное понятие вычислимости (а тем самым и интуитивное понятие алгоритма).

Пусть даны два алфавита А и В, такие, что А∩B≠{Ø}. Рассмотрим подмножество LÍ(A*)ⁿ, т.е. совокупности из n слов в алфавите А

(A*)ⁿ = {(w₁, w₂, …, w_n | w_i Î A*}, где А* - множество слов над алфавитом А.

n-местной частичной функцией из (А*)ⁿ (совокупности n слов над алфавитом А) в В* называется правило:

f(w₁, w₂, …, w_n) = w Î В*

т.е. совокупности n слов (w₁, w₂, …, w_n) Î (A*)ⁿ ставится в соответствие слово w Î В*, где А∩B≠{Ø}.

Область определения функции f: Def(f) = LÍ(A*)ⁿ, т.е. совокупности n слов над алфавитом А.

Область значений функции f: Im(f) = {wÎ B*| если существует совокупность из n слов (w₁, w₂, …, w_n) Î (A*)ⁿ, w = f(w₁, w₂, …, w_n) }.

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

Пусть МТ Т имеет рабочий алфавит А U В. будем говорить, что МТ Т определяет n-местную частичную функцию f_T, отображающую (A*)ⁿ в В*, если выполняются следующие условия:

1. Совокупность n слов (w₁, w₂, …, w_n) Î Def(f_Т) тогда и только тогда, когда имеет место отношение <bw₁bw₂b…bw_n(b)b>Þ*<bjbw(b)yb> (т.е. МТ Т начав работу в начальной ситуации S₀ за конечное число шагов остановится в ситуации S) S₀ Þ* S, где слово j, y Î (А È В È {b})* - расширение рабочего алфавита МТ Т. w Î B*, при этом слово w является значением функции f_Т, т.е. w = f_T(w₁, w₂, …, w_n)

2. Совокупность n слов (w₁, w₂, …, w_n)ÏDef(f_T), если: МТ неприменима к начальным данным, либо w Ï B*, либо в рабочей ячейке в результате останова МТ содержится не буква b, либо рабочая ячейка не следует за словом w.

Частичная функция f:(A*)ⁿ®B* (задающая отображение) называется вычислимой по Тьюрингу (ВТ-функцией), если существует Мт Т с рабочим алфавитом А È В, такая что n-местная частичная функция f_Т:(A*)ⁿ®B*, определяемая этой МТ, совпадает с f (т.е. f_T=f). О любой такой МТ говорят, что она вычисляет функцию f.

Если МТ Т' моделирует МТ Т, то эти машины вычисляют одну и туже функцию f.

Практическая вычислимость - это вычислимость, которая реализуется с помощью физического автомата и является значительно более узким понятием, чем вычислимость по Тьюрингу.

Функция f:(A*)ⁿ®B* называется нормированно вычислимой по Тьюрингу (НВТ-функцией), если существует МТ Т, которая вычисляет f и при этом удовлетворяет следующим требованиям:

1. Если совокупность из n слов (w₁, w₂, …, w_n)ÏDef(f),, то МТ начав работу с ситуации <bw₁bw₂b…bw_n(b)b> никогда не остановится.

2. Если (w₁, w₂, …, w_n) Î Def(f), то справедливо отношение <bw₁bw₂b…bw_n(b)b>Þ*<bw₁bw₂b…bw_n(b)wb>, где w=f_T(w₁…w_n)

Смысл нормированного вычисления состоит в том, что при таком вычислении часть ленты, расположенная левее символа b, непосредственно предшествующего слову w₁, не меняется и не влияет на работу МТ Т. при нормированном вычислении головка не должна заходить левее указанного символа b.

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

Пример 1 (вычислимой функции). Моделирование работы Машины Поста.

Функция f(x, y) = x + y, определённая на множестве пар неотрицательных целых чисел, является "вычислимой в интуитивном смысле"; покажем что она вычислима и в смысле Тьюринга. Для этого построим МТ М с алфавитом {b, ½} такую, что x + y = f_T(x, y).

Подобная машина должна, имея на ленте коды и ( ½, ½½½½½), разделённые пустой ячейкой, получать из этой записи x + y палочек (не обязательно подряд). Заметим, что x + y = < >+ < > - 2

Легко убедиться, что следующая машина выполняет поставленную задачу:

q₁|βq₂ стирается первая палочка первого кода

q₂βЛq₃

q₃|βq₄ стирается вторая палочка первого кода

q₃ββq₃

q₄βЛq₅ лента сдвигается до тех пор, пока

q₅|Лq₅ головка не дойдёт до несобственного символа

q₅β|q₆ заменяем несобственный символ палочкой

q₄|βq₄ останов

Здесь машина останавливается, поскольку ситуации q₄β нет ни в одной команде. В этот момент на ленте ровно x + y палочек.

Пример 2 (пример частично вычислимой функции).

Функция g(x, y) = x - y определена лишь для тех пар, у которых x ≥ y, покажем, что она частично вычислима по Тьюрингу. Для этого мы построим машину Тьюринга М, выполняющую вычитание. Пусть на ленте имеются коды и , разделённые пустой ячейкой; слева, справа. Машина будет работать последовательными циклами; каждый цикл состоит в стирании одной (самой левой) палочки в и одной (самой правой) палочки .

q₁|βq₁ стирается самая левая палочка в ,

q₁βЛq₂ лента сдвигается на одну ячейку влево,

q₂|Лq₂ лента сдвигается влево, пока головка не дойдёт до конца кода ,

q₁βЛq₃ головка переходит через пробел, разделяющий и ,

q₃|Лq₃ лента сдвигается влево, пока головка не дойдёт до конца кода ,

q₃βПq₄ шаг назад на первый символ ,

q₄|βq₄ стираем обозреваемый символ,

q₄βПq₅ делаем шаг вправо,

q₅|Пq₆ проверяем, если обозреваем палочку, то продолжаем вычисления, иначе машина останавливается, так как отсутствует команда q₅β,

q₆|Пq₆ сдвигаемся вправо, пока не встретим начало кода ,

q₆βПq₇ переходим через пробел, разделяющий и ,

q₇|Пq₈ если в осталось хоть одна палочка, вычисления продолжаются,

q₇βПq₇ если в не осталось ни одной палочки (случай ), машина будет работать вечно, сдвигая ленту вправо,

q₈|Пq₈ лента сдвигается до начала кода ,

q₈βЛq₁ головка устанавливается так, что обозревается самая левая палочка "остатка" кода ; машина переходит в начальное состояние, тем самым оказывается готовой начать очередной цикл.

Пример 3 (нормированные вычисления).

Построить МТ М, делающую нормированные вычисления <bw(b)b>Þ*<bwbw₁(b)b>, где w, w₁ , A={1, 0}, w₁=w+1, т.е. должны быть сохранены исходные данные.

Для этого необходимо вначале скопировать исходные данные, а затем осуществлять прибавление 1, т.е. вначале необходимо построить копировальную машину <bw(b)b>Þ*<bwbw(b)b>, а затем строить МТ <bw bw(b)b>Þ*<bwbw₁(b)b>, делающую нормированные вычисления и прибавляющую 1 к любому второму числу за конечное число тактов.