Сновные сведения из теории

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, K₀ , P>,

где

Q = { q₀ , q₁ , q₂ , q _z } ,

A = {a, b, c, λ},

K₀ = q₀ a b c λ.

1) Совокупность команд:

P = {q₀ a → q₁ λ R ; q₁ b → q₂ λ R ; q₂ c → q _z λ E }

2) Таблица переходов:

3) Диаграмма переходов:

1.4. Вычисления на МТ

Рассмотрим, каким образом производятся вычисления на МТ.

В общем случае внешний алфавит (A) представляет собой

,

где

A_исх – алфавит, на котором могут быть записаны исходные слова на ленте перед началом работы МТ,

A_рез – множество символов (алфавит), на котором могут быть записаны все слова на ленте после остановки МТ,

A_промеж – алфавит, символы которого могут появляться во время функционирования МТ.

Замечание: будем рассматривать простейший случай, когда все алфавиты совпадают.

В соответствии с определением стандартной начальной конфигурации (K₀) ко всякой незаключительной конфигурации (K_i) применима некоторая команда МТ. После такого применения МТ переходит в новое полное состояние (или конфигурацию) K_i+1 . Этот переход принято обозначать

.

Если для некоторых K_i , K_j существует такая последовательность конфигураций

,

то это принято обозначать

.

Определение:

Дана f-функция, отображающая множество слов из алфавита во множество слов из . Машина Тьюринга М вычисляет (правильно) функцию f, если:

1) f(V)=W и , для – множество слов в алфавите и соответственно.

2) Существует V такое, что f(V) – не определено. Тогда и МТ, запущенная в стандартной начальной конфигурации q₀ V, работает бесконечно долго или зацикливается.

Определение:

Если для f существует МТ М, которая ее вычисляет (правильно), то функция f называется (правильно) вычислимой по Тьюрингу.

Замечание: Две МТ, M₁ и M₂ , с одинаковыми алфавитами являются эквивалентными, если они правильно вычисляют одну и ту же функцию.

1.5. Примеры МТ

Построить МТ, которая бы умножала два натуральных числа.

Условимся обозначать натуральное число a словом, состоящим из такого количества единиц, количество которых равно численному значению a, а разделительный символ между числами будем обозначать «*».

Построить МТ для

1^a * 1^b 1^a+b .

, , , .

Решение:

P = { , , , , , , , , , , , , , , , , }.

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

Для каждой ли вычислимой функции можно построить реализующий её на МТ алгоритм?

Ответом служит тезис Тьюринга: «Всякий алгоритм может быть реализован на МТ». Доказательства у этого утверждения нет, и не может быть, поскольку само понятие алгоритма является неточным.

Подтверждением тезиса Тьюринга могут служить следующие обстоятельства (неформальные):

- практика создания программ для МТ по всем вычислительным функциям;

- совокупность описания алгоритма в любой алгоритмической системе к МТ.

Этот тезис позволяет утверждать, что если невозможно создать МТ для вычисления какой-либо функции, то алгоритма вычисления этой функции не существует вообще!

В частности, это относится к:

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

· проблеме определения выводимости в любой теории и т.д.

· проблеме существования М-транслятора: любой программы на алгоритмическом языке , которая определяет зацикливание

Проблема остановки для произвольной МТ:

- по некоторому алгоритму (?? А и Д α ) определить, существует ли результат вычислений по алгоритму А?

- построить МТ М₀ так, что любые М и любые и Дα

T₀(T,α) = «Истина», если М – останавливается.

T₀(T,α) = «Ложь», если М - не останавливается.