Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Сходимость, сложность, надежность

Правильность программ

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

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

Для сложных программ удачное тестирование не дает гарантии того, что программа не содержит ошибок.

С интуитивной точки зрения программа будет правильной, если в результате ее выполнения достигается тот результат, для получения которого и была написана программа. Факт безаварийного завершения программы еще ни о чем не говорит: возможно, что программа делает совсем не то, что было задумано и для чего она была написана. Предположим, что программа не содержит синтаксических ошибок, и обратим внимание на содержание. Доказательство правильности программы состоит в предъявлении такой цепочки аргументов, которые убедительно свидетельствуют о том, что программа действительно решает поставленную задачу.

Пусть – программа, P – утверждение, относящееся ко входным данным, которое должно быть истинно перед выполнением программы, и Q – утверждение, которое должно быть истинно после выполнения программы. P – называется предусловием, а Qпостусловием программы. Полезно различать два вида правильности: частичную и тотальную. Программа называется частично правильной по отношению к P и Q, если, всякий раз, когда предусловие истинно перед выполнением и заканчивает работу, постусловие также будет истинно. Программа называется тотально правильной по отношению к P и Q, если она частично правильна по отношению к P и Q и обязательно завершает свою работу, если P истинно. Понятие правильности программы сформулировано относительно соответствующих утверждений P и Q, и из частичной или тотальной правильности программы при данных пред- и постусловиях не обязательно следует истинность утверждения о правильности при других пред- и постусловиях.

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

Более строгий путь проверки программы – верификация, которая представляет собой теоретическое обоснование правильного вычисления программы и включает логико-математическое доказательство того, что вычислительное поведение программы правильно.

Эффективность алгоритмов

Для обоснованного использования времени и памяти вычислительной машины необходим теоретический и эмпирический анализ эффективности.

На практике приходится довольствоваться приближенным решением задачи и мириться с элементами неопределенности в решении. Как правило, точно решаются только задачи с конечным числом входных и выходных данных, допускающих конечное представление. Можно выделить две причины, по которым ограничиваются приближенным решением: либо задачу невозможно решить точно, либо точное решение не нужно. Невозможность получить точное решение может объясняться тем, что:

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

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

ограничен класс допустимых алгоритмов.

Большинство реальных задач приходится решать, располагая лишь неполной или приближенной информацией. Численные процедуры используют арифметику конечной точности и основываются на теории аппроксимации. В принципе желательно описывать численные алгоритмы с той же строгостью, что и алгебраические. Понятие вычисления может относиться не только к числам. Первые символьные манипуляции были связаны с использованием шифров и тайнописи. Начиная с 1963 г распространяются программные системы для формульных преобразований. Другим примером символьных вычислений являются: работа с текстами, игры в шашки, шахматы, го. К этой же группе программ относятся программы для получения математических доказательств.

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

Существует ряд важных причин для анализа алгоритмов. Одной из них является необходимость получения оценок (или границ) для объема памяти или времени работы, которое потребуется алгоритму для успешной обработки конкретных данных. Машинное время и память относительно дефецитные и дорогие ресурсы. Другая – желание иметь некий количественный критерий для сравнений двух алгоритмов, претендующих на решение одной и той же задачи. Еще одна причина - желание иметь механизм для выявления наиболее эффективных алгоритмов. Иногда невозможно составить четкое мнение об относительной эффективности двух алгоритмов. Один может в среднем лучше работать, к примеру, на случайных входных данных, другой лучше работает на каких-то специальных данных. Важно также установить абсолютный критерий. Когда считать решение задачи оптимальным, т.е. когда наш алгоритм настолько хорош, что его невозможно (независимо от наших умственных способностей) значительно улучшить.

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

Ограничение финитности для практических целей является не-достаточно жестким: используемый алгоритм должен иметь не просто конечное, а предельно конечное, разумное число шагов. В реальных вычислениях главный вопрос относительно некоторой функции состоит не в том "вычислима ли данная функция", а скорее в том "вычислима ли она практически". Т.е. существует ли программа, вычисляющая функцию за время, которым мы располагаем? Можно измерять время, требуемое для вычисления каждого значения функции по конкретной программе, в предположении, что каждый шаг совершается за единицу времени. И мерой вычислительной сложности брать время вычисления.

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

 

 

