Cтраница 2
Конечные последовательности базовых символов называются выражениями теории S. [16]
Произвольная конечная последовательность символов алфавита ( в том числе и пустая) называется цепочкой, Произвольное подмножество LA множества всех возможных цепа -, чек называется языком над А. [17]
В рассматриваемой СПД реализован режим коммутации пакетов, представляющей собой такой способ передачи, при котором данные из сообщений пользователей разбиваются на отдельные пакеты, маршруты передачи которых в сети от источника к получателю определяются в каждом УК, куда пакеты поступают. Под сообщениями понимается конечная последовательность символов, имеющая смысловое содержание. Пакет - это блок данных с заголовком, представленный в установленном формате и имеющий ограниченную максимальную длину. Отметим, что СПД с коммутацией пакетов обладают высокой эффективностью благодаря возможности быстрой перестройки путей передачи данных ( маршрутизации) при возникновении перегрузок и повреждении элементов СПД. Эффективность различных вариантов построения СПД и ее фрагментов оценивается средними временами доставки данных пользователям и вероятностями отказа в установлении требуемого пользователю соединения в данный момент времени. [18]
Разумеется, не всякая конечная последовательность символов является высказыванием; например, ( S0 Л ( 55)) - высказывание, а л л) S3 и S0 л - нет. [19]
F - множество всех конечных последовательностей символов, которые являются образующими или их обратными. Все слова из F делятся на классы следующим образом: если Wi и W2 - эквивалентные слова из F, то Wi и W2 принадлежат одному классу; если Wi и W2 - не эквивалентные слова из F, то Wi и W2 не лежат в одном классе. Иначе говоря, слова Wi и W2 лежат в одном классе тогда н только тогда, когда они эквивалентны. Общая проблема, состоящая в том, чтобы решить в случае произвольной группы, будут ли два слова эквивалентны, крайне трудна. [20]
Метаматематика - это теория, изучающая формализованные математические теории. Формализованная теория-это, грубо говоря, множество некоторых конечных последовательностей символов, называемых формулами и термами, и множество некоторых простых операций, производимых над этими последовательностями. Формулы и термы, получаемые с помощью pie - скольких простых правил, служат заменой для предложений и функций интуитивной математической теории. Операции над формулами соответствуют элементарным шагам дедукции в математических рассуждениях. Формулы, соответствующие аксиомам интуитивной теории, играют особую роль - они являются аксиомами формализованной теории. Формулы, которые могут быть выведены из аксиом посредством принятых операций, соответствуют теоремам теории. [21]
Метаматематика - это теория, изучающая формализованные математические теории. Формализованная теория-это, грубо говоря, множество некоторых конечных последовательностей символов, называемых формулами и термами, и множество некоторых простых операций, производимых над этими последовательностями. Формулы и термы, получаемые с помощью нескольких простых правил, служат заменой для предложений и функций интуитивной математической теории. Операции над формулами соответствуют элементарным шагам дедукции в математических рассуждениях. Формулы, соответствующие аксиомам интуитивной теории, играют особую роль - они являются аксиомами формализованной теории. [22]
Во-вторых, можно отказаться от требования счетно-сти сигнатуры и сказать так: для всякого подмножества А С М найдется элементарная подструктура М С М, содержащая А, мощность которой не превосходит максимума из NQ, мощности множества А и мощности сигнатуры. В самом деле, и конструкция замыкания относительно сигнатурных операций, и конструкция экзистенциального замыкания, и счетное объединение возрастающей цепи не выводят мощность за пределы указанного максимума, поскольку и формулы, и термы являются конечными последовательностями символов сигнатуры и счетного числа других символов ( см. подробнее в [6]); то же самое можно сказать о числе возможных наборов значений параметров. [23]
В рассматриваемой ИВС реализован режим коммутации пакетов, подставляющий такой способ передачи, при котором данные из сообщений пользователей разбиваются на отдельные пакеты. Маршруты передачи пакетов в сети от источника к получателю определяются в каждом УК, куда они поступают. Под сообщениями понимается конечная последовательность символов, имеющая смысловое содержание. Пакет - это блок данных с заголовком, представленный в установленном формате и имеющий ограниченную максимальную длину. Отметим, что ИВС с коммутацией пакетов обладают высокой эффективностью благодаря возможности быстрой перестройки путей передачи данных ( маршрутизации) при возникновении перегрузок и повреждении элементов ИВС. Эффективность различных вариантов построения ИВС и ее фрагментов оценивается средними временами доставки данных пользователям и вероятностями отказа в установлении в данный момент времени требуемого пользователю соединения. [24]
При рассмотрении ( конечного или бесконечного) счетного множества числа, соответствующие его элементам в некотором фиксированном пересчете, можно употреблять в качестве индивидуальных обозначений или названий этих элементов. Но и обратно, если название или явное выражение в некоторой заранее данной недвусмысленной системе обозначений может быть индивидуальным образом сопоставлено каждому элементу некоторого множества, то это множество ( конечное или бесконечное) счетно при том условии, что название или выражение должно быть конечной последовательностью символов, выбранных из данного конечного алфавита доступных нам символов. Например, алгебраические уравнения с целыми коэффициентами могут быть записаны с помощью десятичных обозначений для коэффициентов и показателей. Запись показателей вверху является несущественной особенностью наших обозначений, которую можно устранить с помощью подходящего соглашения. [25]
Рассмотрим, например, задачу об умножении двух многочленов с целыми коэффициентами. Проблема в том, как записать эти многочлены, чтобы их можно было ввести в компьютер. Машины Тьюринга, которые мы рассматриваем ниже, понимают лишь конечные последовательности символов ( слова) из некоторого конечного множества А, называемого внешним алфавитом. Поэтому строгая формулировка вычислительной задачи должна включать в себя алфавит и способ кодировки входных данных. [26]
С каждым алфавитным оператором связывается интуитивное представление о его сложности. Наиболее простыми являются алфавитные операторы, осуществляющие посимвольные отображения. Посимвольное отображение состоит в том, что каждый символ s входного слова а заменяется некоторым символом выходного алфавита В. Большое значение имеют так называемые кодирующие отображения. Под кодирующим отображением понимается соответствие, сопоставляющее каждому символу входного алфавита некоторую конечную последовательность символов в выходном алфавите, называемую кодом. [27]
Они образуют несчетное множество. Вычислимые функции образуют очень важное подмножество, к изучению которого мы приступаем. Действительно, при использованииу любого алгоритмического языка всякая программа состоит из конечной последовательности символов конечного или счетного алфавита. Отсюда следует, что множество программ счетно-бесконечное. [28]
Рассмотрим несколько отличную форму проблем индуктивного вывода. Предположим, что нам дана достаточно длинная последовательность символов и что задача состоит в предсказании последующих символов этой последовательности. Это обычная задача для тех случаев, где требуется оценивать вероятности по индукции. Задача эта несколько освежена введением современного понятия универсальной вычислительной машины и составленного для нее языка программирования. Программа называется допустимой, если, получив ее, машина печатает последовательность, пусть даже бесконечную, которая начинается с заданной конечной последовательности символов. Таким образом, каждая допустимая программа осуществляет предсказание. [29]