Cтраница 1
Блуп, Флуп и Глуп - это не имена гномов, не разговоры лягушек в пруду и не бульканье воды в засорившейся раковине. Это компьютерные языки, каждый из которых имеет особое предназначение. Они были придуманы специально для этой главы. Мы воспользуемся ими для того, чтобы объяснить новые значения слова рекурсивный - в частности, понятия примитивной рекурсивности и общей рекурсивности. [1]
Блуп - язык для определения предсказуемо конечных вычислений. [2]
Определяющей чертой Блупа была ограниченность его циклов. Что, если мы опустим это требование и создадим второй язык, под названием Флуп. [3]
Другая важная черта Блупа - это то, что выходом некоторых процедур в нем может быть ДА или НЕТ вместо числового значения. Такие процедуры являются не функциями, но тестами. Чтобы указать на эту разницу, в конце названия теста ставится вопросительный знак. Кроме того, стандартным выбором ВЫХОДА здесь, разумеется, будет не 0, а НЕТ. [4]
Теперь нам нужен тест Блупа под названием ТЕРМИНАТОР. [5]
Остается объяснить две важные особенности Блупа. Первая из них состоит в том, что однажды определенная процедура может быть вызвана при определении следующих процедур. Она рассматривается в таком случае как не что целое, как основной шаг. [6]
Так же, как в случае Блупа, вообразим клуб, членами которого являются все программы Флупа. [7]
Давайте посмотрим, как работают эти черты Блупа в алгоритме, проверяющем, какие числа являются простыми. [8]
Давайте теперь посмотрим на другую процедуру, которая покажет нам некоторые черты Блупа, делающие эту программу более общей. [9]
До сих пор мы просто повторяли с Флупом то, что ранее проделали с Блупом. Посмотрим теперь, удастся ли нам скопировать последнюю часть - диагональный метод. [10]
Для начала представим себе забавное понятие: некий клуб, членами которого являются все возможные программы Блупа. Нет нужды говорить, что число членов этого клуба ( назовем его клубом Б) бесконечно. [11]
ОСНОВНОЙ ФАКТ 1: Свойство пара-доказательности - это примитивно рекурсивное свойство теории чисел; следовательно, оно может быть проверено на программе Блупа. [12]
Прежде, чем рассмотреть еще несколько интересных вопросов, касающихся Блупа, и перейти к его родственнику, Флупу, давайте вернемся к тому, зачем нам вообще понадобился Блуп, и к его связи с ТТЧ. Ранее я сказал, что критическая масса, необходимая формальной системе для приложения метода Геделя, достигается тогда, когда в этой системе представимы все примитивно-рекурсивные понятия. Прежде всего, мы должны различать между понятиями представимости и выразимости. Выразить предикат означает просто перевести его с русского языка на язык формальной системы. Это не имеет ничего общего с теоремнос-тью. [13]
Мы также показали, что Блуп не описывает всех функций натуральных чисел, которые можно выразить словами. Можно ли улучшить Блуп таким образом, что Beldiag [ N ] станет в нем представимой. [14]
Из этого следует, что в схемах, которые мы анализируем, можно говорить о двух видах формы. Прежде всего, там существуют такие качества, как правильно-сформированность, наличие которой можно определить с помощью предсказуемо конечных тестов, как в программах Блупа. [15]