2.Определение машины Тьюринга

Алгоритм является точным математическим понятием. В качестве формальной модели алгоритма исторически первой была модель машины, предложенная англичанином Аланом Тьюрингом в 40-х годах 20-го века. Машина Тьюринга представляет собой устройство, содержащее пишущую ленту бесконечной длины. В каждой ячейке может быть записан один и только один символ из входного алфавита машины Тьюринга. Как правило, для простейших задач рассматривают внешний алфавит, состоящий из трех символов: 0, 1, .  - пустой символ, обозначающий, что содержится в ячейке не 0, не 1. «Слово» - последовательность непустых символов, ограниченная слева и справа символом . В начальный момент на ленту записывается какое-то слово. Обычно это слово представляет собой описание некоторой задачи, на которых специализируется данная машина Тьюринга. Кроме ленты, у машины имеется читающая-пишущая головка, которая позволяется считать символ из ячейки или записать в ячейку, непосредственно находящуюся под головкой, какой-то один символ. Машина Тьюринга работает по тактам. Такты машины Тьюринга никак не привязываются к единицам времени, например, секундам. Но! именно в тактах измеряется “время”, затрачиваемое машиной Тьюринга на то, чтобы выполнить обработку входного слова. Разумно и сложность задачи связывать с числом тактов, которую необходимо затратить на Машине Тьюринга для ее решения. Машина Тьюринга работает по определенным правилам. По сути также правила однотипны и сводятся к следующему: 1) считывает символ в текущей ячейки; 2) по текущему состоянию МТ считывает символы. Определить новое состояние, которое перейдет МТ; 3) записать в ячейку новый символ или оставить предыдущий; 4) сдвинуть ленту на одну ячейку вправо или влево, или остаться в этом же положении и перейти к шагу 1.

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

Такие правила удобнее всего представлять в виде таблицы.

3.Тезис Черча-Тьюринга.

Те́зис Чёрча — Тью́ринга — фундаментальное эвристическое утверждение, существенное для многих областей науки, в том числе, для математической логики, теории доказательств, информатики, кибернетики, дающее интуитивное понятие о вычислимости. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.

В терминах теории рекурсии, это утверждение формулируется как совпадение классов вычислимых и частично рекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча.

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

Тезис Чёрча — Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает эквивалентность между строго формализованным понятием частично вычислимой функции и неформальным понятием вычислимости.

Позднее были сформулированы другие практические варианты утверждения:

-физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга;

-сильный тезис Чёрча — Тьюринга (тезис Чёрча — Тьюринга — Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.

Машина Маркова.

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

Суть этих самых алгоритмов Маркова в следующем. Задача для алгоритмов Маркова ставится в виде: найти алгоритм (написать программу) переводящую любую строку S (заданную на некотором алфавите (т.е. наборе символов, которые могут в нее входить)) из некоторого допустимого множества входных строк в строку f(S). Т.е., построить программу - преобразователь строк, выполняющую некое преобразование. Программа на языке алгоритмов Маркова - представляет из себя набор правил. Каждое правило представляет собой замену.

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

Определение всякого нормального алгорифма состоит из двух частей: определения алфавита алгорифма (к словам из символов которого алгорифм будет применяться) и определения его схемы. Схемой нормального алгорифма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида L\to D, где L и D — два произвольных слова в алфавите алгорифма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки называются слова вида L\to\cdot D, где L и D — два произвольных слова в алфавите алгорифма. При этом предполагается, что вспомогательные буквы \to и \to\cdot не принадлежат алфавиту алгорифма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы). Любой нормальный алгорифм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгорифму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгорифмам, принято называть «принципом нормализации».

Нормальные алгорифмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгорифма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.