Теорема Клини о нормальной форме - Рекурсивные функции
Существуютпримитивнорекурсивныефункция u и примитивно разрешимый предикат T такие, что e, x ( E(x)=p ( k [T(e, x,k)])). В частности, e, x ( E(x) k T(e, x,k))
(здесь и далее запись вида f(x)= означает, что функция f неопределена в точке x).
Доказательство.
Неформальная формулировка результата прямо следует из предыдущих рассуждений. Для более формального доказательства рассмотрим слегка измененную версиюпрограммы вычисления универсальной функции, добавив в нее счетчик состояний:
{сделать шагов n шагов в вычислении универсальной функции}
{и проверить, не вычислилось ли значение y}
Start(e, x,y, n);
Привести_программу_в_ начальное_состояние;
Счетчик:=O;
While Счетчик<=n and Не_попали_в_конечное_состояние do
Begin Перейти_к_следующему_состоянию; Счетчик:=S(Счетчик) end
По_конечному_состоянию_определить_значение_функции
IfРезультат=y
Stop(1) {true}
Else
Stop(0) {false}
End
Эта программа вычисляет предикат "при входных данных e, x программа вычисления универсальной функции на шаге n вычисляет y", обозначим его через T1(e, x,n, y). Очевидно, за счет добавления счетчика - параметра цикла - единственный цикл нашей программы гарантированно сходиться, т. е. Т1 - примитивно разрешимый предикат. Для окончания доказательства осталось положить T(e, x,k)= T1(e, x,Элемент_пары(k,1),Элемент_пары(k,2)) и p(k)=Элемент_пары(k,2)
Результат предыдущей теоремы может показаться неожиданным - фактически, он означает, что любую программу можно преобразовать в эквивалентную ей программу, содержащую Единственный цикл. Это действительно так, и можно дать более строгое доказательство этого факта. Но, на практике, все нащи нетривиальные программы содержат множество циклов. Тем более, поклонники нисходящего проектирования программ вряд ли сочтут такую форму программы нормальной, т. е. канонической. С другой стороны, для сторонников событийного программирования такая форма программ естественна - они знают, что в интерактивной программеналичествует если и не единственный, то главный цикл - цикл обработки событий, предназначенный для определения типа компонент входного потока и вызова соответствующих этим типам процедур (методов). Мы продолжим разговор о моделях вычислений с единственным циклом и трактовке работы алгоритмов как реакции на внешние события в лекции по теории автоматов.
Похожие статьи
-
Теорема о параметризации., Универсальные функции - Рекурсивные функции
Любую часть x1,x2,...,xn входных значений можно породить программно, более того - существует алгоритм, который генерирует по x1,x2,...,xn текст...
-
Теорема об универсальной функции - Рекурсивные функции
Для любого n, nN, универсальная функция u(n) вычислима. Доказательство. При доказательстве мы можем ограничиться случаем N=1. Действительно, программу,...
-
Синтаксис и семантика. Теорема Райса - Рекурсивные функции
Попробуем теперь проанализировать круг проблем, неразрешимость которых доказана в предыдущем пункте. Общим для них является то, что по кодам, т. е....
-
Теорема о параметризации - Рекурсивные функции
Одно и то же выражение может порождать несколько разных функций, от разного числа аргументов. Так, обычное арифметическое выражение xK можно считать...
-
Перечислимость. - Рекурсивные функции
В предыдущем упражнении мы показали, что операции алгебры логики не выводят за пределы разрешимых предикатов. Но полный язык математической логики, как...
-
Теория алгоритмов. Основные результаты, Программы как данные - Рекурсивные функции
Вместо предисловия . Сверх-идеей любой научной теории можно считать перевод знания из сферы подсознательного, интуитивногов осознанную, точную и...
-
Еще одним подходом к проблеме формализации алгоритма являются, так называемые, рекурсивные функции. Исторически этот подход возник первым, поэтому в...
-
Кодирование программ - Рекурсивные функции
(Эффективной) Нумерацией , или Перечислением множества А назовем Произвольное эффективное отображение f :N A, f(N)=A; таким образом, мы допускаем, что в...
-
Сводимость - Рекурсивные функции
Помимо построения контрпримеров, в математических доказательствах часто используют метод сведения, который на практике мы часто формулируем в виде...
-
Лемма (о декартовом произведении)., Замечания и упражнения - Рекурсивные функции
Если А - эффективное множество, то Для любого эффективного множества B AB эффективно (и, следовательно, любое декартово произведение A1A2...Аn...
-
Принцип сходимости, Предел функции. Теорема Гейне - Свойства функций
Рассмотрим вопрос о существовании пределов последовательностей концевых точек бесконечной системы промежутков, вложенных друг в друга. Лемма Кантора ....
-
Неразрешимость - Рекурсивные функции
Сейчас же займемся более важной задачей - определением принципиальных границ вычислимости. Если теоремы о параметризации, универсальнойфункциии...
-
Выбор математической формы функции при моделировании зависимости выпуска продукции от производственных факторов Постановка проблемы. Одним из важнейших...
-
Ответ: y=f(kx) получается из Графика функции f(x) сжатием его вдоль оси ох в k раз, если k>1 и растяжением в 1 деленную на k раз, если k>0 но меньше 1....
-
Теорема 1. Предел постоянной равен самой постоянной. . Доказательство. f(x)=с, докажем, что . Возьмем произвольное e>0. В качестве d можно взять любое...
-
Сложение, вычитание, умножение комплексных чисел в алгебраической форме производят по правилам соответствующих действий над многочленами. Четность и...
-
Неразрешимость - методы доказательства, Диагонализация - Рекурсивные функции
Основными методами при доказательстве теорем о не существовании алгоритмовявляются - прямой метод Диагонализации, восходящий к "диагональному"...
-
Линейная функция - Конформное отображение
Определение 2. Функция вида: , где - фиксированные комплексные числа, называется линейной. Определение 3. Отображение, осуществимое линейной функцией...
-
Непрерывность композиции, Точки разрыва - Свойства функций
Пусть задана функция, со значениями в, и на множестве определена функция со значениями в. Тогда для любого можно вычислить, на можно определить функцию...
-
В данной работе доказывается методами элементарной математики "большая" или "последняя" теорема Ферма. Некоторая, излишняя в обычных случаях, подробность...
-
Технология разработки формы для ввода исходных данных средствами VBA Для разработки формы ввода исходных данных необходимо отобразить вкладку...
-
Построим функцию роста валового регионального продукта: Таблица 11-Данные для функции роста ВРП Год (t) Y (миллион рублей) 1 372930 2 483951 3 648211 4...
-
Структурная и приведенная формы модели. - Моделирование в эконометрике
Система совместных, одновременных уравнений (или структурная форма модели) обычно содержит эндогенные и экзогенные переменные. Эндогенные Переменные...
-
Интегральная теорема Муавра-Лапласа
Предположим, что в условиях схемы Бернулли проводится испытаний, в результате каждого из которых с вероятностью () происходит событие. Интегральная...
-
1. Нормальные алгоритмы Маркова Для формализации понятия алгоритма российский математик А. А. Марков предложил использовать ассоциативные исчисления....
-
Пусть u = f(x, y) - функция, определенная в области w. Рассмотрим точку М(х, у) О w и некоторое направление l, определяемое направляющими косинусами Cosa...
-
Функции и ее свойства - Методы решения системы линейных уравнений
В современной математике понятие множества является одним из основных. Универсальность этого понятия в том, что под него можно подвести любую...
-
Выполнил: Шварц В. И. 9-Б класс Руководитель: Шагалина Д. Г. Межгорье 2005 Решение уравнений и неравенств, содержащих выражения под Знаком модуля Любое...
-
Выделим случай, когда входной сигнал X ( T ) является элементарной функцией 1( T ). Реакцию системы на воздействие 1( T ) можно компактно: [1] Где...
-
Теорема: Для того, чтобы ограниченная на сегменте функция была интегрируемой на этом сегменте, необходимо и достаточно, чтобы для любого нашлось такое...
-
Метод Колывагина-Флаха - Великая теорема Ферма
К лету 1991 года Уайлс проиграл сражение: теорию Ивасавы не удалось приспособить к решению проблемы. Он снова обратился к научным журналам и монографиям,...
-
Если функция f(x) периодична с периодом Т, то по значениям этой функции на любом отрезке длины Т можно восстановить ее значения на всей числовой прямой....
-
Опытом называется всякое осуществление определенных условий и действий, при которых наблюдается изучаемое случайное явление. Опыты можно характеризовать...
-
Дуэль с бесконечностью - Великая теорема Ферма
Чтобы доказать Великую теорему Ферма, Уайлсу было необходимо сначала доказать гипотезу Таниямы-Шимуры о том, что каждой эллиптической кривой можно...
-
Создатель Великой проблемы - Великая теорема Ферма
Пьер де Ферма родился 20 августа 1601 года в городе Бомон-де-Ломань на юго-западе Франции. Его отец, Доминик Ферма, был состоятельным торговцем кожей,...
-
Теоремы Ферма, Ролля, Лагранжа и Коши
Введение В данном реферате рассматриваются теоремы Ферма, Ролля, Лагранжа и Коши. "Теорема - высказывание, нравственность которого установлена при помощи...
-
Методы построения функций принадлежности нечетких множеств - Нечеткая логика
В приведенных выше примерах использованы прямые методы, когда эксперт или просто задает для любого x?E значение ?A(x), или определяет функцию...
-
Интегральная и дифференциальная функции распределения - Основы научных исследований
Наиболее общей формой задания распределения случайных величин является Интегральная функция распределения . Она определяет вероятность того, что...
-
Пусть Dl, r() соответственно левые (правые) границы интервалов I, отвечающих на криволинейной трапеции ОИО значениям 0< < 1. Тогда интересующая нас...
-
Вычисления для следующих входных данных F=1000H m=200 кг m'=1 кг/сек k=2 t0=0 сек V0=0 м/сек B=50 n=50 V1 (t) - результаты, полученные с помощью...
Теорема Клини о нормальной форме - Рекурсивные функции