Выбрать книгу по жанру
Фантастика и фэнтези
- Боевая фантастика
- Героическая фантастика
- Городское фэнтези
- Готический роман
- Детективная фантастика
- Ироническая фантастика
- Ироническое фэнтези
- Историческое фэнтези
- Киберпанк
- Космическая фантастика
- Космоопера
- ЛитРПГ
- Мистика
- Научная фантастика
- Ненаучная фантастика
- Попаданцы
- Постапокалипсис
- Сказочная фантастика
- Социально-философская фантастика
- Стимпанк
- Технофэнтези
- Ужасы и мистика
- Фантастика: прочее
- Фэнтези
- Эпическая фантастика
- Юмористическая фантастика
- Юмористическое фэнтези
- Альтернативная история
Детективы и триллеры
- Боевики
- Дамский детективный роман
- Иронические детективы
- Исторические детективы
- Классические детективы
- Криминальные детективы
- Крутой детектив
- Маньяки
- Медицинский триллер
- Политические детективы
- Полицейские детективы
- Прочие Детективы
- Триллеры
- Шпионские детективы
Проза
- Афоризмы
- Военная проза
- Историческая проза
- Классическая проза
- Контркультура
- Магический реализм
- Новелла
- Повесть
- Проза прочее
- Рассказ
- Роман
- Русская классическая проза
- Семейный роман/Семейная сага
- Сентиментальная проза
- Советская классическая проза
- Современная проза
- Эпистолярная проза
- Эссе, очерк, этюд, набросок
- Феерия
Любовные романы
- Исторические любовные романы
- Короткие любовные романы
- Любовно-фантастические романы
- Остросюжетные любовные романы
- Порно
- Прочие любовные романы
- Слеш
- Современные любовные романы
- Эротика
- Фемслеш
Приключения
- Вестерны
- Исторические приключения
- Морские приключения
- Приключения про индейцев
- Природа и животные
- Прочие приключения
- Путешествия и география
Детские
- Детская образовательная литература
- Детская проза
- Детская фантастика
- Детские остросюжетные
- Детские приключения
- Детские стихи
- Детский фольклор
- Книга-игра
- Прочая детская литература
- Сказки
Поэзия и драматургия
- Басни
- Верлибры
- Визуальная поэзия
- В стихах
- Драматургия
- Лирика
- Палиндромы
- Песенная поэзия
- Поэзия
- Экспериментальная поэзия
- Эпическая поэзия
Старинная литература
- Античная литература
- Древневосточная литература
- Древнерусская литература
- Европейская старинная литература
- Мифы. Легенды. Эпос
- Прочая старинная литература
Научно-образовательная
- Альтернативная медицина
- Астрономия и космос
- Биология
- Биофизика
- Биохимия
- Ботаника
- Ветеринария
- Военная история
- Геология и география
- Государство и право
- Детская психология
- Зоология
- Иностранные языки
- История
- Культурология
- Литературоведение
- Математика
- Медицина
- Обществознание
- Органическая химия
- Педагогика
- Политика
- Прочая научная литература
- Психология
- Психотерапия и консультирование
- Религиоведение
- Рефераты
- Секс и семейная психология
- Технические науки
- Учебники
- Физика
- Физическая химия
- Философия
- Химия
- Шпаргалки
- Экология
- Юриспруденция
- Языкознание
- Аналитическая химия
Компьютеры и интернет
- Базы данных
- Интернет
- Компьютерное «железо»
- ОС и сети
- Программирование
- Программное обеспечение
- Прочая компьютерная литература
Справочная литература
Документальная литература
- Биографии и мемуары
- Военная документалистика
- Искусство и Дизайн
- Критика
- Научпоп
- Прочая документальная литература
- Публицистика
Религия и духовность
- Астрология
- Индуизм
- Православие
- Протестантизм
- Прочая религиозная литература
- Религия
- Самосовершенствование
- Христианство
- Эзотерика
- Язычество
- Хиромантия
Юмор
Дом и семья
- Домашние животные
- Здоровье и красота
- Кулинария
- Прочее домоводство
- Развлечения
- Сад и огород
- Сделай сам
- Спорт
- Хобби и ремесла
- Эротика и секс
Деловая литература
- Банковское дело
- Внешнеэкономическая деятельность
- Деловая литература
- Делопроизводство
- Корпоративная культура
- Личные финансы
- Малый бизнес
- Маркетинг, PR, реклама
- О бизнесе популярно
- Поиск работы, карьера
- Торговля
- Управление, подбор персонала
- Ценные бумаги, инвестиции
- Экономика
Жанр не определен
Техника
Прочее
Драматургия
Фольклор
Военное дело
Жар холодных числ и пафос бесстрастной логики - Бирюков Борис Владимирович - Страница 33
Nn (х1, х2, ..., Хn) = 0 при любых значениях аргументов.
(б) Одноместная функция S «следования за», то есть функция, для которой выполняется равенство S(х) = х' где штрих означает взятие числа, непосредственно следующего за x в натуральном ряду.
(в) n-местные проектирующие функции Ini, Для которых Ini{х1, .... xn) = xi ( i = 1, 2, ..., n; n = 1, 2, 3, ...).
Функции, получающиеся из исходных конечным числом применений схем порождения I и II, называются примитивно рекурсивными; как очевидно, эти функции являются всюду определенными. К примитивно рекурсивным относятся не все, а только часть арифметических функций (правда, наиболее часто встречающееся такого рода функции примитивно рекурсивны). Если разрешить применять схему порождения III, то функции, которые будут таким образом возникать, называются частично рекурсивными. Хотя частично рекурсивные функции — как и примитивно рекурсивные — в конечной счете получаются из исходных (примитивно рекурсивных) функций (а), (б), (в), они в общем случае не всюду определены; это вызывается спецификой (μ-оператора, который из всюду определенной может породить частичную (и даже нигде не определенную) функцию. Если частично рекурсивная функция от n аргументов является всюду определенной (то есть если она определена для любого набора из n натуральных чисел), она называется общерекурсивной функцией. Таким образом, каждая примитивно рекурсивная функция является общерекурсивной, а каждая общерекурсивная — частично рекурсивной. Однако существуют частично рекурсивные функции, не являющиеся общерекурсивными, и общерекурсивные, не являющиеся примитивно рекурсивными.
Итак, математическая часть нами изложена; перейдем к методологическому аспекту разговора. Рассмотрим характер тех действий, которые производятся при вычислении значений рекурсивных функций.
Если исходная функция принадлежит к типу (а), то для любого набора значений ее аргументов ее значением является нуль. Эта функция «аннулирует» любой набор. Операция очень проста, она не требует особой фантазии или интуиции.
Работа с исходной функцией (б) сводится к написанию вместо данного числа такого числа, которое непосредственно следует за ним в натуральном ряду. Такая операция необходима для математики —это некий ее «голодный минимум». Она необходима также для любого конструктивного процесса, независимо от области, в которой он осуществляется. Брауэр, как мы знаем, считал процесс порождения следующего натурального числа изначальным актом, на котором зиждется вся деятельность интеллекта математика. Оставляя в стороне философскую сторону взглядов Брауэра, следует согласиться с тем, что операция «взятие следующего» обладает определенной «первичностью» — не ясно, к чему более простому можно было бы ее редуцировать.
Смысл проектирующих функций тоже очень прост: каждая из них отыскивает i-тый по порядку аргумент и объявляет его значением функции. Вычисление значений такой Функции выполняется с помощью обыкновенного счета: если дан определенный набор значений аргументов некоторой функции типа (в), то считывается нижний индекс i в ее обозначении и в упомянутом наборе отыскивается (с помощью счета) i-тое число; это число и оказывается значением функции.
Что же представляют собой акции, позволяющие строить из одних рекурсивных функций другие, вообще говоря, более сложные рекурсивные функции?
Подстановка есть не что иное, как вычисление, разбитое на два этапа: сначала вычисляются значения всех «внутренних» функций, а потом — значение «внешней» функции при аргументах, равных полученным на предыдущем этапе числам. Это — акт суперпозиции, последовательного выполнения однотипных операций. Например, суперпозиция функций I3i и S (где S — внешняя функция) порождает функцию от трех аргументов: f(х1, х2, х3) = S (I3i (х1, х2, х3)); суперпозиция функций S, I11, N1 и I31 (внешняя функция) порождает одноместную функцию q(х) = I31 (S(х), I11(х), N1(х)) и т. д. Самый придирчивый критик не заподозрит в подобных процедурах присутствия чего-либо неясного.
Вычисление по схеме примитивной рекурсии тоже не вызывает недоверия с точки зрения своей четкости и общепонятности. Это мы уже видели на примерах вычисления значения функции «усеченное вычитание», определенной рекурсивно (см. с. 127)[4]. Собственно говоря, мы очень часто пользуемся методом построения какой-то последовательности, формируя каждый ее член по предыдущим членам. В данной схеме следует обратить внимание на то, что вычисление каждого последующего значения нуждается в знании только одного, непосредственно предыдущего, значения. Это, конечно, простейший вариант подобного типа вычислений. Но тем не менее при вычислении по схеме рекурсии значения некоторой функции для какого-то значения ее аргумента (например, для числа 137) приходится на промежуточных фазах вычисления находить значения функции для всех предыдущих значений аргумента: 0, 1, 2, ..., 136, хотя каждый раз все значения, кроме самого последнего, мы можем забывать, стирать с доски и т. д.
Акция, соответствующая четвертому пункту (мю-операция), иначе называется операцией взятия наименьшего числа. Ее включили в определение рекурсивных функций, так сказать, неохотно, под давлением суровой необходимости (в первоначальном определении у Гёделя мю-операции не было), поскольку без нее, как выяснилось, не могут быть получены некоторые функции, играющие в математике важную роль. Как мы отметили выше, функции, в которых участвуют только подстановка и рекурсия, называют примитивно рекурсивными, особо выделяя тем самым мю-операцию. Каков же познавательный статус этой операции? Чем существенным отличается она от подстановки и рекурсии?
Посмотрим сначала, как конкретно функционирует мю-операция. Пусть надо задать способ нахождения наименьшего числа у, для которого выполняется некое условие g°(x1, x2, y) = 0, имеющее вид 100 ∸ х1•хy2 = 0 (напомним, что это равенство равносильно неравенству х1 • хy2 >> 100). Это означает, что над функцией g° (х1, х2, у) надо произвести мю-операцию — определить функцию f° (х1,x2) = μy(g° (x1, x2, y) = 0) = μy(100 ∸ x1 • хy2 = 0).
Сделать это нетрудно, так как функция g° задана, и мы для каждого набора значений ее аргументов х1, х2 можем установить (путем перебора, начинающегося с нуля) то наименьшее значение ее аргумента у, при котором g°(х1, х2, у) = 0. В самом деле, пусть значения аргументов х1, и x2 например, таковы: х1 = 3, х2 = 2. Тогда для вычисления f° (3,2,) надо поступить следующим образом.
1. Положим y = 0; вычислим g°(3, 2, 0). Получим:
100 ∸ 3 • 2° = 100 ∸ 3 • 1 = 100 ∸ 3 = 97. Условие не выполнено, поэтому сделаем следующий шаг, перейдем к значению y = 1.
2. Положим y = 1; вычислим g°(3, 2, 1). Получим:
100 ∸ 3 • 21 = 100 ∸ 3 • 2 = 100 ∸ 6 = 94. Требуемое условие не выполнено, так что возьмем следующее значение у.
3. Положим y = 2; вычислим g° (3, 2, 2). Получим:
100 - 3 • 22 = 100 ∸ 3 • 4 = 100 ∸ 12 = 88. Условие не выполнено. Перейдем к следующему значению у,
4. Положим y = 3; вычислим g° (3, 2, 3). Получим:
100 ∸ 3 • 23 = 100 ∸ 3 • 8 = 100 ∸ 24 = 76. Требуемое условие не выполнено; берем следующее значение у.
5. Положим y = 4; вычислим g° (3, 2, 4). Получим:
100 ∸ 3 • 24 = 100 - 3 • 16 = 100 - 48 = 52. Требуемое условие не выполнено; сделаем еще один шаг.
6. Положим y = 5; вычислим g° (3, 2, 5). Получим:
100 ∸ 3 • 25 = 100 ∸ 3 • 32 = 100 ∸ 96 = 4. Требуемое условие не выполнено, и мы возьмем на единицу большее значение у.
7. Положим у = 6; вычислим g° (3, 2, 6). Получим:
100 ∸ 3 • 26 = 100 ∸ 3 • 64 = 100 ∸ 192 = 0. Условие на этот раз выполнено, поэтому в качестве значения функции f° берется число 6—мы пишем: f° (3, 2) = μy(g° (3, 2, 6) = 0) = 6.
Таким же образом, конечно, можно вычислить значение функции f° для любых значений двух ее аргументов.
- Предыдущая
- 33/52
- Следующая