Текст книги "Большая Советская Энциклопедия (РЕ)"

Рекурсивные функции

Рекурси'вные фу'нкции (от позднелатинского recursio – возвращение), название, закрепившееся за одним из наиболее распространённых вариантов уточнения общего понятия арифметического алгоритма, т.е. такого алгоритма, допустимые исходные данные которого представляют собой системы натуральных чисел, а возможные результаты применения являются натуральными числами. Р. ф. были введены в 30-х гг. 20 в. С. К. Клини, в свою очередь основывавшимся на исследованиях К. Гёделя, Ж. Эрбрана и др. математиков.

  Каждая Р. ф. задаётся конечной системой равенств точно охарактеризованного типа в том смысле, что её значения вычисляются с помощью этой системы равенств по точно формулируемым правилам, причём таким образом, что в итоге для вычисления значений заданной Р. ф. получается алгоритм определённого типа.

  Арифметические функции, для вычисления значений которых имеются какие-либо алгоритмы, принято называть вычислимыми. Вычислимые функции играют в математике важную роль. Вместе с тем, если понятию алгоритма здесь не будет придан точный смысл, то и само понятие вычислимой функции окажется несколько расплывчатым. Р. ф. уже в силу самого характера своего определения оказываются вычислимыми. В известном смысле верно и обратное: имеются серьёзные основания считать, что математическое по своему характеру понятие рекурсивности является точным эквивалентом несколько расплывчатого понятия вычислимости. Предложение считать понятие вычислимости совпадающим по объёму с понятием рекурсивности известно в теории Р. ф. под названием тезиса Чёрча по имени американского математика А. Чёрча, впервые (в 30-х гг. 20 в.) сформулировавшего и обосновавшего это предложение. Принятие тезиса Чёрча позволяет придать понятию вычислимой арифметической функции точный математический смысл и подвергнуть это понятие изучению при помощи точных методов.

  Р. ф. являются частичными функциями, т. е. функциями, не обязательно всюду определёнными. Чтобы подчеркнуть это обстоятельство, часто в качестве синонима используют термин «частично рекурсивные функции». Р. ф., определённые при любых значениях аргументов, называют общерекурсивными функциями.

  Определению Р. ф. может быть придана следующая форма. Фиксируется небольшое число чрезвычайно простых исходных функций, вычислимых в упомянутом выше интуитивном смысле (функция, тождественно равная нулю, функция прибавления единицы и функции, выделяющие из системы натуральных чисел член с данным номером); фиксируется небольшое число операций над функциями, переводящих вычислимые функции снова в вычислимые (операторы подстановки, примитивной рекурсии и минимизации). Тогда Р. ф. определяются как такие функции, которые можно получить из исходных в результате конечного числа применений упомянутых выше операций.

  Оператор подстановки сопоставляет функции f от n переменных и функциям g₁, . . ., g_n от m переменных функцию h от m переменных такую, что для любых натуральных чисел x₁, .., x_m

h(x₁, .., x_m) @ f (g₁(x₁, .., x_m), ..., g_m(x₁, .., x_m))

(здесь и ниже условное равенство @ означает, что оба выражения, связываемые им, осмыслены одновременно и в случае осмысленности имеют одно и то же значение).

  Оператор примитивной рекурсии сопоставляет функциям f от n переменных и g от n + 2 переменных функцию h от n + 1 переменных такую, что для любых натуральных чисел x₁, .. .., x_n, y

h(x₁, .., x_n ,0) @ f(x₁, .., x_n),

h(x₁, .., x_n, y + 1) @ g(x₁, .., x_n, y, h(x₁, .., x_n, y )).

  Оператор минимизации сопоставляет функции f от n переменных функцию h от n переменных такую, что для любых натуральных чисел x₁, .., x_n

h(x₁, .., x_n) @ f(x₁, .., x_n-1, y)

