ICQ 357614154 Позвонить
8 903 995-9535

Здесь находится аттестат нашего WM идентификатора 335815356048
Проверить аттестат

Алгоритмы в математике

Ищите кому заказать высшую математику?  Присылайте своё задание на почту  v.fractus@yandex.ru стучите в icq 399737399 - договоримся. Мои реквизиты: wm R369090715159 Яндекс деньги 41001780003049 . После ознакомления с заданием я вышлю Вам свой ответ с указанием цены и срока выполнения работы. О способах оплаты читайте тут
 
 Несмотря на то, что длительное время интуитивного понятия алгоритма было вполне достаточно для задач математики и логики, возникает необходимость уточнения понятия  "алгоритма". Пусть имеется некоторая алгоритмическая проблема, то есть необходимо найти алгоритм для решения определенного класса задач. Если такой алгоритм найден, то предложенный способ решения задачи и признается всеми как алгоритм, исходя из их собственного интуитивного представления об алгоритме. Но в истории математики накопилось много случаев длительных и часто безрезультатных поисков тех или иных алгоритмов. При этом естественно возникало сомнение в существовании алгоритма.
 
 Так, например, в 1890г. на II Международном математическом конгрессе в Париже немецкий математик Давид Гильберт огласил список 23 трудных проблем, на важность решения которых он обращал внимание математической общественности. 10-я проблема Гильберта: требуется выработать алгоритм, позволяющий для любого Диофантова уравнения с целыми коэффициентами   выяснить, имеет ли оно целочисленное решение. Только в 1968г. Молодой математик Ю. Матиясевич доказал, что нет алгоритма, дающего решение поставленной задачи. Для доказательства не существования алгоритма необходимо его точное определение. Разработка точного определения алгоритма – одно из самых замечательных достижений в логике и математике. Оно получено в 30-х годах ХХ века в трудах Э.Поста, А.Тьюринга, А. А.. Маркова.
Когда алгоритма не существует, говорят, что рассматриваемая массовая проблема неразрешима. Ролью массовых проблем в математике и определяется как значение, так и сфера приложения понятия алгоритма.
 
 В подходах к определению алгоритма можно выделить три основных направления:
 
1. При решении алгоритмических проблем типичным является положение, когда надо найти алгоритм для вычисления значений числовой функции, зависящей от целочисленных значений аргументов. Числовые функции, значения которых можно вычислять посредством некоторого алгоритма, называются эффективно вычислимыми функциями. Это  понятие интуитивное, так как понятие алгоритма интуитивное. При различном понимании алгоритма должны получаться различные совокупности вычислимых функций. В 1936г. Чёрч точно описал совокупность так называемых рекурсивных функций, которая совпадает с совокупностью всех вычислимых функций при самом широком до сих пор известном понимании алгоритма. 
 
 Тезис Чёрча гласит: класс частично рекурсивных функций совпадает с классом эффективно вычислимых функций.
Это не теорема, а именно тезис, в нем предлагается отождествить несколько расплывчатое интуитивное понятие с понятием, сформулированным в точных математических терминах, и потому доказать его невозможно. Точное описание класса рекурсивных функций вместе с тезисом Чёрча является уточнением понятия алгоритма.
 
2. Связано с машинной математикой. Здесь сущность понятия алгоритма раскрывается путем рассмотрения процессов осуществляемых в машине. Это впервые было сделано Тьюрингом в 1937г. И Постом в 1936г. Они описали в точных математических терминах такие классы машин, что на этих машинах оказалось возможным осуществить все алгоритмические процессы, которые когда-либо встречались в математике.
 
