Алгоритм - способ выполнения арифметических действий над десятичными числами. Обозначение любой последовательности действий, приводящей к решению поставленной задачи. Узбекский математик Мухаммед бен Муса аль- Хорезми. Слово алгоритм европеизированное произношение слов аль-Хорезми.

XVII век – попытка построить общий алгоритм решения любых математических задач. Г.В. Лейбниц как раздел математики возникла в начале 30-х годов XX века. XX век - эта идея приобрела более конкретную форму: построить алгоритм проверки правильности любой теоремы при любой системе аксиом. Построить такие алгоритмы не удавалось, и математики выдвинули предположение: а вдруг для того или иного класса задач в принципе невозможно построить алгоритм решения?

Задача останова допускает несколько формулировок: 1) завершится ли выполнение программы, если отсутствуют данные? 2) завершится ли выполнение программы, когда в качестве входных данных выступают программы? 3) завершится ли выполнение программы для данных X?

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

10-я проблема Гильберта требуется выработать алгоритм, позволяющий для любого алгебраического уравнения P(x 1, x 2, …, x n ) = 0, где P многочлен с целыми коэффициентами, выяснить, имеет ли оно целочисленное решение. Ю.В. Матиясевич

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

III направление Отвлекается от конкретных машин (т.е. в этих моделях отсутствуют понятия память, состояние машины и т.п.). Наиболее известная алгоритмическая модель этого типа нормальные алгоритмы Маркова. II направление Определение алгоритмического процесса как процесса, осуществимого на конкретной теоретической машине (машина Тьюринга, машина Поста)

Все эти подходы привели к одному и тому же классу алгоритмически вычислимых функций. Указанные результаты составляют основу так называемой дескриптивной теории алгоритмов, основным содержанием которой является классификация задач по признаку алгоритмической разрешимости, т.е. получение высказываний типа Задача П алгоритмически разрешима или Задача П алгоритмически неразрешима

задачи, связанные с вычислением функций задачи, связанные с распознаванием принадлежности объекта заданному множеству (или ответом на вопрос: обладает ли объект заданным свойством?)

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

Каждый алгоритм А вычисляет значение функции F A при некоторых заданных значениях входных величин. Функции, вычисляемые некоторым алгоритмом, называются вычислимыми (алгоритмически вычислимыми) функциями.

общерекурсивная функция, - определимая функция (Черч: 1933 г., Клини: 1935 г.); вычислимая функция по Тьюрингу (Тьюринг: 1936 г., 1937 г.); представимая функция в формальной системе (Гедель: 1936 г.); комбинаторно определимая функция (Шейнфинкель, Карри, Россер: 1924–1936 гг.); каноническая система (Пост: 1943 г.); нормальный алгоритм (Марков: 1950 г.).

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

1. Как выдумаете, существует ли формальный исполнитель алгоритмов, который мог бы выполнить любой алгоритм? 2. Можно ли создать такое физическое устройство, которое могло бы выполнить любой алгоритм? 3. Приведите примеры формальных исполнителей и опишите их систему команд. 4. С какими формальными исполнителями вы знакомились на уроках информатики?

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

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

В каждой машине Тьюринга есть две части: 1) неограниченная в обе стороны лента, разделенная на ячейки; 2) автомат (головка для считывания/записи, управляемая программой).

С каждой машиной Тьюринга связаны два конечных алфавита: алфавит входных символов A = {a 0, a 1,..., a n }и алфавит состояний Q = {q 0, q 1,..., q m }. (С разными машинами Тьюринга могут быть связаны разные алфавиты A и Q.) Состояние q 0 называется начальным. Находясь в этом состоянии, машина начинает свою работу.

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

Каждая команда машины содержит не более одного действия. Фактически команды выглядят так: a i q j – в обозреваемую ячейку записать a i, сместиться вправо (к следующей ячейке) и перейти в состояние q j ; a i q j – в обозреваемую ячейку записать a i, сместиться влево (к следующей ячейке) и перейти в состояние q j ; a i S q j - в обозреваемую ячейку записать a i, остановиться и перейти в состояние q j.

