Математическая логика. Шапорев С.Д (1019113), страница 33
Текст из файла (страница 33)
Все выволимыс формулы исчисления предикатов прсдставлмог собой южд»- огненно истинные высказывания. Обратно, кажлая тождественно истинная форьзула выводима в исчислении прсдикаюв. Из этого ясно, что в исчислении предикатов нельзя вывести сколько-нибудь содержательное по существу высказывание, в частности, математическое. Однако если к аксиомам исчисления предикатов присоединить какие-либо невыводимые формулы в качестве новых аксиом, то получится другое исчисление, в котором выводимы, помимо тождественно истинных формул, и другие формулы.
Средствами этого исчисления могут быль описаны различные математические дисциплины, например арифметика, теория чисел, геометрия, твари» множеств. Любви дедуктивна» сишвма может быть вырюкена указанными средствами. При этом любая выбранная система аксиом должна быть внутренне нспротиворечива и независима, т. с кюкдая из аксиом должна быть не выволима из остальных.
Глава о Теория алгоритмов $.1. Характерные черты алгоритма Понятие алгоритма в математике прошло большой путь развития. Общее определение алгоритма, имеющее ннгуитивиырг характер, следующее Ауггор хн — зго общий, единообразный„точно устаоовлснный способ решения лгсбой зазачи из данной массовой проблемы Таким образо», алггуритм всеглз связан с решением массовой проблемы. Задачи такого класса отличаются друг от друга значениями входящих в них параметров. Примеры аягоритмов извлечение квадратного корня, предальный переход, иахожпение производной и т. п Приведенное понятие алгоритма нсстрогос В нем встр»- чаюкя слова, точный смысл которых не установлен, налримср "способ" Тем ие менее даже при таком определении можно выделить некоторые хпракз срные черты шчгоритма' 1.
уунскретнасть Каждая последующая величина получается из значений предыдущих по определенному закону Все величины получаются последовательно друг за другом 2. Деягсрьгнггггрозпггносягь. Между всеми величинами, получаемыми алгоритмоч, существует жест ка» причинная связь Последующие значения за- висят от предыдущих 3. Э сггзгглгаругасягь широв шггортянп. бакан получения паследузощсй сис- темы величин из предшествующей должен быть прость и 4. Массозасщь. Начальная система величин выбирашс» из некоторого множе- ства Начальные условна могут варьировагьсз в бесконечных нредалах.
б. Рсзугьвюшнаяасягь. Конечный результат всегда должон быть получен Слава "шггаритм" происходит ат имени математика зль Хорезми бш Горсзми — шггоритм). Интуитивное понятие алгоритма рабатасг, когда речь идсг Лбу й 1мр Муз ымынб Му -Х р Г тау Ззаз — р б З Чесм 1. Ылгамюич яа яшина 21В о найденном алгоритме решения конкретной задачи. Положение существенно меняется, если возникает алгорнтьгическая проблема, решение которой не найдено, н требуетая установить, имеет лн она решение. В этом случае недо доказать либо существование влгоритыа, либо его отсуютвие, Первое могкно сделать путем фактического описана» пронесса, ренмюшсго задачу. В этом случае достаточно н интуитивною понятна алгоритма, чтобы удостовериться в том, чта описанный процесс есть алгоритм.
Доказать несуществование алгорнтма такич путем невозможно. Для этого необходимо точное формальное определение. В уточнении понятии алтари гма выделяются трн напрааленннг 1. Уточнение понятия эффективна вычислимой функции. Этим заннмьлнсь А. Черч и ЗС Гсдель. В результате был выделен ктасс частично рекурсивных функций, имеющих строгое математическое онрсделеннс. 2. Машинная арифметика.
Здесь сущность понятия алгоритма раскрывается путем рассьготрення процессов, осуществляемых в вычислительной машине 3. Направление, связанное а понятием нормальных азгорнтмов нз рабат А. Маркова*. Существование различных определений понятия алгоритма имеет н сваи преимущества, т. к. дл» решения различных задач удобно использовать различные наиболее подходящие для этого случая определения. Первое направление †. уточнение понятия алюрнтма — связано с точным описанием специального ю1асса функций, называеммх рекурсивными. Числовые функции, значения которых можно вычислить пОсредством алгоритма, называкнся енчиглиными 9 улкдняни. Понятие алгоритма здесь не определено формально точно, поэтому понятие вычнслимой функции оказывается интуитивным.
Однако совокупность вычналнмых функций, соотваютвующнх условняч 1 — 5, т.а. удовлетворяющих характерным чертам алгоритма для многих процессов, оказазааь одной и той жс, легко описываемой в математических юрминах. Эта точно описанная совокупность числовых функций. совпадающая с совокупностью всех вычислнмых функций в самом широком понимании алюрнтма, называется сгаакуллаагныа релургпаных функций. Рекурснвные функции впервые описаны ревелем, затем в 1936 г.
Черч нришсп к такому же кзассу функций Анализ идей, лежащих в основе определанна рекурсивных функций, позвОлил Черчу высказать пгпотезу о тоьг, гю «лвю рекуранвн1нх функций тождественен классу впаду определенных вы- Амг вхчлгывн м 9 а 11903-19791 — юеюг яи е щ. ггг Глава В. Т о ия ал оригмов числимык функций. Эта гипотеза изшютна под именем тезиса Чгрча; доказать ве нельзя, т. к. понятие вычислимой функции тоню не определено.
В силу тезиса Черча вопрос о вычислимасти функции равносмлем вопрооу о ев рекурсивности. Понятие рекурсивной функции строгое. Пгюкольку в влгоритмических пробяемвх речь обычно идат ме сб алгоритьгах, а о вычисли- мости некоторых специальным образом подобранных, решающих проблему функциях, то можно строго доказать, чта решающая конкретную залачу функция не может быть рекурсивной, а следовательно, не существует и алгоритма решения этой задачи. Именно этим пукм Черч доказал неразрешимость алгоритмической проблемы логики предиквтов.
Если первое направление уточняет понятие алгоритма через кяасс рекурсив. ных функций. то второ», связанное с машинной арифметикой, сначала уточняет понятие алгоритма, азатом определяет «ласс вычислнмых фумнций Это направление развито Постом и Тыорингом . Оановная идея этого направления заключается в том, что алгоритмические процессы — это процессы, которые могут иягитироваться иа подходяще пгютроеиных ьгашинак, «отары» описываются а точных матаматичсских терминах В результате оказывается, что сложные процессы можно моделировать на простых устройствах.
Всякий алгоритм может были задан некоторой фуикционт~ьной схемой и реализован в аостветствующей чашинс Тьюримга. Эта гипотеза называется тезисом Уяюрияго. Его также нельзя доказать по той же причин», что и тезис Черчв. Вас известные до аих пор алгоритмы могут быть заданы посредством гьюринговых функциантгьных схем. Третье направление — теория иориплыгыя авгартяягов угуоугя во.
Будем называть гмфавивюч А всякое непуатое конечное множество символов; аами символы называются буктьми. Словом в алфавите А называется всякая конечная послеловательноать букв этого алфавита. Проешйшнми действиями в норьшльных алгоритьгах Маркова являются поаледовательмы» замены вкождений подолов специального вида на другие сяавв. Нормальный алгоритм может переводить слово и в слово 55, причем на множестве слов испальзуеьюго алфавита слово ф одмоэмачно определяеюя этим алфавитом и словом и. Нормальный алгоритм может быть и не применим к слову и, если он не преобразует а ни в какое слово. Основное положение об вуниве5юальностив нармввьных алгоритмов — лрияммв яортцяизапии: любой атгоритм над «онечмыьг алфавитом А эквивалентен стноситечьно А некоторому нормальному алгоритму нвд А. Этот принцип подобен тезисам Черча и Тьюринга и недоказуем из-зв н»апреде- Ат Мяг святца» и [гз!2-!ззвз — а ~гя Ясвяв и в Чее;ъ Г уяг мег ческая поп к шв пенности формвльного понятия алгоритма.
На практике достаточно ограничигьш алгорить»ами, действующими на последовательностях натуральнык чисел и выдающих в качестве значений также последовательности натуральных чисел. Действии нормальных алгоритмов Маркова похожи на действия машин Тьюринга В последующих разделах более подробно изучим класс рекурсивных функций и процессы, происхолящие и машинах Тьюринга, Нормальные алгоршь»ы Маркова не будут рассматриватьсл. 6.2. Вычислимые, частично рекурсивные и общерекурсивные функции Пусть функции у зависит ог целочисяенных аргументов знх, т„.
Функция у = » (зй х„.. х) назь»вается эффекшиено еычислниай, если существует аягоритм, пазвоянощий вычислить ее значения. Простейшие эффективно вычислимые функции. ! В(т) = х ч ! оператор сдвига. 2 О(х)= 0 — оператор аннулирования. 3. 1„"'(щ,~,....х„) = х„„ ! < т < и .- оператор прсеьтироаания. Рассьютрим функции 1,(хпх„...,х„) У,(х„х„...,х„)...,1,„(х„х»,...,х„) и функцию ф(х»,х»,...,х„,) а функцию ф(х»,х»,...,хе ) определим равенством »у(х„х„...,х„)= »РЯ(хпх»,..,,х„)/~(хпх»,...,х„)..., 1„(х„х»,...,х„)) Яана, что функция »у(х,,х„...,х„) получена суперпозицией функций гр(х,,х»,...,х„,) и г»(хпх„...,х„) /»(хпх„...,х„)...,~„(хох„,х„) Очевидно, что если все функции 1„/»,..., 1„и гр вс»оду определены, то й» -- всюду определена. Функция Ч» будет не всюду опр«делена, если хати бы одна из функций,г„,у„...,1„, не всюду определена илн если 1», у„..., 1„, всюду определены, но ф(1п у»,...,1,„) гдето неопредеяена ит.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