Сходимость, сложность, надежность

В общем виде алгоритм определяет некоторую величину y по известной величине x, символически это можно записать y=A(x). В большинстве случаев бывает достаточно вычислить y*=A*(x*). При этом ожидается, что значение y* будет близко к искомому решению y. Возникает вопрос, что такое "близко"?

Множество элементов x любой природы называется метрическим пространством, если в нем введено расстояние р(х1,х2) между любой парой элементов, удовлетворяющее следующим аксиомам:

а) р(х1,х2) - вещественное неотрицательное число;

б) р(х1,х2)=0, только если х1=х2;

в) р(х1,х2)=р(х2,х1);

г) р(х1,х3)<=р(х1,х2)+ р(х2,х3).

Последовательность метрического пространства хn называют сходящейся по метрике к элементу х, если р(хn,х) 0 при n . Последовательность хn называется фундаментальной, если для любого >0 найдется такое k(), что р(хn,хm)< при всех n и m>k. Метрическое пространство называется полным, если любая фундаментальная последовательность его элементов сходится к элементу того же пространства. Если переменные x и y принадлежат неполным пространствам, то обосновать сходимость метода очень трудно: даже если удается доказать, что при хnх последовательность yn фундаментальная, то отсюда еще не следует, что она сходится к элементу данного пространства, т.е. к решению допустимого класса.

Сложность алгоритмов разделяют на вычислительную и описательную.

Описательная сложность является характеристикой способа, которым задается алгоритм, его описания, программы (объем программы, длина записи, число команд и т.д.)

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

Что такое формальное описание алгоритма и сложность описания интуитивно ясно. Ясно и то, что возможны различные способы описания и разные меры сложности. В качестве мер сложности программы машины Тьюринга можно использовать число состояний, произведение числа состояний на число букв алфавита ленты, объем или длину программы. Средства и методы, употребляемые для описания алгоритмов, очень разнообразны. Каждый из них определяет некоторый формальный язык. Характеристики сложности описаний соответственно зависят от выбранного языка.

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

Пусть р – простейшая операция. Простейшими можно назвать арифметические операции, операции сравнения. Обозначим сложность операции р через сомр(р) и будем считать эту величину конечной. Выбор множества Р простейших операций и определение их сложности – это часть постановки задачи.

Пусть Np – приближенный информационный оператор. Np называется допустимым по отношению к Р, если существует программа вычисления Np(f) " f Î F, состоящая из конечного числа простейших операций.

Число сомр(Np(f)) = сомр(рi) называется информационной сложностью оператора Np(f).

Алгоритм называется допустимым по отношению к Р, если существует программа вычисления (y) для y = Np(f) " f Î F,, состоящая из конечного числа простейших операций q1,... qj. Число сомр((y)) = S comp(qi) называется комбинаторной сложностью алгоритма (y).

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

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

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

Третий показатель – это интенсивность отказов Z, с помощью которого определяется распределение отказов по какому-то аргументу (например, во времени). Любые оценки показателей надежности программ могут иметь только вероятностный характер. Информация о любом дефекте должна однозначно вести к устранению этого дефекта. А в программе остаются те дефекты, о которых ничего не известно или известно недостаточно много, чтобы их найти и устранить. Получение оценок показателей надежности программ производится с помощью моделей – математических выражений, связывающих значение одного из показателей надежности с непосредственно измеряемыми параметрами, которые характеризуют программное обеспечение.

Модели можно разделить на:

априорные,

эмпирические,

непрерывные эмпирические,

дискретные эмпирические,

полные.

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

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

С помощью верификации либо доказывается абсолютная правильность программ и тогда никакие модели надежности не требуются, либо относительно программы в целом не доказывается ничего. Кроме того, дефекты семантического происхождения (например, по вине заказчика) с помощью верификации не могут быть обнаружены вообще.

 

 