3. Связано с понятием нормальных алгоритмов, введенных и разработанных российским математиком А.А. Марковым.
Как не странно, со временем выяснилось, что все эти подходы равносильны. Тем самым было получено подтверждение тезиса Чёрча.
Итак, первое направление формализации интуитивного понятия вычислимой функции, было предложено в 1935 г. А.Черчем и С.Клини. Класс рекурсивных функций строится следующим образом: выбираются некоторые первоначальные, в каком-то смысле простейшие, функции. Затем формулируются некоторые правила, на основе которых можно строить новые функции из уже имеющихся. Такие операции над функциями принято называть операторами. Тогда требуемым классом функций будет совокупность всех функций, которые получаются из простейших с помощью выбранных операторов. Для различных операторов получим различные классы функций. Несколько странная терминология в этой области сложилась, видимо, в результате переводов с английского. По-английски были ‘primitive recUrsive fUnctions’ (примитивно рекурсивные функции). Затем было дано более общее (general) понятие вычислимой всюду определенной функции, и такие функции были названы ‘general recUrsive fUnctions’. Затем стали рассматривать и частичные (partial) вычислимые функции, называя их ‘partial recUrsive fUnctions‘. В русском же языке слово ‘partial’ попало не туда, и вместо частичных рекурсивных функций  стали говорить о частично рекурсивных функциях. Та же участь постигла и слово ‘general’, которое странным образом вошло в прилагательное ‘общерекурсивная’ и означает, что функция всюду определена.
Определение примитивно рекурсивной функции было дано великим логиком Куртом Геделем и использовано как техническое средство при доказательстве теоремы Геделя о неполноте в начале 1930-х годов. Он же дал определение общерекурсивной функции. Американский логик Алонзо Черч высказал тезис: 
 
 Всякая вычислимая всюду определенная функция является общерекурсивной.
 
 Итак, тезис Черча утверждает, что интуитивно понимаемый класс вычислимых частичных функций совпадает с формально определенным классом частично рекурсивных функций. Это основная гипотеза теории вычислимых функций, ее можно высказать также в следующей форме; понятие частично рекурсивной функции является искомым уточнением, точным математическим аналогом понятия функции, вычислимой в интуитивном смысле. Затем американский математик Клини предложил распространить этот тезис на функции, не являющиеся всюду определенными.
 
 Тезис Черча, разумеется, не может быть доказан, поскольку содержит в своей формулировке такое расплывчатое понятие, как ‘вычислимая функция’. Какие же аргументы можно высказать в пользу этого тезиса. В чем заключается его обоснование. Основным аргументом является многовековой опыт человечества. Все функции  c которыми когда-либо приходилось иметь дело математикам и которые математики признавали вычислимыми (в интуитивном смысле), оказались частично рекурсивными. В этом отношении тезис Черча имеет такой же характер, как и другие естественнонаучные законы. Эта гипотеза является результатом большого человеческого опыта, итогом многих тысячелетних испытаний, проверок, экспериментов.
 
 Возьмите какую-нибудь интуитивно вычислимую функцию и попробуйте доказать ее частичную рекурсивность. Как говорит Владимир Андреевич Успенский в "Лекциях о вычислимых функциях" (1960), после достаточно большого числа подобных опытов-упражнений вы приобретете интуитивную уверенность в верности Основной гипотезы. А впрочем, если кто-то не согласится принять Основную гипотезу, - ничего страшного. Ему просто будет непонятно то внимание, которое уделяется понятию частично рекурсивной функции, для него теория частично рекурсивных функций будет всего лишь теорией некоторого конкретного подкласса всех интуитивно вычислимых функций.
 
 Второе направление, как мы уже говорили выше, условно можно назвать механистическим или машинным. Понятие машины Тьюринга возникает в результате прямой попытки разложить интуитивно известные нам вычислительные процедуры на элементарные шаги. В этом параграфе мы опишем этот довольно просто определяемый класс машин, на которых можно вычислить любую вычислимую функцию.
Обычно вопрос об алгоритмической неразрешимости какой-то задачи сводится к проблеме остановки машины Тьюринга, а последняя проблема (как будет доказано в этом параграфе) неразрешима.
 
 Тьюринг описал некоторого рода теоретически вычислительную машину, которая отличается от компьютера и от человека – вычислителя 2 чертами:
1) МТ не может ошибаться
2) МТ снабжена потенциально бесконечной памятью, т. е. в каждый момент количество накопленной информации конечно, но для этого количества нет верхней границы.
Термин "машина" был предложен профессором В.А. Успенским. Сами же Пост и Тьюринг не пользовались этим термином.
 
cup Вход на сайт

www.megastock.ru Univer2.Ru. Copyright © 2010. All rights reserved.