(34) Машины тьюринга (автор Алан Тьюринг) – 3-й способ определения вычислимых функций

Суть способа: лента с “0” и “1” поступает на вход «черного ящика» – ЭВМ. Черный ящик – ЭВМ – используется для входной ленты как пространство памяти ячеек для вычисления в виде инструкций для перехода из одного состояния в другое (модель конечного автомата).

Т.е., «машина Тьюринга» – функция перехода под действием входных данных из одного состояния в другое.

Один шаг действия может быть 3-х типов:

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

Определение 1: Машина Тьюринга – это функция такая, что для некоторого натурального числа область определения этой функции есть подмножество множества , а область значений есть подмножество множества

Например, пусть . То есть, когда машина дойдет до инструкции , а на обозреваемой ячейке написан символ 1, она его стирает, и оставляет 0. Ленту передвигает влево и переходит к инструкции . Если инструкция не определена, то, дойдя до инструкции , а на ячейке написан 1, то машина останавливается.

Входные данные и выходные данные – это строчки из 1, разделенные 0.

Пусть - строчка из 1 длины . Тогда строка, состоящая из строчек из 1, разделенными 0.

Определение 2: Пусть область определения местной функции . Функция называется «вычислимой», если существует машина Тьюринга такая, что как только начинает с инструкции , обозревая самый левый символ строки (вся остальная часть ленты пуста) тогда:

а) если значение функции определено, то в конце концов остановится, обозревая самый левый символ строки , при этом часть, находящаяся справа от этой строки, пустая;

б) если значение не определено, то никогда не останавливается.

ЗАМЕАНИЕ 1: Существует бесконечное число машин Тьюринга, для каждой из которых соответствует своя вычислимая функция.

ЗАМЕАНИЕ 2: Для любой вычислимой функции имеется бесконечное число машин Тьюринга.

ПРИМЕР: построим машину Тьюринга для « ». Зададим функцию :

; ; ; ;

; ; ; .

Например, ; обозреваемый символ выделен жирным шрифтом и почеркнут.

Номер инструкции	Текущая строка символов	Комментарий
0 0	0110110 0110110	Прохождение через первое слагаемое
0	0110110	Заполнение промежутка
1 1	0111110 0111110	Прохождение через второе слагаемое
1	0111110	Конец второго слагаемого
2	0111110	Стирание 1
3	0111100	Стирание второй 1
4 4 4	0111000 0111000 0111000	Движение назад
4 5	0111000 0111000	Остановка

(35) ДРУГИЕ ПОДХОДЫ К ОПРЕДЕЛЕНИЮ ПОНЯТИЯ АЛГОРИТМА. ТЕЗИС ЧЕРЧА

а) Гедель-Эбран-Клини: общерекурсивные функции, определенные с помощью исчисления «рекурсивных уравнений». Книга: Мендельсон. Введение в матем. Логику.- М.: Наука, 1976.-320 с.

б) Пост: Функции, определенные каноническими дедуктивными системами. Книга: Катленд Н. Вычислимость. Введение в теорию рекурсивных функций.-М.: Мир, 1983.-256 с.

в) Марков: Функции, задаваемыми «нормальными алгоритмами» над конечным алфавитом. Книга: Мендельсон. Введение в матем. Логику.- М.: Наука, 1976.-320 с.

г) Шепердсон-Стерджис: МНР-вычислимые функции (Катленд……..)

ТЕЗИС ЧЕРЧА: Интуитивно и неформально определенный класс эффективно вычислимых функций совпадает с классом определимых функций.

Вера в тезис подкрепляется аргументами:

1. многие независимые варианты уточнения интуитивного понятия вычислимости привели к одному и тому же классу;

2. обширное семейство эффективно вычислимых функций принадлежат этому классу;

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

(36)АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ (АНП)

Определение 1: Предикат называется «разрешимым», если его характеристическая функция, задаваемая формулой : , если – истинно; , если – ложно, вычислима.

Определение 2: Предикат называется «неразрешимым», если он не является разрешимым.

Алгоритмически Неразрешимые Проблемы:

1. Теорема Черча «о неразрешимости логики предикатов»: Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет.

2. Проблема остановки программы неразрешима: Не существует общего алгоритма проверки программ на наличие в них бесконечных циклов, т.е. на языке исчисления: «Не существует общего алгоритма узнать, имеет ли данное выражение «нормальную форму» или нет».

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

4. Диофантово полиномиальное уравнение имеет или не имеет целочисленного решения? Не существует общего алгоритма, который может установить конкретный ответ (Матиясевич доказал эту теорему).