где у таково, что f(x₁, .., x_n-1, y-1) определены и отличны от x_n, а f(x₁, .., x_n, y) определена и равна x_n, если же у с указанными свойствами не существует, то значение h(x₁, .., x_n) считается не определённым.

  Важную роль в теории Р. ф. играют т. н. примитивно рекурсивные функции – Р. ф., получающиеся из исходных функций в результате конечного числа применений одних лишь операторов подстановки и примитивной рекурсии. Они образуют собственную часть класса общерекурсивных функций. В силу известной теоремы Клини о нормальной форме Р. ф. могут быть указаны такие конкретные примитивно рекурсивные функции U от одной переменной и T_n от n + 2 переменных, что для любой Р. ф. j от n переменных и для любых натуральных чисел x₁, . . ., x_n имеет место равенство j(x₁, ..., x_n) @ U(y), где у есть наименьшее из чисел z таких, что T_n(j, x₁, ..., x_n,z) = 0 (здесь j представляет собой т. н. геделев номер функции j – число, которое эффективно строится по системе равенств, задающей функцию j). Из этой теоремы, в частности, вытекает, что для Р. ф. от п переменных может быть построена универсальная Р. ф. от n+1 переменных, т. е. такая Р. ф. Ф_n, что для любой Р. ф. j от n переменных и для любых натуральных чисел x₁, . . ., x_n имеет место условное равенство

j( x₁, . . ., x_n) @ Ф_n(, x₁, . . ., x_n).

  Это – один из центральных результатов общей теории Р. ф.

  Теория Р. ф., являясь частью алгоритмов теории, представляет собой разветвленную математическую дисциплину с собственной проблематикой и с приложениями в др. разделах математики. Понятие «Р. ф.» может быть положено в основу конструктивного определения исходных математических понятий. Широкое применение теория Р. ф. нашла в математической логике. В частности, понятие примитивно рекурсивной функции лежит в основе первоначального доказательства знаменитой теоремы Гёделя о неполноте формальной арифметики, а понятие «Р. ф.» в его полном объёме было использовано С. К. Клини для интерпретации интуиционистской арифметики (исследование это составило целую эпоху в области семантики). Аппарат теории Р. ф. используется также в теории вычислительных машин и программирования.

  Исследования показали, что все известные уточнения общего понятия алгоритма, в том числе Р. ф., взаимно моделируют друг друга и, следовательно, ведут к одному и тому же понятию вычислимой функции. Это обстоятельство служит серьёзным доводом в пользу тезиса Чёрча.

  Лит.: Клини С. К., Введение в математику. пер. с англ., М., 1957; Успенский В. А., Лекции о вычислимых функциях, М., 1960; Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; Роджерс Х., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972.

  Н. М. Нагорный.

Релаксанты

Релакса'нты (от лат. relaxo – уменьшаю, ослабляю), миорелаксанты, вещества, уменьшающие тонус скелетной мускулатуры, что проявляется снижением двигательной активности вплоть до полного обездвижения. В зависимости от механизма действия Р. подразделяют на курареподобные средства, нарушающие передачу возбуждения через нервно-мышечный синапс, т. е. с двигательных нервов на мышцу (такие Р. используют в анестезиологии для полного расслабления мускулатуры), и вещества центрального действия, влияющие на центральные нервные образования, участвующие в регуляции мышечного тонуса. Р. центрального действия (мепротан, мидокалм и др.) применяют в неврологической практике при спинномозговых и церебральных спастических параличах,паркинсонизме и т. д. См. также Кураре,Курарины,Нейролептические средства,Релаксация.

Релаксации время

Релакса'ции вре'мя, время установления полного или частичного термодинамического равновесия в системе. См. Релаксация.

Релаксационные колебания

