Теория алгоритмов. Машина Тьюринга

1.

Теория алгоритмов.
Машина Тьюринга.
Калининград, 2024

2.

Неразрешимые алгоритмические
проблемы
Алгоритмическая проблема — это проблема, в которой требуется найти
единый метод (алгоритм) для решения бесконечной серии однотипных
единичных задач. Такие проблемы называют также массовыми
проблемами. Они возникали и решались в различных областях математики
на протяжении всей ее истории.
Один из самых известных алгоритмов — алгоритм Евклида — был описан
на рубеже четвёртого и третьего веков до н.э. С тех пор человечество
разработало огромное количество алгоритмов, но вплоть до первой трети
XX века никто не задумывался о необходимости формального определения.

3.

Математики в начале XX в. столкнулись с тем, что
для некоторых массовых проблем не удается
подобрать общий алгоритм для их решения. В связи с
этим возникла необходимость дать точное
определение самому понятию алгоритма.
История теории алгоритмов берёт своё начало в 1900
году, когда крупнейший математик того времени
Давид Гильберт на математическом конгрессе в
Париже огласил список из 23 нерешённых
математических проблем. В некоторых проблемах
Гильберт просил найти «механическую процедуру»
отыскания решения задачи, то есть фактически он
просил найти алгоритм.
Давид Гилберт
1862 —1943
немецкий математик
- универсал

4.

Причины появления теории
• Внутренние потребности теоретической математики
(математическая логика, алгебра, геометрия и анализ).
• Создание быстродействующих электронных вычислительных и
управляющих машин.
• Связь с рядом областей лингвистики, экономики, физиологии
мозга и психологии, философии, естествознания.

5.

Алгоритмы: определение и
основные свойства
Слово “алгоритм” является производным от имени
среднеазиатского ученого Аль Хорезми, уроженца
Хивы, жившего в IX веке нашей эры.
Алгоритм – это точное предписание о выполнении в некотором
порядке системы операций, определяющих процесс перехода от
исходных данных к искомому результату для решения задачи
данного типа.
Это понятие относится к исходным математическим понятиям,
которые не могут быть определены через другие, более простые
понятия.

6.

Историческая справка
•создал математический анализ - дифференциальное и
интегральное исчисления;
•создал комбинаторику как науку;
•заложил основы математической логики;
•описал двоичную систему счисления с цифрами 0 и 1,
•в механике ввёл понятие «живой силы» (прообраз
современного понятия кинетической энергии) и
сформулировал закон сохранения энергии.
Готфрид Вильгельм
Лейбниц
1646 —1716
немецкий философ,
математик, физик

7.

Свойства и параметры
• Предписание считается
алгоритмом, если оно обладает
следующими свойствами:
• Каждый алгоритм, в общем
случае, должен задаваться
следующими параметрами:
определенностью, то есть
общепонятностью и точностью, не
оставляющими место произволу,
массовостью, то есть возможностью
исходить из меняющихся в известных
пределах значений исходных данных,
результативностью, то есть
направленностью на получение искомого
результата,
элементарностью шагов, на которые
разбивается последовательность
операций.
множеством допустимых исходных
данных,
начальным состоянием,
множеством допустимых
промежуточных состояний,
правилами перехода из одного
состояния в другое,
множеством конечных результатов,
конечным состоянием.

8.

Всеобщий алгоритм
задача точного определения понятия алгоритма
"А нельзя ли создать Всеобщий Алгоритм,
который решал бы любую математическую
задачу аксиоматической теории?"
Готфрид Вильгельм Лейбниц:
такой алгоритм будет найден!
1920е годы: две точки зрения
Все проблемы алгоритмически
разрешимы, но для некоторых
алгоритм еще не найден, поскольку
еще не развиты соответствующие
разделы математики.
Есть проблемы, для которых
алгоритм вообще не может
существовать.

9.

Алан Мэтисон Тьюринг
Дал определение вычислимой функции в
терминах воображаемой вычислительной машины
• Ввёл математическое понятие абстрактного
эквивалента алгоритма, или вычислимой функции,
получившее затем название «машины Тьюринга».
• Создал теорию «логических вычисляющих
машин».
• Проводил исследования в области искусственного
интеллекта.
Алан Мэтисон
Тьюринг
1912 —1954
Английский
математик, логик,
криптограф

10.

Эмиль Леон Пост
•один из основателей многозначной
логики (1921);
•предложил абстрактную вычислительную
машину - машину Поста.
Эмиль Леон Пост
1897 —1954
Американский
математик и логик

11.

Классические машины Тьюринга
Задача описания алгоритма может быть сведена к построению
машины некоторого типа, которая способна воспринимать набор
правил, выраженных на некотором языке, и делать то, что
предписано этими правилами.
А.М.Тьюринг, 1937 год
Машина Тьюринга – абстрактная (воображаемая) "вычислительная
машина" некоторого точно охарактеризованного типа, дающая
пригодное для целей математического рассмотрения уточнение
общего интуитивного представления об алгоритме.

12.

•В 1936 г. английский математик А. Тьюринг описал схему гипотетической
(абстрактной) машины и формализовал правила работы этой машины.
Машина Тьюринга (МТ) является абстракцией, которую нельзя реализовать
практически. Поэтому алгоритмы для МТ должны выполняться другими
средствами. Основным следствием формализации алгоритмов с
использованием МТ является возможность доказательства существования
или несуществования алгоритмов решения задач.
• Описывая различные алгоритмы для МТ и доказывая реализуемость
всевозможных композиций алгоритмов, Тьюринг показал разнообразие
возможностей предложенной им конструкции, что позволило ему выступить
с тезисом: «Всякий алгоритм может быть реализован соответствующей
машиной Тьюринга». Доказать тезис нельзя, так как в его формулировке не
определено понятие «всякий алгоритм». Его можно только обосновывать,
представляя различные алгоритмы в виде МТ.