Состояние машины Q Внешний алфавит А q0q0 …qjqj …qnqn a0a0 a1a1 … aiai a s q t … amam

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

Пример 1. На ленте записана последовательность из некоторого количества одного и того же символа «*». Составить функциональную схему, которая заставляет машину Тьюринга увеличивать на одну количество звездочек в этой последовательности. Решение приведено в таблице 2 Q A q0q0 a0a0 *S q 0 ** q 0

Ощутим себя в роли машины Тьюринга, изобразим в виде последовательности рисунков, как изменяется информация на ленте при работе машины Тьюринга, описанной функциональной схемой в табл. 2 Например, дана лента: **** Логический блок находится в состоянии q 0 и обозревает ячейку, в которой записан символ «*».

Согласно таблице, в эту ячейку записывается символ «*», блок смещается влево и переходит в состояние q 0. **** Теперь блок обозревает ячейку с символом «пробел». **** Согласно программе, в ячейку записывается символ «*» и машина прекращает свою работу. * В результате, количество символов увеличилось на один.

Пример 2. Работа машины Тьюринга описана следующей функциональной схемой: Q A q0q0 q1q1 q2q2 q3q3 q4q4 a0a0 * q 2 a 0 q 4 a 0 q 3 a 0 Sq 0 * * q 1 * q 0 * q 1 a 0 q 4 * q 4

Определите, какое сообщение будет на лентах а и б, и укажите, напротив какой ячейки в этот момент будет находиться ее пишущий блок. ***** а)а) б)б) ****

***** Изобразим в виде последовательности рисунков, как изменяется информация на ленте а при работе машины Тьюринга, описанной функциональной схемой в таблице примера 2. а) Решение Дано: 1 ) * q 1 ***** 2) * q 0 *****

****** 3) * q 2 4) * q 1 ****** 5) * q 0 ****** 6) * q 1 ******

7) a 0 q 4 ****** 8) * q 4 ****** 9) * q 4 ****** 10) * q 4 ****** 11) * q 4 ******

12) * q 4 ****** 13) a 0 Sq 0 ******

Для тестирования второго примера воспользуемся компьютерной реализацией машины Тьюринга. Программа называется Алго 2000 (создана Р.Зартдиновым).

********* б) Решение

Решение. Данная функциональная схема заменяет символ «*» на символ «#», находящийся слева от символа «#». Дано: **#***####* Получаем: *##**#####*

Решение. Данная функциональная схема заменяет символ «*» на символ «#». Дано: **#***####* Получаем: ###########

Решение Машина должна прибавить единицу к последней цифре числа. Если последняя цифра равна 9, то ее заменить на 0 и прибавить единицу к предыдущей цифре. Программа для данной машины Тьюринга может выглядеть так: QAQA q0q0 a0a0 1S q S q 0 23S q 0 34S q 0 45S q 0 56S q 0 67S q 0 78S q 0 89S q q 0

В этой машине Тьюринга q 0 состояние изменения цифры, S состояние останова. Если в состоянии q 0 автомат видит цифру 0..8, то он заменяет ее на 1..9 соответственно и машина останавливается. Если же он видит цифру 9, то заменяет ее на 0, сдвигается влево, оставаясь в состоянии q 0. Если же все цифры были равны 9, то он, сдвигаясь влево, заменит их нулями, запишет 0 на месте старшей цифры, сдвинется влево и в пустой клетке запишет 1. Затем остановится. QAQA q0q0 a0a0 1S q S q 0 23S q 0 34S q 0 45S q 0 56S q 0 67S q 0 78S q 0 89S q q 0

Приведите пример, когда формальный исполнитель имитирует другого формального исполнителя. Какого формального исполнителя называют универсальным? Что такое машина Тьюринга? Чем одна машина Тьюринга отличается от другой?

1. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Пишущий блок в состоянии q 0 обозревает некую цифру входного слова. (Указание. Сначала необходимо найти правый конец числа). 2. Подготовить доклад на тему «Машина Поста»