Релаксацио'нные колеба'ния, автоколебания, возникающие в системах, в которых существенную роль играют диссипативные силы: внешнее или внутреннее трение – в механических системах, активное сопротивление – в электрических. Рассеяние энергии, обусловленное этими силами, приводит к тому, что энергия, накопленная в одном из двух (или более) накопителей, входящих в состав автоколебательной системы, не переходит полностью к другому накопителю (как в системах, совершающих гармонические колебания), а рассеивается в системе, превращаясь в тепло. Р. к., как и всякие автоколебания, могут происходить только в нелинейных системах, поэтому рассмотрение Р. к. требует применения нелинейной теории колебаний. Релаксационные автоколебательной системы характерны тем, что при отключении источника энергии в них невозможны колебательные движения. Если в системе преимущественное значение имеет один из энергоёмких параметров (например, ёмкость при пренебрежимо малой индуктивности или упругость при пренебрежимо малой массе), то каждый период Р. к. может быть разделён на несколько резко разграниченных этапов, соответствующих медленным и быстрым изменениям состояния системы, в которой происходят Р. к., что позволяет рассматривать Р. к. в подобных вырожденных системах как разрывные колебания.

  Простейшим примером механической системы, создающей Р. к., может служить колодка К, насаженная с трением на вращающийся вал В и укрепленная при помощи пружин (рис. 1). При вращении вала колодка вследствие трения увлекается валом до тех пор, пока момент упругих сил пружин не станет равным максимально возможному моменту сил трения. Тогда колодка начинает скользить по валу в обратном направлении, при этом относительная скорость колодки и вала увеличивается, сила трения падает, и колодка возвращается обратно. Но при приближении колодки к положению равновесия упругая сила пружины уменьшается, вал снова захватывает колодку и увлекает её за собой, дальше процесс повторяется (рис. 2).

  С механическими Р. к. приходится встречаться в различных механизмах (например, тормозные колодки), в которых трение достаточно велико и вместе с тем величина трения падает (по крайней мере в некоторой области) при увеличении относительной скорости движения поверхностей, между которыми возникают силы трения.

  Простейший пример электрических Р. к. – колебания, возникающие при определённых условиях в схеме с газоразрядной лампой (рис. 3), которая обладает свойством зажигаться при некотором напряжении U₃ и гаснуть при более низком напряжении U_m. В этой схеме периодически осуществляется зарядка конденсатора С от источника тока Е через сопротивление R до напряжения зажигания лампы, после чего лампа зажигается, и конденсатор быстро разряжается через лампу до напряжения гашения лампы. В этот момент лампа гаснет и процесс начинается вновь. В течение каждого периода этих Р. к. происходит два медленных изменения силы тока I при заряде и разряде конденсатора и два быстрых – скачкообразных – изменения тока /_c, когда лампа зажигается и гаснет (рис. 4).

  Упрощённое рассмотрение механизма возникновения Р. к. основано на пренебрежении параметрами системы, влияющими на характер быстрых движений. Методы нелинейной теории колебаний позволяют исследовать не только медленные, но и быстрые движения, не пренебрегая параметрами, от которых характер быстрых движений существенно зависит, и не прибегая к специальным постулатам о характере быстрых движений. В зависимости от свойств системы возможно большое разнообразие форм релаксационных автоколебаний от близких к гармоническим до скачкообразных и импульсных.

  Электрические Р. к. широко применяются в измерительной технике, телеуправлении, автоматике и др. разделах электроники. Для создания Р. к. существуют разнообразные схемы генераторов релаксационных колебаний, например блокинг-генераторы, мультивибраторы, RC-генераторы и т. д.

  Лит.: Андронов А. А., Витт А. А., Хайкин С. Э., Теория колебаний, 2 изд., М., 1959, гл. IV, IX; Меерович Л. А., 3еличенко Л. Г., Импульсная техника, 2 изд., М., 1954, гл. XIV, XV; Капчинский И. М., Методы теории колебаний в радиотехнике, М. – Л., 1954.

Рис. 3. Электрическая релаксационная система.

Рис. 1. Механическая релаксационная система.

Рис. 2. График изменений угла j поворота колодки со временем t.

Рис. 4. График изменения силы тока I со временем t в контуре с газоразрядной лампой.

Релаксационные явления в полимерах

Релаксацио'нные явле'ния в полиме'рах, изменения физических свойств полимерных тел, обусловленные процессами установления статистического равновесия. Эти явления подобны релаксациив любых других телах, но из-за длинноцепочечного строения макромолекул в полимерах они протекают в широких временных диапазонах, что делает их легко доступными для наблюдения.

  Р. я. в п. обусловлены перестройкой структуры, которая осуществляется тепловыми движениями цепей, движениями отдельных атомных групп в цепи, а также элементов надмолекулярной структуры. Исследование Р. я. в п. широко используется как важный физико-химический метод изучения структуры полимеров.

  Лит.: Каргин В. А., Слонимский Г. Л., Краткие очерки по физико-химии полимеров, 2 изд., М., 1967: Переходы и релаксационные явления в полимерах, пер. с англ., М., 1968.

Релаксационный генератор

