Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Лекция № 8. Тезисы теории алгоритмов




Теорема о неподвижной точке

 

Теорема 7.2.1. Пусть U – главная вычислимая универсальная функция для класса вычислимых функций одного аргумента, h(x) – произвольная всюду определенная вычислимая функция одного аргумента. Тогда существует такое число n, Un=Uh(n), то есть n и h(n) – номера одной функции.

Приведенная теорема называется теоремой Клини о неподвижной точке или теоремой о рекурсии.

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

Теорема 7.2.2. Пусть U(n, x) – главная вычислимая универсальная функция для класса всех вычислимых функций одного аргумента. Тогда существует такое число p, что U(p, x)=p для любого x.

Теорема 7.2.3. Если W – главное универсальное перечислимое множество, то всякая вычислимая всюду определенная функция h имеет неподвижную точку n, для которой Wn=Wh(n).

Определение 7.2.1. Два множества U1 и U2 вычислимо изоморфны, если существует биекция (вычислимая перестановка) f: N®N такая, что (x, yU1Û (f(x), f(y)U2.

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


Понятие алгоритма используется в математике давно, но до начала 1920 гг. оно встречалось примерно в таком контексте – для решения такой-то задачи необходимо совершить такие-то действия, чтобы получить искомый результат. В двадцатые годы прошлого столетия математики столкнулись с дачами, для которых они, как ни старались, не могли найти алгоритмы их решения. В математическом сообществе появилась идея, что таких алгоритмов вовсе не существует. Но тут же возникла другая проблема – отсутствие чего следует доказывать. Определение понятия «алгоритм», пригодное для решения многих разнообразных математических задач, в то время отсутствовало. В середине 30-х годов XX века и позднее были предприняты попытки формализации понятия алгоритма – определения универсальной формы записи информации и ограниченного, четко определенного набора элементарных действий по ее переработке, необходимых и достаточных для реализации любого содержательно описанного алгоритма.

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

«Тезис формализации. Любой содержательно описанный алгоритм может быть формализован в рамках используемых в теории алгоритмов строгих математических определений понятия алгоритма» [].

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

Это обстоятельство становится особенно ясным, если определить понятие интуитивно вычислимой функции примерно следующим образом:

«функция f(x) – интуитивно вычислима, если для вычисления ее значений существует алгоритм».

В этом контексте Тезис Черча-Клини о том, что класс интуитивно вычислимых функций» совпадает с классом «частично рекурсивных функций», есть ни что иное, как предположение о том, что:

– если мы хоть как-то можем вычислить некоторую функцию f(x), то она либо базисная, либо может быть построена из базисных функций конечным числом применения операторов суперпозиции функций, примитивной рекурсии и m-оператора (т.е. путем конечного применения ограниченного набора операций);

– если функция f(x) – не является частично-рекурсивной (а такие функции существуют), то она не является интуитивно вычислимой, а потому ее вычисление является алгоритмически неразрешимой проблемой.

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

Существуют и другие тезисы теории алгоритмов. Вот некоторые из них.

Тезис Тьюринга. Любой вербальный алгоритм в алфавите M может быть реализован некоторой машиной Тьюринга, работающей над алфавитом M.

Тезис Маркова – принцип нормализации. Любой вербальный алгоритм в алфавите M может быть реализован некоторым нормальным алгорифмом над алфавитом M.

О том, что эти два тезиса справедливы (или не справедливы) одновременно, гласит следующая теорема.

Теорема 8.1. Для любой машины Тьюринга (Т) в алфавите М существует нормальный алгорифм (N) над алфавитом М такой, что для всех aÎМ*, N(a)=Т (a). Для любого нормального алгорифма (N) в алфавите М существует машина Тьюринга (Т) над алфавитом М такая, что для всех aÎМ*, Т (a)=N(a).

Еще один тезис теории алгоритмов звучит так.

Тезис Черча-Тьюринга. Всякая интуитивно вычислимая функция является вычислимой по Тьюрингу.

Соответственно, справедлива следующая теорема.

Теорема 8.2. Функция f(x1, …, xn) частично рекурсивна тогда и только тогда, когда она вычислима по Тьюрингу.

Иными словами, рассмотренные подходы к формализации понятия алгоритм (в терминах рекурсивных функций, машины Тьюринга, алгорифмов Маркова), согласно приведенным теоремам, в принципе эквивалентны.

Более того, следует сказать, что в рамках теории алгоритмов были разработаны различные способы уточнения понятия «вычислимость» с использованием аппарата:

1) l- определимых функций (А.Черч, С.К.Клини, 1933–1936 гг.);

2) общерекурсивных функций (Ж.Эрбан, К.Гедель, С.К.Клини, 1934–1936 гг.);

3) m -рекурсивных и частично рекурсивных функций (К.Гедель, С.К.Клини, 1934–1936 гг.);

4) машин Тьюринга (А.Тьюринг, 1936 г.);

5) машины Поста (Э.Пост, 1943 г.);

6) нормальных алгорифмов Маркова (А.А.Марков, 1950);

7) МНР-вычислимых функций (Дж.Шепердсон, Х.Стерджис, 1963).

Однако, несмотря на значительные различия в подходах при описании вычислимости, каждое из перечисленных уточнений понятия «вычислимость» приводит к одному и тому же классу вычислимых функций. Заметим, что этот результат рассматривается в теории алгоритмов как серьезное подтверждение справедливости тезисов этой теории. С прагматической точки зрения данный результат означает ровно одно. Если функция не вычислима в соответствии с каким-то из указанных подходов, то она не может быть вычислена в рамках иной другой из указанных формализаций.

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

 

Раздел 2. Формальные языки и грамматики

 




Поделиться с друзьями:


Дата добавления: 2014-01-06; Просмотров: 547; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.015 сек.