(37) Определение: Однородный класс вычислительных задач будем называть «проблемой (массовой задачей)» и обозначать через Т, а алгоритм, ее решающий, через А. Частный случай Т обозначим через . А выполняет последовательность вычислений . Длина характеризует время вычислений. Глубина - число уровней параллельных шагов – время параллельных вычислений.

1) сложность вычислений «в наихудшем случае», где мера вычисления может быть выбрана как: а) число элементов или б) глубина или в) число модулей (уровень технологии); – размер.

2) сложность «поведения в среднем», где - вероятность появления I среди возможных частных случаев .

3) Анализ алгоритмов связан с вопросом «для заданной функции размера и меры вычисления точно определить для данного алгоритма А, решающего проблему Т, либо сложность «для наихудшего случая», либо, при подходящих предположениях, «поведение в среднем» . (Кнут «Искусство программирования»).

4) Сложность задачи – сложность наилучшего алгоритма, известного для ее решения (нижняя оценка сложности алгоритма).

Определение: Будем говорить, что функция есть , если существует константа с такая, что для всех натуральных n.

Основной вопрос теории сложности: с какой стоимостью может быть решена заданная проблема?

(38) а) линейные ; б) быстрее их - ; в) полиномиальные алгоритмы принадлежат к классу , для которых временная сложность порядка , где целое;

г) экспоненциальные – для них не существует оценки .

Определение: Задача «труднорешаема», если для нее не существует «полиномиального» алгоритма.

Замечание: для малых «экспоненциальный» алгоритм может быть быстрее полиномиального.

Класс Р:

1) найти эйлеров цикл на графе из ребер: алгоритм проверки циклов - ; 2) задача Прима-Краскала: городов в плоской стране. Общая длина телефонных линий соединения городов минимальна. Жадный алгоритм находит «остовное» дерево за .

3) Быстрое преобразование Фурье (БПФ) за шагов; 4) Умножение целых чисел по алгоритму Шенхаге-Штрассена (Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.: Мир, 1979.-536 с.) за шагов по сравнению с умножением двух разрядных чисел по традиционному алгоритму .

5) Умножение матриц - .

КЛАСС Е:

1. построить множество всех подмножеств; 2) все полные подграфы графа или все поддеревья графа.

ЗАДАЧИ, не принадлежащие к классу Р и не принадлежащие к классу Е :

1. задача «коммивояжера»; 2) задача «составления расписаний при определенных условиях»; 3) задача «оптимальной загрузки емкости (рюкзака, вагонов поезда, самолета и т.д.); 4) задача «распознавания простого числа» и другие.

Определение: Детерминированный алгоритм – алгоритм, в котором переход из одного состояния в другое однозначный. Недетерминированный имеет несколько вариантов перехода (вероятностный переход).

(39) NP-трудные и NP-полные задачи

Определениe: Задача Q полиномиально сводится к задаче R тогда и только тогда, когда выполнены условия:

1. Существуют функции и , вычисляемые за полиномиальное время ;

2. Для любого входа и для любого частного случая задачи Q значение - вход частного случая задачи R;

3. Для любого решения (выхода) задачи R значение - решение задачи Q:

Определение: Если одновременно задача Q полиномиально сводится к задаче R и задача R полиномиально сводится к задаче Q, то задачи Q и R полиномиально эквивалентны.

Определение: Задача является NP-трудной (или NP-сложной), если каждая задача из класса NP полиномиально сводится к ней. Задача является NP-полной, если она входит в класс NP и является NP-трудной.

Другими словами, задача Т является NP-трудной, если она по крайней мере так сложна, как любая задача в NP.

NP-полные задачи – это самые трудные из NP.

Любая NP-полная задача Т принадлежит NP\Р. Точнее, задача Т принадлежит к классу Р тогда и только тогда, когда Р=NP.

Теорема Кука (задача о выполнимости является NP-полной): F – формула из теории L (ИВ – исчисление высказываний) представлена в КНФ. Существует ли такое распределение истинностных значений высказывательных переменных, при которых формула F выполнима?

Доказательство: Обозначим задачу распределения истинностных значений высказывательных переменных, при которых формула F выполнима, через задачу Т. Задача о выполнимости Т полиномиально сводится к любой NP-трудной задаче, принадлежащей к классу NP, то есть она является NP-полной.

К настоящему времени установлена NP-полнота большого числа задач. Выше были перечислены некоторые задачи, которые не попадают ни в класс Р, ни в класс Е. Все они являются NP-полными.

Проблема состоит в следующем: можем ли мы надеяться, что какая-либо из этих задач имеет полиномиальную сложность?

По-видимому, ответ будет неудовлетворительным. Очень важным аргументом для такого вывода служит тот факт, что все задачи эквивалентны по сложности – стоит нам найти какой-то полиномиальный алгоритм для одной из этих задач, то все эти задачи становятся полиномиально сложны.