Универсальные алгоритмы

Основные понятия

Можно выделить три основных типа универсальных алгоритмических моделей:

1- й тип связывает понятие алгоритма с наиболее традиционными понятями математики – вычислениями и числовыми функциями;

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

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

Машины Тьюринга

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

До сих пор все вычислительные машины в некотором смысле базируются на идее Тьюринга: их память физически состоит из битов, каждый из которых содержит либо 0 либо 1. Более того, т.н. микропрограммное управление унаследовало от этих абстрактных машин и программу, помещенную в "постоянную память", и в значительной мере структуру команды.

Машина Тьюринга представляет собой автомат, с конечным числом состояний, соединенный с внешней памятью – лентой, разбитой на ячейки, в каждой из которых записан один из символов конечного алфавита А= { a1,... am}.

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

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

Детерминированность машины Т определяется следующим образом: для любого внутреннего состояния qi и символа aj однозначно заданы

а) следующее состояние qi`

б) символ aj`, который надо записать в ту же ячейку вместо aj (стирание – это запись пустого символа)

в) направление сдвига головки dk (L – влево, R – вправо, E – на месте).

Это задание может описываться либо системой правил

qiaj qi`aj`dk

либо таблицей, строкам которой соответствуют состояния, столбцам – входные символы, а на пересечении записана тройка символов qi`aj`dk.

