Cтраница 1
Последовательность классов & п обладает следующими свойствами. [1]
В этой работе мы изучаем последовательность классов вычислимых функций, сложность вычисления которых можно сравнительно просто предсказать. Класс рекурсивных функций состоит из таких функций, для которых существуют механические процедуры для получения значений из аргументов. Однако этот класс, так как он включает все вычислимые функции, должен содержать функции со сколь угодно сложными вычислениями. Существуют различные более ограниченные классы функций, которые легко вычисляются каким-либо способом, однако это в большой степени происходит за счет интуиции. Приятное исключение составляет класс F - функций, вычислимых2) конечными автоматами. Но этот класс слишком ограничен: он не содержит даже умножения. Мы строим иерархию более содержательных классов функций; каждый из них определяется как класс таких функций, сложность вычисления которых предсказывается функцией из предыдущего класса. [2]
Следующее определение вводит понятие независимости последовательности классов событий. [3]
Сначала мы покажем, что объединение любой рекурсивно перечислимой иерархии классов сложности ( последовательности возрастающих классов сложности) само является классом сложности. [4]
Первая задача интерпретации - определение класса моделей сравнения - может быть решена рассмотрением последовательности расширяющихся классов гипотетических моделей и выбором минимального класса, содержащего индивидуальные модели, формально сопоставимые с и. [5]
Во-первых, мы доказываем теорему об объединении, которая утверждает, что объединение любой рекурсивно перечислимой последовательности возрастающих классов сложности снова является классом сложности. Отсюда следует, что многие изучавшиеся ранее подклассы рекурсивных функций естественным образом подходят под многие меры сложности. Например, существует рекурсивная граница L ( n) емкости ленты, такая, что класс функций, вычислимых на машинах Тьюринга, у которых длина ленты ограничена функцией L ( n), состоит точно из примитивно рекурсивных функций. Второй главный результат этой части - теорема об именовании - несколько ослабляет остроту теоремы о пробелах, показывая, что для любой меры существует ( измеримое) множестэе функций, которые именуют все классы сложности, не оставляя сколь угодно широкие пробелы вверх. К сожалению, оказывается, что именование классов сложности может иметь сколь угодно широкие пробелы вниз. [6]
Количественная ( кардиналистская) функция полезности - функция полезности, возникающая в том случае, когда мы не только можем определить расстановку и последовательность классов безразличия, но и указываем, как мы оцениваем разность в уровнях благосостояния, соответствущих каждому из таких классов безразличия. [7]
В главах 2 - 28 изложена химия отдельных классов. Избранная последовательность классов такова, что позволяет постепенно знакомить читателя с новыми реакциями, понятиями и концепциями органической химии с максимальным соблюдением принципа от простого к сложному. По этой причине в первых главах ( главы 2 - 11) излагаются химия углеводородов и методы введения в их молекулы различных функциональных групп. [8]
Обратно, если две последовательности гр. SM соответствуют одной и той же последовательности классов вычетов ЭКя то их разность - нуль-последовательность. [9]
Ft имеют слишком упрощенную ( грубую) структуру. В этом случае надо расширять класс F0, беря, возможно, последовательность расширяющихся классов F0 с Ftcz. Fn, содержащий элементы ( напр. [10]
То же самое справедливо относительно операций счетного объединения и счетного пересечения. Применение к данному семейству М множеств попеременно бе-операции Ф и Фс позволяет построить возрастающую трансфинитную последовательность классов МаМ, MI. Колмогорова о непустоте классов: если Ф есть нормальная бе-операция более мощная, чем операции счетного объединения ( или счетного пересечения), а М есть семейство всех замкнутых подмножеств метрич. Ма, a Wj, порождаемые операцией Ф из семейства М, попарно различны. Аналогичным образом Л - операция порождает из семейства М борелевских множеств классы Ма. Каждое С-множество измеримо и обладает свойством Бэра. Все С-множества входят в класс ( В2), но не исчерпывают его. [11]