Релаксацио'нный генера'тор, релаксатор, генератор электрических негармонических колебаний, обычно обладающих широким спектром (см. Генерирование электрических колебаний). Основные элементы Р. г. – реактивный накопитель энергии (ёмкостный или индуктивный) и нелинейный элемент с вольтамперной характеристикой, имеющей падающий участок, благодаря чему такой элемент приобретает гистерезисные свойства (см. Гистерезис). Наличие этих свойств обусловливает чередование двух основных стадий работы Р. г. – стадии запасания в накопителе энергии от питающего источника постоянного тока (напряжения) и стадии релаксации, когда накопитель освобождается от значительной части энергии (она рассеивается в нелинейном элементе др. активных элементах Р. г., например резисторах). Соизмеримость максимально запасённой и теряемой накопителем энергии – характерная отличительная особенность Р. г. В качестве нелинейного элемента в Р. г. применяют газоразрядные приборы (тиратроны, неоновые лампы), электронные лампы, транзисторы, тиристоры, туннельные диоды и др. либо усилительный каскад (транзисторный, ламповый) с положительной обратной связью.

  К числу наиболее распространённых Р. г. относятся мультивибраторы,блокинг-генераторы, генераторы пилообразного напряжения (в частности, фантастроны). Для Р. г. типичен автоколебательный режим работы, при котором период релаксационных колебаний определяется параметрами Р. г. Из-за невысокой стабильности частоты (а следовательно, и периода) колебаний Р. г. такие генераторы часто синхронизируют от внешнего источника стабильных колебаний. Используется также ждущий режим работы, при котором Р. г. включается в результате воздействия сигнала извне. Р. г. применяют в устройствах импульсной техники, в частности в телевизионной, радиолокационной и радиоизмерительной аппаратуре.

  Лит.: Андронов А. А., Витт А. А., Хайкин С. Э., Теория колебаний, 2 изд., М., 1959; Ицхоки Я. С., Овчинников Н. И., Импульсные и цифровые устройства, М., 1972.

  Я. С. Ицхоки.

Релаксация магнитная

Релакса'ция магни'тная, один из этапов релаксации — процесс установления термодинамического равновесия в среде с участием системы спиновых магнитных моментов атомов и молекул среды. Т. к. взаимодействие между спинами (магнитными моментами спинов) во многих случаях значительно сильнее, чем др. взаимодействия, в которых участвуют спины (например, сильнее взаимодействия спинов с фононами кристалла), то часто равновесие в самой системе спинов наступает быстрее, чем в среде в целом (для остальных внутренних степеней свободы). Поэтому Р. м. идёт поэтапно, причём, как правило, последний (наиболее длительный) этап Р. м. соответствует установлению равновесия между спинами и др. степенями свободы, например между системой спинов и квантами колебаний кристаллической решётки твёрдого тела – фононами. Каждый этап Р. м. описывается своим временем релаксации (например, в кристаллах вводят времена спин-спиновой и спин-решёточной релаксации).

  В средах, обладающих магнитной структурой (в ферро– и антиферромагнетиках), Р. м. происходит благодаря столкновению спиновых волн (магнонов) друг с другом, а также с фононами, с дислокациями, с атомами примесей и др. дефектами в кристаллах.

  В твёрдых телах Р. м. существенно зависит от их структуры: характера кристаллической решётки (моно– или поликристалл), наличия примесей, дислокаций, доменной структуры (см. Домены) и т. п. Как правило, уменьшение числа дефектов в кристалле и понижение его температуры ведут к увеличению времени Р. м.

  Р. м. ядерных спинов (магнитных моментов ядер) обладает своей спецификой, обусловленной особенно малым взаимодействием ядерных спинов с др. степенями свободы среды.

  Р. м. проявляется в процессах намагничивания и перемагничивания (см. Магнитная вязкость), определяет ширину линий ядерного магнитного резонанса, электронного парамагнитного резонанса, ферро– и антиферромагнитного резонансов. Свойства ферро– и антиферромагнетиков в высокочастотных электромагнитных полях существенно зависят от Р. м. В ряде случаев Р. м. накладывает ограничения на условия применения в технике магнитных тонких плёнок, на быстродействие магнитных элементов запоминающих устройств ЭВМ и др. Времена Р. м. относятся к тем параметрам твёрдого тела, которые сравнительно легко изменяются технологической обработкой (легированием,закалкой и т.п.).

  Лит. см. при статьях Релаксация,Магнитный резонанс.

  М. И. Каганов.

Назад к карточке книги "Большая Советская Энциклопедия (РЕ)"