либо блок-схемой (диаграммой переходов), в которой состояниям соотвествуют вершины, а правилу вида (qiaj qi`aj`dk) – ребро, ведущее из qi в qi`.

Полное состояние машины Т, по которому однозначно можно определить ее дальнейшее поведение, определяется ее внутренним состоянием, состоянием ленты (т.е. символом, записанным на ленте) и положением головки на ленте.

Полное состояние будем называть конфигурацией или машинным словом. Стандартной начальной конфигурацией называется конфигурация вида q1, то есть конфигурацию, содержащую начальное состояние, в котором головка обозревает крайний левый символ слова, написанного на ленте. Аналогично, стандартной заключительной конфигурацией называется конфигурация вида qz. Ко всякой незаключительной конфигурации К машины Т применима ровно одна команда вида

qiaj qi`aj`dk,

которая конфигурацию К переводит в конфигурацию К. По-следовательность К1 К2 К3... однозначно определяется исходной конфигурацией К1 и полностью описывает работу машины Т, начиная с К1.

Для того чтобы говорить о том, что могут делать машины Т, уточним как будет интерпретироваться их поведение и как будут представляться данные.

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

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

1) для любых V и W таких, что f(V)=W q1V* q1zW*, где V* и W* – правильные записи V, W.

2) для любого V такого, что f(V) не определена, машина Т,запущенная в стандартной начальной конфигурации q1V*, работает бесконечно долго.

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

Пусть f() задана описанием: "если P() истинно, то f()=g1(), иначе f()=g2() ". Функция называется разветвлением или условным переходом к g1() и g2() по условию P().

Благодаря вычислимости композиции и разветвления словесные описания и язык блок-схем можно сделать вполне точным языком для описания работы машин Тьюринга.

Cистему команд машин Тьюринга можно интерпретировать и как описание работы конкретного механизма и как программу. Естественно поставить задачу построения машины Тьюринга, реализующей алгоритм воспроизведения работы машины Тьюринга – такая машина называется универсальной. Существование универсальной машины Тьюринга означает, что систему команд любой машины Тьюринга можно представить двояко: либо как описание работы конкретного устройства машины Т, либо как программу для универсальной машины U. Это естетственно: для инженера, проектирующего систему управления, любой алгоритм управления может быть реализован либо аппаратурно – построением соответствующей схемы, либо программно – написанием программы для универсальной управляющей ЭВМ.

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

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

В числе общих требований, предъявляемых к алгоритмам упоминалось требование результативности. В наиболее радикальном виде: по любому алгоритму А и данным определить, приведет ли работа А при исходных данных к результату или нет. Иначе говоря, нужно построить алгоритм В такой, что В(А,)=И, если А() дает результат, и В(А,)=Л, если нет.

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

Теорема: Не существует машины Тьюринга, решающей проблему остановки для произвольной машины Тьюринга.

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

 

 

Рекурсивные функции

Первоначальной целью теории вычислимости (рекурсии) было придать строгость интуитивной идее вычислимой функции, т.е. функции, значения которой могут быть вычислены или автоматически или каким-либо другим эффективным способом

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

Очевидно, что к вычислимым функциям следует отнести все константы, т.е. все натуральные числа 0,1,2.... Нет необходимости включать в базис бесконечное множество констант. Достаточно 0 и функции следования f(x)= x+1, (x').

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

(x1,...xn)=xm (m<=n)

Мощным средством получения новых функций из уже имеющихся является суперпозиция. Оператором суперпозиции называется подстановка

(h,g1,...gm)=h(g1(x1,...xn)...gm(x1,...xn)).

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

Оператором примитивной рекурсии называются подстановки, удовлетворяющие системе уравнений

f(x1,...,xn)= g(x1,...,xn)

f(x1,...,xn,y+1)= h(x1,...,xn,y,f(x1,...,xn,y)),

которая называется схемой примитивной рекурсии.

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

В формально-индуктивном виде это определение выглядит следующим образом:

1. Функции 0, Х', для всех натуральных m и n являются примитивно-рекурсивными.

2. Если h,g1,...gm – примитивно-рекурсивные функции, то – примитивно-рекурсивная функция.

3. Если g(x1,...xn),h(x1,...xm,y,z) – примитивно-рекурсивные функции, то – примитивно-рекурсивная функция.

4. Других примитивно-рекурсивных функций нет.

Примерами примитивно-рекурсивных функций являются

1. .

2. .

3. .

Отношение R(x1,...xn) называется примитивно-рекурсивным, если примитивно-рекурсивна его характеристическая функция

.

ПР-операторы

Оператор называется примитивно-рекурсивным (ПР), если он сохраняет примитивную рекурсивность функций, т.е. если результат его применения дает снова примитивно-рекурсивную функцию.

Операторы и являются ПР-операторами по определению.

Еще один ПР-оператор – оператор условного перехода , который по функциям и и предикату строит функцию

Существует теорема: если , и вычислимы по Тьюрингу, то разветвление и по также вычислимо.

В силу этой теоремы ПР-оператор вычислим по Тьюрингу.

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

Ограниченный оператор минимизации – применяется к предикатам.

Из предиката с помощью оператора получается функция .

Ограничение z в операторе дает гарантию окончания вычислений, поскольку оно оценивает сверху число вычислений предиката .

Если (ПР-оператор), то для вычисления f понадобится k+1 вычисление g и k вычислений h. В силу конечности общего числа операторов и , использованных для построения f из базисных функций, для любого k можно оценить количество элементарных действий для вычисления f.

Еще один ПР-оператор – оператор одновременной рекурсии – точнее целое семейство .

C его помощью строится рекурсивное описание сразу нескольких функций от (n-1)-ой переменной, причем значение каждой функции в точке y+1 зависит от значения всех функций в точке y.

По существу, совместная рекурсия дает рекурсивное описание функции-вектора.

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

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

2. Строго говоря, мы имеем дело не с функциями, а с их примитивно-рекурсивным описанием. Различие здесь имеет тот же смысл, что и различие между функциями и их представлением в виде формул.

Возникает вопрос: все ли функции являются примитивно-рекурсивными? Простые теоретико-множественные соображения пока-зывают, что нет.

Функция называется частично-рекурсивной, если она может быть построена из простейших функций: 0, х`, с помощью конечного числа применений , и -оператора.

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

Будучи применен к вычислимой функции - оператор снова дает вычислимую функцию.

Однако эта процедура может не привести к результату: когда на данном наборе уравнение не имеет решения. В таком случае функция считается неопределенной.

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

Частично-рекурсивная функция называется общерекурсивной, если она всюду определена.

 

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...