13.

Тезис Тьюринга
Тезис Тьюринга – любой алгоритм можно преобразовать в
машину Тьюринга.
Эту гипотезу невозможно доказать, потому что она оперирует
неформальным понятием алгоритма.
Однако обоснование гипотезы есть: все алгоритмы, придуманные
в течение столетий, могут быть реализованы на машине Тьюринга.
Кроме того, эквивалентность всех формальных определений
алгоритма неслучайна и говорит в пользу гипотезы.
Чтобы опровергнуть основную гипотезу необходимо придумать
такой алгоритм, который невозможно было бы реализовать на
машине Тьюринга, но пока такого алгоритма нет.

14.

Принципы построения машины
• Каждый шаг алгоритма таков, что его может выполнить достаточно
простое устройство (машина).
• Желательно, чтобы это устройство было универсальным, т.е. чтобы
на нем можно было выполнять любой алгоритм.
• Механизм работы машины должен быть максимально простым по
логической структуре, но настолько точным, чтобы эта структура
могла служить предметом математического исследования.

15.

Машина Тьюринга
•Машина Тьюринга является расширением конечного автомата и,
согласно тезису Чёрча — Тьюринга, способна имитировать все
исполнители (с помощью задания правил перехода), каким-либо
образом реализующие процесс пошагового вычисления, в котором
каждый шаг вычисления достаточно элементарен.
•Автомат с конечным числом состояний и неограниченной
памятью, представленной набором одной или нескольких лент,
бесконечных в обоих направлениях
•Автомат с конечным числом состояний и неограниченной
памятью, представленной набором одной или нескольких лент,
бесконечных в обоих направлениях

16.

Реальные машины Тьюринга
Машина Тьюринга была построена в металле в 1973 в Малой
Крымской Академии Наук.
http://aturingmachine.com/index.php

17.

Неформальное определение
машины Тьюринга
Машина Тьюринга — это автомат, имеющий бесконечную в обе стороны
ленту, считывающую головку и управляющее устройство. Управляющее
устройство может находиться в одном из состояний, образующих
конечное множество Q={q0, q1,..., qn}- Множество Q называют
внутренним алфавитом машины Тьюринга. Среди состояний
управляющего устройства выделяются начальное состояние q0, из
которого автомат начинает свою работу, и заключительное состояние qz,
в котором автомат завершает работу.
Принципиальное отличие МТ от вычислительных машин состоит в том,
что её запоминающее устройство представляет собой бесконечную ленту.
Лента разделена на ячейки, в каждую из которых может быть записан
один символ из входного алфавита машины Тьюринга А={а0, а1 ..., аn,}.

18.

В алфавите А выделяют два символа специального назначения: а0 — символ
для обозначения пустой ячейки, a1 — символ, который используется для
разделения цепочек на ленте. Во время функционирования МТ заполнено
конечное число ячеек.
За один такт работы машина Тьюринга обозревает одну ячейку ленты. В
зависимости от символа в этой ячейке и состояния управляющего устройства
автомат записывает в ячейку новый символ или оставляет его без изменения,
может сдвинуть влево или вправо на одну ячейку считывающую головку или
оставляет ее на месте, а управляющее устройство может перейти в новое
состояние или остается в прежнем. Действия, которые выполняются
машиной Тьюринга за один такт, описываются одной командой, а
совокупность команд представляет собой функцию переходов автомата.

19.

Требования к машине Тьюринга
1. машина должна быть полностью детерминированной (вычисления
должны быть точные и общепонятные) и действовать в
соответствии с заданной системой правил.
2. должна допускать ввод различных “начальных данных”
(соответствующих различным задачам из данного класса задач).
3. заданная система правил работы машины и класс решаемых задач
должны быть согласованы так, чтобы всегда можно было
“прочитать” результат работы машины.
С помощью машины Тьюринга можно доказать существование
или не существование алгоритмов решения различных задач.

20.

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

21.

Формальное описание машины
Тьюринга
• Машиной Тьюринга называется упорядоченная семерка вида;
• Т = (Q, А, δ, р0, рz, а0, а1), где
• Q - конечное множество состояний управляющего устройства;
• А - входной алфавит;
• δ — функция переходов, или отображение δ: Q * А —> Q * А * S,
где S = {R, L, Е} - направления сдвига считывающей головки;
• р0 - начальное состояние, р0 ϵ Q; pz - заключительное состояние,
pz ϵ Q; а0 - символ для обозначения пустой ячейки, а0 ϵ А; а1 символ, который используется для разделения цепочек на ленте,
а1 ϵ А.

22.

Командой машины Тьюринга является элемент функции переходов,
которая, например, может иметь вид: qa—>pbR, где
q ϵ Q - состояние машины Тьюринга до выполнения команды,
р ϵ Q - состояние, в которое переходит машина Тьюринга после
выполнения команды,
а ϵ А - символ, читаемый автоматом со входной ленты
b ϵ A - символ, который может быть записан в ячейку в результате
выполнения команды
R ϵ S - сдвиг считывающей головки вправо на одну ячейку

23.

Спасибо за внимание!
Калининград, 2024