| 8406202 9216 1210 912 1лгоритмы, принято называть вычислимыми. Вычислимые функции играют в математике важную роль. Вместе с тем, если понятию алгоритма здесь не будет придан точный смысл, то и само понятие вычислимой функции окажется неск. расплывчатым. Р. ф. уже в силу самого характера своего определения оказываются вычислимыми. В известном смысле верно и обратное: имеются серьёзные основания считать, что математическое по своему характеру понятие рекурсивности является точным эквивалентом неск. расплывчатого понятия вычислимости. Предложение считать понятие вычислимости совпадающим по объёму с понятием рекурсивности известно в теории Р. ф. под названием тезиса Чёрча по имени амер. математика А. Чёрча, впервые (в 30-х гг. 20 в.) сформулировавшего и обосновавшего это предложение. Принятие тезиса Чёрча позволяет придать понятию вычислимой арифметич. функции точный математич. смысл и подвергнуть это понятие изучению при помощи точных методов.
Р. ф. являются частичными функциями, т. е. функциями, не обязательно всюду определёнными. Чтобы подчеркнуть это обстоятельство, часто в качестве синонима используют термин "частично рекурсивные функции". Р. ф., определённые при любых значениях аргументов, наз. общерекурсивными функциями.
Определению Р. ф. может быть придана следующая форма. Фиксируется небольшое число чрезвычайно простых исходных функций, вычислимых в упомянутом выше интуитивном смысле (функция, тождественно равная нулю, функция прибавления единицы и функции, выделяющие из системы натуральных чисел член с данным номером); фиксируется небольшое число операций над функциями, переводящих вычислимые функции снова в вычислимые (операторы подстановки, примитивной рекурсии и минимизации). Тогда Р. ф. определяются как такие функции, к-рые можно получить из исходных в результате конечного числа применений упомянутых выше операций.
Оператор подстановки сопоставляет функции f от п переменных и функциям g1, . . ., gnот т переменных функцию h от m переменных такую, что для любых натуральных чисел
x1, . . ., xm h(x1, ..., xm) ~ f(g1(x1, ..., xm), ..., gm(x1, ..., xm))
(здесь и ниже условное равенство ~; означает, что оба выражения, связываемые им, осмыслены одновременно и в случае осмысленности имеют одно и то же значение).
Оператор примитивной рекурсии сопоставляет функциям f от n переменных и g от n + 2 переменных функцию h от n +1 переменных такую, что для любых натуральных чисел
x1, . . ., xп, y h(x1, ..., хn, 0) ~ f(x1, ..., хn), h(x1, ..., хn, у + 1) ~ g(x1, ..., хn, у, h(x1, ..., хn, y)).
Оператор минимизации сопоставляет функции f от п переменных функцию h от п переменных такую, что для любых натуральных чисел x1, ..., хn
h(x1, ..., хn) =: f(x1, ..., хn-1, y),
где у таково, что f(x1, ..., хn-1, 0), ... . . ., f(x1, ..., хn-1, y-1) определены и отличны от хn, a f(x1, ..., хn-1, у) определена и равна хп; если же у с указанными свойствами не существует, то значение h(x1, ..., хn) считается не определённым.
Важную роль в теории Р. ф. играют т. н. примитивно рекурсивные функции - Р. ф., получающиеся из исходных функций в результате конечного числа применений одних лишь операторов подстановки и примитивной рекурсии. Они образуют собств. часть класса общерскурсивных функций. В силу известной теоремы Клини о нормальной форме Р. ф. могут быть указаны такие конкретные примитивно рекурсивные функции U от одной переменной и Тn от n + 2 переменных, что для любой Р. ф. ф от и переменных и для любых натуральных чисел x1, . . ., хn имеет место равенство fp(x1, . . ., xn)~=U(y), где у есть наименьшее из чисел z таких, что
Тn (ф, x1, . . ., Хп, z) = 0 (здесь ф представляет собой т. н. гёделев номер функции ф - число, к-рое эффективно строится по системе равенств, задающей функцию ф). Из этой теоремы, в частности, вытекает, что для Р. ф. от и переменных может быть построена универсальная Р. ф. от n + 1 переменных, т. е. такая Р. ф. Фn, что для любой Р. ф. ф от п переменных и для любых натуральных чисел х1, . . ., хn имеет место условное равенство
ф(x1, .... xn) ~ Фn(ф, x1, ..., xn).
Это - один из центральных результатов общей теории Р. ф.
Теория Р. ф., являясь частью алгоритмов теории, представляет собой разветвлённую математич. дисциплину с собств. проблематикой и с приложениями в др. разделах математики. Понятие "Р. ф." может быть положено в основу конструктивного определения исходных математич. понятий. Широкое применение теория Р. ф. нашла в математич. логике. В частности, понятие примитивно рекурсивной функции лежит в основе первоначального доказательства знаменитой теоремы Гёделя о неполноте формальной арифметики, а понятие "Р. ф." в его полном объёме было использовано С. К. Клини для интерпретации интуиционистской арифметики (исследование это составило целую эпоху в области семантики). Аппарат теории Р. ф. используется также в теории вычислит. машин и программирования.
Исследования показали, что все известные уточнения общего понятия алгоритма, в том числе Р. ф., взаимно моделируют друг друга и, следовательно, ведут к одному и тому же понятию вычислимой функции. Это обстоятельство служит серьёзным доводом в пользу тезиса Чёрча.
Лит.: Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; Успенский В. А., Лекции о вычислимых функциях, М., 1960; Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; Роджерс X., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972. Н. М. Нагорный.
РЕЛАКСАНТЫ (от лат. relaxo - уменьшаю, ослабляю), миорелаксанты, вещества, уменьшающие тонус скелетной мускулатуры, что проявляется снижением двигат. активности вплоть до полного обездвижения. В зависимости от механизма действия Р. подразделяют на курареподобные средства, нарушающие передачу возбуждения через нервно-мышечный синапс, т. е. с двигат. нервов на мышцу (такие Р. используют в анестезиологии для полного расслабления мускулатуры), и вещества центр. действия, влияющие на центр. нервные образования, участвующие в регуляции мышечного тонуса. Р. центр. действия (мепротан, мидокалм и др.) применяют в неврологич. практике при спинномозговых и церебральных спастических параличах, паркинсонизме и т. д. См. также Кураре, Курарины, Нейролептические средства, Релаксация.
РЕЛАКСАЦИИ ВРЕМЯ, время установления полного или частичного термодинамич. равновесия в системе. См. Релаксация.
РЕЛАКСАЦИОННЫЕ КОЛЕБАНИЯ, автоколебания, возникающие в системах, в к-рых существенную роль играют диссипативные силы: внеш. или внутр. трение - в механич. системах, активное сопротивление - в электрических. Рассеяние энергии, обусловленное этими силами, приводит к тому, что энергия, накопленная в одном из двух (или более) накопителей, входящих в состав автоколебат. системы, не переходит полностью к другому накопителю (как в системах, совершающих гармонические колебания), а рассеивается в системе, превращаясь в тепло. Р. к., как и всякие автоколебания, могут происходить только в нелинейных системах, поэтому рассмотрение Р. к. требует применения нелинейной теории колебаний. Релаксационные автoколебат. системы характерны тем, что при отключении источника энергии в них невозможны колебат. движения. Если в системе преимущественное значение имеет один из энергоёмких параметров (напр., ёмкость при пренебрежимо малой индуктивности или упругость при пренебрежимо малой массе), то каждый период Р. к. может быть разделён на неск. резко разграниченных этапов, соответствующих медленным и быстрым изменениям состояния системы, в к-рой происходят Р. к., что позволяет рассматривать Р. к. в подобных вырожденных системах как разрывные колебания.
Простейшим примером механич. системы, создающей Р. к,, может служить колодка К, насаженная с трением на вращающийся вал В и укреплённая при помощи пружин (рис. 1). При вращении вала колодка вследствие трения увлекается валом до тех пор, пока момент упругих сил пружин не станет равным максимально возможному моменту сил трения. Тогда колодка начинает скользить по валу в обратном направлении, при этом относит. скорость колодки и вала увеличивается, сила трения падает, и колодка возвращается обратно. Но при приближении колодки к положению равновесия упругая сила пружины уменьшается, вал снова захватывает колодку и увлекает её за собой, дальше процесс повторяется (рис. 2).
С механич. Р. к. приходится встречаться в различных механизмах (напр., тормозные колодки), в к-рых трение достаточно велико и вместе с тем величина трения падает (по крайней мере в нек-рой области) при увеличении относит. скорости движения поверхностей, между к-рыми возникают силы трения.
Простейший пример электрич. Р. к.- колебания, возникающие при определённых условиях в схеме с газоразрядной лампой (рис. 3), к-рая обладает свойством зажигаться при нек-ром напряжении U3 и гаснуть при более низком напряжении Up. В этой схеме периодически осуществляется зарядка конденсатора С от источника тока Е через сопротивление R до напряжения зажигания лампы, после чего лампа зажигается, и конденсатор быстро разряжается через лампу до напряжения гаш |
