Основ. положения об алгоритмах
2 Теория алгоритмов
2.1 Основные требования к алгоритмам.
Каждый алгоритм работает с данными: входными, промежуточными, выходными.
При этом, объекты должны быть четко определены и отличны как друг от друга, так и от ?необъектов?. Например, к алгоритмическим объектам относятся числа, векторы, матрица смежности графа, формулы. Дело даже не в том, что рисунок графа менее ясно представляет граф, чем матрица, а в том, что матрицу можно разбить на элементы (0 и 1). Не является алгоритмическими объектами ? ?хорошая книга?, ?осмысленное утверждение?.
Набор элементарных объектов образуют конечный алфавит исходных символов ( букв, цифр и т.д.) из которых строятся другие объекты. Средством построения являются индуктивные определения, указывающие, как строить новые объекты из уже построенных. Например: идентификатор - это буква, либо идентификатор, к которому приписана справа буква или цифра. Слова конечной длины в конечных алфавитах (в частности числа) ? наиболее обычный тип алгоритмических данных, а число символов в слове (длина слова) ? единица измерения объема обрабатываемой информации. Более сложный случай ? формулы. Здесь основным алгоритмам предшествуют вспомогательные, которые проверяют, удовлетворяют ли исходные данные нужным требованиям (синтаксический анализ).
Перечислим основные требования к алгоритмам.
1. Данные для размещения требуют памяти. Память обычно считается однородной и дискретной, т.е. состоит из одинаковых ячеек, каждая ячейка может содержать один символ алфавита. При этом память может быть бесконечной.
2. Алгоритм состоит из отдельных элементарных шагов (действий), причем количество их конечно. Например, множество элементарных действий ? система команд ЭВМ. Обычно элементарный шаг имеет дело с фиксированным числом символов, однако это требование не всегда выполняется. Например: динамическая память, используемая в программировании.
3. Последовательность шагов детерминирована, т.е. после каждого шага указывается, что делать дальше.
4. Результативность или сходимость алгоритма, т.е. остановка после конечного числа шагов.
5. Следует различать:
а) описание алгоритма (инструкция, программа)
б) механизм реализации (ЭВМ)
в) процесс реализации (последовательность шагов, которая будет порождена при применении алгоритма к конкретным данным).
6. Массовость алгоритма ? служит для решения не какой-либо конкретной задачи, а целого класса задач. Например: формулы для решения системы двух уравнений определяют решение при любом значении коэффициента, арифметические правила применимы к любым числам и т.д.
Процедуру для решения индивидуальной задачи не называют алгоритмом. Например: xn+yn=zn ? не известен алгоритм, позволяющий определить для n= 1,2,3,4,.. решение. Но для конкретных n существует решение. Например: n=2, x=3, y=4, z=5.
Ниже рассматриваемые алгоритмические модели можно считать формализацией понятия ?алгоритм?, то есть, они универсальны ? допускают описание любых алгоритмов. При этом будет показано, что каждая модель сводится к другой.
Выделяют три основных типа универсальных алгоритмических моделей, различающихся исходными эвристическими соображениями о том, что такое алгоритм.
? Рекурсивные функции. Модель основана на функциональном подходе и рассматривает понятие алгоритма с точки зрения того, что можно вычислить с помощью алгоритма. Исторически это первая формализация алгоритма, которая связывает определение алгоритма с вычислениями и числовыми функциями.
? Машина Тьюринга. Алгоритм представляется как детерминированное устройство, выполняющее примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Эвристика этой модели близка к ЭВМ
? Канонические системы Поста, нормальный алгоритм Маркова ? преобразование слов в произвольных алфавитах, в которых элементарной операцией являются подстановки, т.е. замены подслова ? другим словом. Другими словами, в этих моделях формализован процесс преобразования записей исходных данных в запись результатов. Преимуществами можно считать: максимальную абстрактность и возможность применить понятие алгоритма к объектам произвольной природы (не обязательно числовой).
Пример
1) Алгоритм Евклида ( НОД двух заданных целых положительных чисел a и b).
1. Обозревай данные числа a и b. Переходи к следующему указанию.
2. Сравни обозреваемые числа (a=b или a<b или a>b). Переходи к следующему указанию.
3. Если обозреваемые числа равны, то каждое дает искомый результат. Процесс вычисления остановить. Если нет, переходи к следующему указанию.
4. Если первое обозреваемое число меньше второго, то переставь их местами. Переходи к следующему указанию.
5. Вычитай второе число из первого и обозревай остаток. Переходи к указанию 2.
Элементарные шаги в алгоритме Евклида ? арифметические действия (вычитание, сравнение). Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям называются численными алгоритмами.
Блок-схемы алгоритмов
Связи между шагами можно изобразить в виде графа. Например для алгоритма Евклида это:
нет
да
Вершины ? шаги, ребра ? переходы между шагами. Вершины, из которых выходит одно ребро ? оператор, вершины, из которых выходит два ребра ? логическое условие или предикат. Важная особенность блок-схемы ? каждый шаг может не быть элементарным ?значит можно алгоритм ?разблочивать? (разбивать на отдельные задания, и раздавать для программирования разным лицам). Необходимо программисту блока знать: где лежит информация, форму ее представления, что должен делать блок, куда записать результат.
Можно также из нескольких алгоритмов, рассматриваемых как блоки, связать один большой алгоритм. Например: A1?вычисляет f1(x), A2 - вычисляет f2(x), блок-схема, представляющая композицию A1 и A2 представлена на рисунке
2.2 Машины Тьюринга
Машина Тьюринга состоит из
? управляющего устройства, которое может находиться в одном из состояний, образующих множество Q={q1, ?, qn}
? ленты, разбитой на ячейки, в каждой из которых может быть записан символ из конечного алфавита A={a1,?, am}
? устройства обращения к ленте ? считывающей или пишущей головки, которая в любой момент времени обозревает ячейку ленты и в зависимости от символа в ячейке и состояния управляющего устройства записывает в ячейку символ ( может быть совпадающий с прежним или пустой (т.е. стирает)), сдвигается на ячейку влево или вправо или остается на месте. При этом управляющее устройство переходит в новое состояние ( или остается в старом ).
Среди состояний управляющего устройства выделены начальное q1 и конечное qz(q0) ( z,0 ? не числовые переменные, а знак конца).
Таким образом память машины Тьюринга ? это внутренняя память (множество состояний) и внешняя память (лента).
Лента бесконечна в обе стороны, но в начальный момент времени только конкретное число ячеек заполнено непустыми символами, остальные пустые, т.е. содержат λ (пустой символ обозначает пробел).
Данные машины Тьюринга ? слова, как исходные, так и окончательные результаты.
Элементарные шаги ? считывание, запись символов, сдвиг головки, переход управляющего устройства в следующее состояние.
Детерминированность машины Тьюринга (последовательность шагов) определяется таким образом: для каждого внутреннего состояния qi и символа aj однозначно заданы:
а) следующее состояние qi′ ,
б) символ aj′, который нужно записать вместо aj в ту же ячейку,
в) направление сдвига головки ? dk :( L ? влево, R ? вправо, E (с) ? на месте)
Следовательно, Машина Тьюринга может описываться системой правил (команд), имеющих вид:
1) qiaj → qi′ aj′ dk (1)
2) aj
qi qi′ aj′ dk
3)
qi aj → aj′ dk qi′
Однозначно требуется, чтобы для любого j и любого i ≠z в системе команд имелась одна команда аналогичная (1) (с левой частью qiaj ); qz в левой части не встречается.
Полное состояние машины Тьюринга (внутреннее состояние + состояние ленты + положение головки ) называется конфигурацией или машинным словом и обозначается α1qiα2, где qi - текущее внутреннее состояние, α1 ? слово слева от головки, α2 ? слово = (символ обозревателя головки + символы справа от него ), причем слева от α1 и справа от α2 нет непустых символов. Например, конфигурация с внутренним состоянием qi , в котором на ленте записано abcde и головка обозревает d запишется abcqide.
Стандартная начальная конфигурация q1α (головка обозревает крайний левый символ слова на ленте). Стандартная заключительная конфигурация qzα.
Пример:
Алфавит А={1, λ}, состояния { q1 , qz },
Команды q1 1 q11R, q1λ q1 1 R
Для любой начальной конфигурации такая Машина Тьюринга работает бесконечно, заполняя 1 ленту вправо.
Если α1 q1 α2 => β 1 qz β2 , то машина Тьюринга Т перерабатывает слово α1 α2 в β 1 β2 , обозначим это Т(α1 α2) = β 1 β2 .
Исходными данными машины Тьюринга будем считать слова, записанные на ленте и векторы из таких слов.
Запись на ленте словарного вектора правильная, если она имеет вид α1 λ α2 λ ? αk-1 λ αk (λ Аисх), либо α1*α2 * ? αk-1 * αk (*-символ?разделитель, * Аисх).
Обозначим Арез ? алфавит результатов (совокупность слов, разделенных пробелами). Может быть что Аисх= Араз, также выделим Апр ? промежуточный алфавит, который может быть ≠ Аисх и Арез (в частности это разделитель). Таким образом алфавит ленты А=Аисх U Апр U Арез. В простейшем случае Аисх = Арез, А = АисхU{λ}
Пусть f ? функция, отображающая множество векторов над Аисх в множество векторов над Арез . f: Vисх → Wрез
Машина Тьюринга правильно вычисляет функцию f, если
1)Для любого V? Vисх и W ? Wрез , таких, что f(V)=W, следует q1V* qz W* (V*, W* - правильные записи V и W)
2)Для любого V, такого что f (V) ? не определена, машина Т, с начальной конфигурацией q1V* работает бесконечно.
Если для f существует машина Тьюринга, которая правильно ее вычисляет, то f называется правильно вычислимой по Тьюрингу.
Две машины Тьюринга с одним алфавитом Аисх эквивалентны , если они вычисляют одну и туже функцию.
Далее будем рассматривать числовые функции, т.е. f : N →N. Натуральные числа будем представлять в единичном (унарном) коде, т.е. Аисх = {1} либо Аисх = {1, *}, число x представляется словом 1?1=1x. Таким образом, числовая функция f(x1,?,xn) правильно вычислима по Тьюрингу, если существует машина Тьюринга q11x1 * 1x2 * ?* 1xn qz1y, когда f(x1,?,xn) = y и Т работает бесконечно, начиная с q11x1 *?1xn, когда f(x1,?,xn) не определена.
Пример (Сложение, машина Т+)
Сложить a и b означает следующее: слово 1a*1b переработать в 1a+b , т.е. удалить разделитель * и сдвинуть, например первое слагаемое, ко второму.
Обозначим машину Тьюринга - Т+, введем 4 состояния (q1,?,q4) и систему команд.
q11→ q2λR
q21→ q21R
q2*→ q31L
q31→ q31L
q3λ→ q4λR
Диаграмма переходов
1→R 1→ L
1→ λ R * →1 L λ→ λ R
Пример (Копирование машина Ткоп)
Переработка слова α → α * α; α = 1α
Система команд приведена в таблице
1 λ * 0
q1
q2
q3
q4 q20R
q21R
q31R
q41L qzλR
q3*R
q41R q1* L
q3*R
q4*L q11L
q10R
Диаграмма переходов
0 →1L 1→ R 1→ R *, 1→L
1 3 4
*→L 1→0R *, λ→ *R λ→ 1L
8 6
0→ R
λ→R 10
Ткоп при каждом проходе исходного числа 1α заменяет левую из его единиц 0 (q1) и пишет ( в состояние q3 ) одну единицу справа от 1α в ближайшую пустую клетку (q3 ). При первом проходе, кроме того ( состояние q2 ) ставится маркер. Таким образом копия 1α строится за α проходов. После записи очередной 1 машина переходит в состояние q4 , которое передвигает головку влево от ближайшего нуля, после чего машина переходит в состояние q1 и цикл повторяется. Он прерывается когда q1 обнаруживает на ленте не 1, а маркер. Это значит, что все 1 в 1α исчерпаны, т.е. сделано α проходов. Тогда головка возвращается влево в исходное положение, заменяя по дороге все 0 единицами.
Некоторые операции над машинами Тьюринга
Напомним, что композицией 2-х функций f1(x) и f2(g) называется g(x)=f2(f1(x)) .
Теорема
Если f1(x) и f2(x) вычислимы по Тьюрингу, то f2(f1(x)) также вычислима по Тьюрингу.
Пример
Рассмотрим машину, вычисляющую f(x) = 2x(x≠0). Ее можно представить как композицию Т+ (Ткоп). Ткоп строит двухкомпонентный вектор, Т+ вычисляет функцию от 2-х переменных (складывает их).
Диаграмма переходов
0 →1L 1→ R 1→ R *, 1→L
*→L 1→0R *, λ→ *R λ→ 1L Ткоп
0→ R
λ→ q21R
1→R 1→ L
1→ λ R * →1 L λ→ λ R
Т+
* →λ R
Пример (предикат):
Машина с нижеприведенной диаграммой вычисляет предикат ?α ? четное число?
λ→И
1→ λ L
1→R λ→ L
λ→Л
1→R 1→R 1→ λ L
λ→ L λ→И
Считывающая головка достигает конца числа α в состоянии q2, если число единиц четно; в состоянии q3, если число единиц нечетно. После чего она перемещается в исходное положение в состояние q4 или q5 (в каждом из них есть петля) и печатает И или Л. Чтобы предикат вычислялся с восстановлением, достаточно чтобы в петлях заменить 1→ λ L на 1→ L .
Машина Тьюринга Т++ - для сложения n чисел ( n=1,2,?)
1→ 1R 1→ 1R 1→1L
1→ λR *→ 1R λ→ λ L λ→ λ R
*→ λ R
*→*L
λ→ λ R
1→1L
q41→ q41 R ? проход 2-го (очередного) слагаемого
q4λ→ q5 λ L - проверка на 3-е (следующее ) слагаемое
Цикл из состояний q1, q2 , q3 ? ?зацикленная? Т+ , в которой заключены состояния совмещенные с начальной суммой, полученной на очередном цикле ? 1-е слагаемое следующего цикла. q4 ? разветвление. В нем проверяется условие, есть ли 2-е слагаемое, если да (* присутствует), то переход к новому циклу, если нет (λ после единиц), то машина выходит из цикла.
Заключение
1) Для вычислений на машине Тьюринга достаточно, чтобы лента была бесконечна в одну сторону, например вправо. Такая лента называется полулентой.
Теорема
Любая функция, вычислимая по Тьюрингу, вычислима на машине Тьюринга с правой полулентой.
Другими словами, для любой машины Тьюринга существует эквивалентная ей машина Тьюринга с правой полулентой. Аналогичная теорема формулируется для левой полуленты.
Такую эквивалентную машину можно построить например так: каждый раз, когда головке прежней машины нужно зайти за левый край ленты, новая машина предварительно сдвинет все написанное вместе с головкой на клетку вправо.
2)Тезис Тьюринга
Любой алгоритм может быть реализован машиной Тьюринга.
Тезис Тьюринга не является теоремой, это гипотеза, как например гипотезы об адекватности математических моделей физическим явлениям.
Подтверждением тезиса Тьюринга является математическая практика, а также то, что описание алгоритмов в терминах другой известной алгоритмической модели может быть сведено к его описанию в виде машины Тьюринга.
2.1 Основные требования к алгоритмам.
Каждый алгоритм работает с данными: входными, промежуточными, выходными.
При этом, объекты должны быть четко определены и отличны как друг от друга, так и от ?необъектов?. Например, к алгоритмическим объектам относятся числа, векторы, матрица смежности графа, формулы. Дело даже не в том, что рисунок графа менее ясно представляет граф, чем матрица, а в том, что матрицу можно разбить на элементы (0 и 1). Не является алгоритмическими объектами ? ?хорошая книга?, ?осмысленное утверждение?.
Набор элементарных объектов образуют конечный алфавит исходных символов ( букв, цифр и т.д.) из которых строятся другие объекты. Средством построения являются индуктивные определения, указывающие, как строить новые объекты из уже построенных. Например: идентификатор - это буква, либо идентификатор, к которому приписана справа буква или цифра. Слова конечной длины в конечных алфавитах (в частности числа) ? наиболее обычный тип алгоритмических данных, а число символов в слове (длина слова) ? единица измерения объема обрабатываемой информации. Более сложный случай ? формулы. Здесь основным алгоритмам предшествуют вспомогательные, которые проверяют, удовлетворяют ли исходные данные нужным требованиям (синтаксический анализ).
Перечислим основные требования к алгоритмам.
1. Данные для размещения требуют памяти. Память обычно считается однородной и дискретной, т.е. состоит из одинаковых ячеек, каждая ячейка может содержать один символ алфавита. При этом память может быть бесконечной.
2. Алгоритм состоит из отдельных элементарных шагов (действий), причем количество их конечно. Например, множество элементарных действий ? система команд ЭВМ. Обычно элементарный шаг имеет дело с фиксированным числом символов, однако это требование не всегда выполняется. Например: динамическая память, используемая в программировании.
3. Последовательность шагов детерминирована, т.е. после каждого шага указывается, что делать дальше.
4. Результативность или сходимость алгоритма, т.е. остановка после конечного числа шагов.
5. Следует различать:
а) описание алгоритма (инструкция, программа)
б) механизм реализации (ЭВМ)
в) процесс реализации (последовательность шагов, которая будет порождена при применении алгоритма к конкретным данным).
6. Массовость алгоритма ? служит для решения не какой-либо конкретной задачи, а целого класса задач. Например: формулы для решения системы двух уравнений определяют решение при любом значении коэффициента, арифметические правила применимы к любым числам и т.д.
Процедуру для решения индивидуальной задачи не называют алгоритмом. Например: xn+yn=zn ? не известен алгоритм, позволяющий определить для n= 1,2,3,4,.. решение. Но для конкретных n существует решение. Например: n=2, x=3, y=4, z=5.
Ниже рассматриваемые алгоритмические модели можно считать формализацией понятия ?алгоритм?, то есть, они универсальны ? допускают описание любых алгоритмов. При этом будет показано, что каждая модель сводится к другой.
Выделяют три основных типа универсальных алгоритмических моделей, различающихся исходными эвристическими соображениями о том, что такое алгоритм.
? Рекурсивные функции. Модель основана на функциональном подходе и рассматривает понятие алгоритма с точки зрения того, что можно вычислить с помощью алгоритма. Исторически это первая формализация алгоритма, которая связывает определение алгоритма с вычислениями и числовыми функциями.
? Машина Тьюринга. Алгоритм представляется как детерминированное устройство, выполняющее примитивные операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Эвристика этой модели близка к ЭВМ
? Канонические системы Поста, нормальный алгоритм Маркова ? преобразование слов в произвольных алфавитах, в которых элементарной операцией являются подстановки, т.е. замены подслова ? другим словом. Другими словами, в этих моделях формализован процесс преобразования записей исходных данных в запись результатов. Преимуществами можно считать: максимальную абстрактность и возможность применить понятие алгоритма к объектам произвольной природы (не обязательно числовой).
Пример
1) Алгоритм Евклида ( НОД двух заданных целых положительных чисел a и b).
1. Обозревай данные числа a и b. Переходи к следующему указанию.
2. Сравни обозреваемые числа (a=b или a<b или a>b). Переходи к следующему указанию.
3. Если обозреваемые числа равны, то каждое дает искомый результат. Процесс вычисления остановить. Если нет, переходи к следующему указанию.
4. Если первое обозреваемое число меньше второго, то переставь их местами. Переходи к следующему указанию.
5. Вычитай второе число из первого и обозревай остаток. Переходи к указанию 2.
Элементарные шаги в алгоритме Евклида ? арифметические действия (вычитание, сравнение). Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям называются численными алгоритмами.
Блок-схемы алгоритмов
Связи между шагами можно изобразить в виде графа. Например для алгоритма Евклида это:
нет
да
Вершины ? шаги, ребра ? переходы между шагами. Вершины, из которых выходит одно ребро ? оператор, вершины, из которых выходит два ребра ? логическое условие или предикат. Важная особенность блок-схемы ? каждый шаг может не быть элементарным ?значит можно алгоритм ?разблочивать? (разбивать на отдельные задания, и раздавать для программирования разным лицам). Необходимо программисту блока знать: где лежит информация, форму ее представления, что должен делать блок, куда записать результат.
Можно также из нескольких алгоритмов, рассматриваемых как блоки, связать один большой алгоритм. Например: A1?вычисляет f1(x), A2 - вычисляет f2(x), блок-схема, представляющая композицию A1 и A2 представлена на рисунке
2.2 Машины Тьюринга
Машина Тьюринга состоит из
? управляющего устройства, которое может находиться в одном из состояний, образующих множество Q={q1, ?, qn}
? ленты, разбитой на ячейки, в каждой из которых может быть записан символ из конечного алфавита A={a1,?, am}
? устройства обращения к ленте ? считывающей или пишущей головки, которая в любой момент времени обозревает ячейку ленты и в зависимости от символа в ячейке и состояния управляющего устройства записывает в ячейку символ ( может быть совпадающий с прежним или пустой (т.е. стирает)), сдвигается на ячейку влево или вправо или остается на месте. При этом управляющее устройство переходит в новое состояние ( или остается в старом ).
Среди состояний управляющего устройства выделены начальное q1 и конечное qz(q0) ( z,0 ? не числовые переменные, а знак конца).
Таким образом память машины Тьюринга ? это внутренняя память (множество состояний) и внешняя память (лента).
Лента бесконечна в обе стороны, но в начальный момент времени только конкретное число ячеек заполнено непустыми символами, остальные пустые, т.е. содержат λ (пустой символ обозначает пробел).
Данные машины Тьюринга ? слова, как исходные, так и окончательные результаты.
Элементарные шаги ? считывание, запись символов, сдвиг головки, переход управляющего устройства в следующее состояние.
Детерминированность машины Тьюринга (последовательность шагов) определяется таким образом: для каждого внутреннего состояния qi и символа aj однозначно заданы:
а) следующее состояние qi′ ,
б) символ aj′, который нужно записать вместо aj в ту же ячейку,
в) направление сдвига головки ? dk :( L ? влево, R ? вправо, E (с) ? на месте)
Следовательно, Машина Тьюринга может описываться системой правил (команд), имеющих вид:
1) qiaj → qi′ aj′ dk (1)
2) aj
qi qi′ aj′ dk
3)
qi aj → aj′ dk qi′
Однозначно требуется, чтобы для любого j и любого i ≠z в системе команд имелась одна команда аналогичная (1) (с левой частью qiaj ); qz в левой части не встречается.
Полное состояние машины Тьюринга (внутреннее состояние + состояние ленты + положение головки ) называется конфигурацией или машинным словом и обозначается α1qiα2, где qi - текущее внутреннее состояние, α1 ? слово слева от головки, α2 ? слово = (символ обозревателя головки + символы справа от него ), причем слева от α1 и справа от α2 нет непустых символов. Например, конфигурация с внутренним состоянием qi , в котором на ленте записано abcde и головка обозревает d запишется abcqide.
Стандартная начальная конфигурация q1α (головка обозревает крайний левый символ слова на ленте). Стандартная заключительная конфигурация qzα.
Пример:
Алфавит А={1, λ}, состояния { q1 , qz },
Команды q1 1 q11R, q1λ q1 1 R
Для любой начальной конфигурации такая Машина Тьюринга работает бесконечно, заполняя 1 ленту вправо.
Если α1 q1 α2 => β 1 qz β2 , то машина Тьюринга Т перерабатывает слово α1 α2 в β 1 β2 , обозначим это Т(α1 α2) = β 1 β2 .
Исходными данными машины Тьюринга будем считать слова, записанные на ленте и векторы из таких слов.
Запись на ленте словарного вектора правильная, если она имеет вид α1 λ α2 λ ? αk-1 λ αk (λ Аисх), либо α1*α2 * ? αk-1 * αk (*-символ?разделитель, * Аисх).
Обозначим Арез ? алфавит результатов (совокупность слов, разделенных пробелами). Может быть что Аисх= Араз, также выделим Апр ? промежуточный алфавит, который может быть ≠ Аисх и Арез (в частности это разделитель). Таким образом алфавит ленты А=Аисх U Апр U Арез. В простейшем случае Аисх = Арез, А = АисхU{λ}
Пусть f ? функция, отображающая множество векторов над Аисх в множество векторов над Арез . f: Vисх → Wрез
Машина Тьюринга правильно вычисляет функцию f, если
1)Для любого V? Vисх и W ? Wрез , таких, что f(V)=W, следует q1V* qz W* (V*, W* - правильные записи V и W)
2)Для любого V, такого что f (V) ? не определена, машина Т, с начальной конфигурацией q1V* работает бесконечно.
Если для f существует машина Тьюринга, которая правильно ее вычисляет, то f называется правильно вычислимой по Тьюрингу.
Две машины Тьюринга с одним алфавитом Аисх эквивалентны , если они вычисляют одну и туже функцию.
Далее будем рассматривать числовые функции, т.е. f : N →N. Натуральные числа будем представлять в единичном (унарном) коде, т.е. Аисх = {1} либо Аисх = {1, *}, число x представляется словом 1?1=1x. Таким образом, числовая функция f(x1,?,xn) правильно вычислима по Тьюрингу, если существует машина Тьюринга q11x1 * 1x2 * ?* 1xn qz1y, когда f(x1,?,xn) = y и Т работает бесконечно, начиная с q11x1 *?1xn, когда f(x1,?,xn) не определена.
Пример (Сложение, машина Т+)
Сложить a и b означает следующее: слово 1a*1b переработать в 1a+b , т.е. удалить разделитель * и сдвинуть, например первое слагаемое, ко второму.
Обозначим машину Тьюринга - Т+, введем 4 состояния (q1,?,q4) и систему команд.
q11→ q2λR
q21→ q21R
q2*→ q31L
q31→ q31L
q3λ→ q4λR
Диаграмма переходов
1→R 1→ L
1→ λ R * →1 L λ→ λ R
Пример (Копирование машина Ткоп)
Переработка слова α → α * α; α = 1α
Система команд приведена в таблице
1 λ * 0
q1
q2
q3
q4 q20R
q21R
q31R
q41L qzλR
q3*R
q41R q1* L
q3*R
q4*L q11L
q10R
Диаграмма переходов
0 →1L 1→ R 1→ R *, 1→L
1 3 4
*→L 1→0R *, λ→ *R λ→ 1L
8 6
0→ R
λ→R 10
Ткоп при каждом проходе исходного числа 1α заменяет левую из его единиц 0 (q1) и пишет ( в состояние q3 ) одну единицу справа от 1α в ближайшую пустую клетку (q3 ). При первом проходе, кроме того ( состояние q2 ) ставится маркер. Таким образом копия 1α строится за α проходов. После записи очередной 1 машина переходит в состояние q4 , которое передвигает головку влево от ближайшего нуля, после чего машина переходит в состояние q1 и цикл повторяется. Он прерывается когда q1 обнаруживает на ленте не 1, а маркер. Это значит, что все 1 в 1α исчерпаны, т.е. сделано α проходов. Тогда головка возвращается влево в исходное положение, заменяя по дороге все 0 единицами.
Некоторые операции над машинами Тьюринга
Напомним, что композицией 2-х функций f1(x) и f2(g) называется g(x)=f2(f1(x)) .
Теорема
Если f1(x) и f2(x) вычислимы по Тьюрингу, то f2(f1(x)) также вычислима по Тьюрингу.
Пример
Рассмотрим машину, вычисляющую f(x) = 2x(x≠0). Ее можно представить как композицию Т+ (Ткоп). Ткоп строит двухкомпонентный вектор, Т+ вычисляет функцию от 2-х переменных (складывает их).
Диаграмма переходов
0 →1L 1→ R 1→ R *, 1→L
*→L 1→0R *, λ→ *R λ→ 1L Ткоп
0→ R
λ→ q21R
1→R 1→ L
1→ λ R * →1 L λ→ λ R
Т+
* →λ R
Пример (предикат):
Машина с нижеприведенной диаграммой вычисляет предикат ?α ? четное число?
λ→И
1→ λ L
1→R λ→ L
λ→Л
1→R 1→R 1→ λ L
λ→ L λ→И
Считывающая головка достигает конца числа α в состоянии q2, если число единиц четно; в состоянии q3, если число единиц нечетно. После чего она перемещается в исходное положение в состояние q4 или q5 (в каждом из них есть петля) и печатает И или Л. Чтобы предикат вычислялся с восстановлением, достаточно чтобы в петлях заменить 1→ λ L на 1→ L .
Машина Тьюринга Т++ - для сложения n чисел ( n=1,2,?)
1→ 1R 1→ 1R 1→1L
1→ λR *→ 1R λ→ λ L λ→ λ R
*→ λ R
*→*L
λ→ λ R
1→1L
q41→ q41 R ? проход 2-го (очередного) слагаемого
q4λ→ q5 λ L - проверка на 3-е (следующее ) слагаемое
Цикл из состояний q1, q2 , q3 ? ?зацикленная? Т+ , в которой заключены состояния совмещенные с начальной суммой, полученной на очередном цикле ? 1-е слагаемое следующего цикла. q4 ? разветвление. В нем проверяется условие, есть ли 2-е слагаемое, если да (* присутствует), то переход к новому циклу, если нет (λ после единиц), то машина выходит из цикла.
Заключение
1) Для вычислений на машине Тьюринга достаточно, чтобы лента была бесконечна в одну сторону, например вправо. Такая лента называется полулентой.
Теорема
Любая функция, вычислимая по Тьюрингу, вычислима на машине Тьюринга с правой полулентой.
Другими словами, для любой машины Тьюринга существует эквивалентная ей машина Тьюринга с правой полулентой. Аналогичная теорема формулируется для левой полуленты.
Такую эквивалентную машину можно построить например так: каждый раз, когда головке прежней машины нужно зайти за левый край ленты, новая машина предварительно сдвинет все написанное вместе с головкой на клетку вправо.
2)Тезис Тьюринга
Любой алгоритм может быть реализован машиной Тьюринга.
Тезис Тьюринга не является теоремой, это гипотеза, как например гипотезы об адекватности математических моделей физическим явлениям.
Подтверждением тезиса Тьюринга является математическая практика, а также то, что описание алгоритмов в терминах другой известной алгоритмической модели может быть сведено к его описанию в виде машины Тьюринга.