Cтраница 2
Цифрами системы являются знаки ( кроме x) t получаемые из /, х и функции следования х 1 подстановкой. [16]
Исследуя, мы обнаруживаем сначала, что каждый индивидуальный класс Fi содержит тождественную функцию и функцию следования. Затем доказываем обратное включение, показывая тем самым, что элементарные функции в точности совпадают с предсказуемо вычислимыми функциями. [17]
Бюхи показал, что множество истинны предложений в LSIS ( относительно стандартной, интерпретации ( N, функция следования) с переменными второго порядка, интерпретируемыми в области конечных множеств) является рекурсивным. Через W51S мы обозначаем множество истинных предложений из LSIS - Мы докажем, что WS1S не является элементарно рекурсивным в смысле Кальмара. В действительности мы утверждаем более сильный результат. [18]
Рассмотрим применение примитивной функции 1 ( succ2), где succ, как и прежде, является функцией следования на множестве целых чисел. [19]
Говорят, что функция однократно рекурсивна ( или примитивно рекурсивна), если она может быть определена из нулевой функции, функции следования и тождественной функции с помощью подстановок и рекурсий. Мы можем также выразить это определение, сказав, что нулевая функция, функция следования и тождественная функция однократно рекурсивны и, далее, что функция однократно рекурсивна, если она определяется подстановкой однократно рекурсивных функций в однократно рекурсивную функцию или определяется однократно рекурсивной схемой с использованием только однократно рекурсивных функций. Таким образом, все функции, определенные до сих пор, однократно рекурсивны, и любая функция, получаемая из них подстановкой, будет однократно рекурсивной. [20]
Дальнейшие замечания: ( 1) Рабин утверждает в своей работе о разрешимости S2S - ( полной) сингулярной теории второго порядка двух функций следования, что его процедура элемен - - тарно рекурсивна. По-видимому, он был введен в заблуждение тем фактом, что каждый шаг элиминации кванторов в его доказательстве элементарен, и тем, что заключительная проверка, допускает ли автомат на дереве непустое множество, также является элементарной относительно размера автомата. [21]
Точнее, эта схема определяет f ( n, а) примитивной рекурсией, исходя из функций а и р В качестве исходных примитивно рекурсивных функций мы берем функцию следования S ( x) t тождественную функцию / (), явно определяемую равенством 1 ( х) х, и нулевую функцию Z ( x), определяемую равенством Z ( x) Q. Говорят, что функция является примитивно рекурсивной, если она исходная или определяется с помощью подстановки или примитивной рекурсии из уже определенных примитивно рекурсивных функций. [22]
Мы описали два процесса - подстановку и рекурсию, с помощью которых можно определять новые функции из введенных ранее, и показали, как строятся see рекурсивные функции из нулевой функции и функции следования. Теперь мы переходим от построения функций к доказательствам равенств. Рассматриваемые Е1ами равенства выражают тот факт, что некоторые функциональные выражения можно подставлять вместо других, например, равенство х у у х указывает, что х 4 - у можно подставить вместо у х, и наоборот. [23]
Под арифметикой будем понимать теорию с языком L и множеством теорем, совпадающим с множеством предложений языка L, истинных в стандартной интерпретации М, областью которой является множество натуральных чисел и которая приписывает символам 0, , , нуль, функцию следования, сложение и умножение соответственно. [24]
Это и следующие упражнения оказываются слишком длинными и утомительными, если в них выписывать полные доказательства. Теория одной функции следования задается аксиомами ( 1), ( 2) и ( 7Ф) из примера 1.4.11 в языке X S, 0, С помощью элиминации кванторов докажите полноту этой теории. [25]
В других случаях полезен индуктивный способ задания, особенно для Л - источников. Индуктивный способ состоит в задании начального состояния q0 и функции следования некоторым правилом. При этом множество Q состояний определяется как множество всех состояний, достижимых из начального, а заключительные состояния выделяются из Q некоторым свойством. [26]
Очевидно, что функция следования вычисляется на машине Тьюрин-га, использующей ровно на одну ячейку больше, чем необходимо для записи входа. Далее, сочленение J) тоже принадлежит F а сложение определяется из функции следования посредством рекурсии, ограниченной сочленением. [27]
Говорят, что функция однократно рекурсивна ( или примитивно рекурсивна), если она может быть определена из нулевой функции, функции следования и тождественной функции с помощью подстановок и рекурсий. Мы можем также выразить это определение, сказав, что нулевая функция, функция следования и тождественная функция однократно рекурсивны и, далее, что функция однократно рекурсивна, если она определяется подстановкой однократно рекурсивных функций в однократно рекурсивную функцию или определяется однократно рекурсивной схемой с использованием только однократно рекурсивных функций. Таким образом, все функции, определенные до сих пор, однократно рекурсивны, и любая функция, получаемая из них подстановкой, будет однократно рекурсивной. [28]
Как и при подходе 2, при подходе 3 к разработке плана общей теории относительности мы прежде всего задаем на замкнутой пространственноподобной гиперповерхности значения Wgik и ( d / dxQ) Wgik. Точно так же, как и при подходе 2, должны быть, кроме того, заданы плотность энергии и ее поток. Найдя функции следования и сдвига, мы уже поступаем в дальнейшем точно так же, как при подходе 2: 1) вычисляем внешнюю кривизну Kik 2) вычисляем полевой момент яг Л; 3) с помощью всех десяти уравнений Эйнштейна определяем четырехмерную геометрию в прошлом и будущем. [29]
Чтобы понять, как измеряется волатильность, мы изучали развитие цены определенной акции изо дня в день. Было показано, что волатильность может рассматриваться как функция следования ежедневным ценовым изменениям. Нас не интересовало, куда в конце концов, двигалась цена акции - нам было интересно, как она двигалась. [30]