Машины Тьюринга. Конкретизация понятия алгоритма

Конкретизация понятия алгоритма

Свойства алгоритмов

Интуитивное понятие алгоритма

Тема 5. Теория алгоритмов

Для решения ряда однотипных задач можно использовать чисто механические вычислительные процессы. С их помощью искомые величины вычисляются последовательно из данных величин по определенным правилам. Описание таких процессов принято называть алгоритмами.

Алгоритм – это строгое предписание, определяющее вычислительный процесс как последовательность шагов, которая приводит от изменяемых начальных данных к конечному результату. Это фундаментальное и неопределяемое понятие.

2. Массовость: алгоритм должен решать не одну конкретную задачу, а целый класс подобных задач.

3. Элементарность шагов: алгоритм разбивается на этапы, каждый из которых должен быть простым и локальным.

4. Детерминированность: после выполнения очередного этапа однозначно определено, что делать дальше.

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

Примеры алгоритмов:

1. Нахождение наибольшего общего делителя.

2. Вычисление ранга целочисленной матрицы.

3. Построение ДНФ и КНФ в логике высказываний.

Интуитивное понятие алгоритма позволяет определить является ли данный процесс алгоритмом. Но существуют и алгоритмически неразрешимые задачи, т.е. задачи для которых построить алгоритм в принципе невозможно.

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

Но для того, чтобы доказать, что алгоритм не существует, надо точно знать, что такое алгоритм.

Начиная с 30-х годов XX века, было предложено несколько уточнений понятия алгоритма. К ним относятся:

· Рекурсивные функции.

· Машина Тьюринга.

· Нормальные алгорифмы Маркова.

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

Машина Тьюринга (МТ) – это математическая модель идеализированного вычисляемого устройства. Для построения МТ надо задать:

1. Конечный алфавит , где - пустой символ.

2. Конечное множество внутренних состояний .

МТ представляет собой

· Бесконечную ленту, разделенную на ячейки. В каждый момент времени в ячейке записана буква . В процессе работы в ячейку может быть записан другой символ

· По ячейкам передвигается управляющее устройство (УУ). В каждый момент времени оно находится напротив какой-то ячейки и имеет некоторое состояние .

Машина действует дискретно, т. е. в определенные моменты времени.

Если в какой-то момент времени УУ воспринимает ячейку, содержащую символ и МТ находится в состоянии , то МТ может совершить следующие действия:

1. Стереть символ и записать на его место символ .

2. Переместиться в ячейку слева (Л).

3. Переместиться в ячейку справа (П).

4. Остаться на месте (С).

Эти действия называются программой.

Таким образом, М=<A,Q, П>.

Программу МТ можно представить в виде последовательности команд вида: ,

где D={Л, П, С}. (Л- переход влево, П – переход вправо, С – остаться на месте).

Программу также можно представить в виде таблицы:

	q1	q2	….	qn
a1
a2
….
am

Пример. МТ добавляет к слову единицу.

Программа:

(Если в воспринимаемой ячейке символ , и МТ находится в состоянии q_1, то состояние не меняется, символ не меняется, УУ сдвигается вправо).

(Если в воспринимаемой ячейке символ 1, и МТ находится в состоянии q_1, то это значит, что УУ находится на начале слова, состояние меняется на q₂, символ не меняется, УУ сдвигается вправо).

(Если в воспринимаемой ячейке символ 1, и МТ находится в состоянии q_2, то это значит, что УУ передвигается по слову, состояние не меняется, символ не меняется, УУ сдвигается вправо).

(Если в воспринимаемой ячейке символ , и МТ находится в состоянии q_2, то это значит, что УУ дошло до конца слова, состояние меняется на заключительное, символ меняется на 1, УУ останавливается).

В виде таблицы эту программу можно записать следующим образом:

	q1	q2

Конфигурация МТ (машинное слово) – это слово вида , где

p₁ – слово в алфавите МТ (может быть пустое),

q_s – внутреннее состояние М,

a_i – воспринимаемый символ,

p₂ – слово в алфавите МТ.

МТ переводит конфигурацию в конфигурацию (), если имеет вид , имеет вид , - одна из команд МТ.

Для рассмотренного выше примера:

1. Команда переводит МТ из конфигурации в конфигурацию

2. Команда переводит МТ из конфигурации в конфигурацию

и т. д.

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

Тезис Тьюринга: Любой интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга.

Дата добавления: 2014-01-15