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

Определим на семействе всех частичных функций операторы S , R , М, которые сохраняют вычислимость функций. Пусть n , k w , f —( n +1)-местная частичная функция, g o ,..., g n — k - местные частичные функции.

Определим k -местную частичную функцию h следующим образом: h ( m 1 ,.., m k ) не определено, если хотя бы одна из частичных функций g o ,..., g n не определена на _ m 1 ,.., m k > и если все g o ,..., g n определены на m 1 ,.., m k >, то h ( m 1 ,.., m k )= f ( g o ( m 1 ,.., m k )…, g n ( m 1 ,.., m k )). Будем говорить, что h получена регулярной суперпозицией из f , g 0 , …, g n и обозначать это следующим образом h = S k , n ( f , g 0 , …, g n ). Оператор (регулярной суперпозиции)- S k , n является всюду определенным отображением из n +1 X n +1 k в k и сохраняет вычислимость, т.е. если частичные функции f n +1; g 0 , …, g n k вычислимы, то и частичная функция S k , n ( f , g 0 , …, g n ) вычислима.

Верхние индексы, у оператора S будут опускаться и вместо S ( f , g 0 , …, g n ) будет, как правило, использоваться более привычное, но менее точное обозначение f ( g 0 ,..., g n ). Пусть n w , f n , g n +2 . Определим по f и g ( n + 1) - местную частичную функцию h так, что для любых m 1 ,.., m n w h( m 1 ,.., m n ,0)=f( m 1 ,.., m n ); h ( m 1 ,.., m n , k +1) не определено, если h ( m 1 ,.., m n , k ) не определено и h ( m 1 ,.., m n , k +1) = g ( m 1 ,.., m n , k ), h ( m 1 ,.., m n , k )), если h ( m 1 ,.., m n , k ) определено.

Очевидно, что h однозначно определена по f и g и вычислима, если вычислимы / и указанное определение h по / и g задает оператор h = R n +1 : n X n +2 ® n +1 который назовем оператором примитивной рекурсии. Про h =функцию h = R n +1 ( f , g ) будем говорить, что она получила примитивной рекурсией из функций f и g . Верхний индекс у оператора R n +1 будем опускать. Пусть n w , f n +1 . Определим по f такую n -местную частичную функцию g , что для любых k , m 1 ,.., m n w тогда и только тогда, когда f ( m 1 ,.., m n ,0)=0 и k =0 или k >0 и f ( m 1 ,.., m n ,0) определены и не равны нулю, а f ( m 1 ,.., m n , k )=0. Ясно, что такая функция д существует и однозначно определена по f ; кроме того, если f — вычислимая функция, то из определения g видно, как вычислять g . Таким образом, задан оператор M n — оператор минимизации — из n +1 в n если g = M n ( f ) то будем говорить, что g получена минимизацией из f . Базисными функциями называются функции о, s , I n m (1 m n ) где о — одноместная функция, которая па любом n принимает значение 0, s — одноместная функция, принимающая на числе n значение n +1, a I n m — n - местная функция, принимающая на наборе ( k 1 ,…, k n ) значение k m . Очевидно, что базисные функции вычислимы.

Определение.

Частичная функция f называется частично рекурсивной, если существует такая конечная последовательность частичных функций g 0 , …, g k что g k = f и каждая g i , i k либо базисная, либо получается из некоторых предыдущих регулярной суперпозицией, примитивной рекурсией или минимизацией. Эта последовательность g 0 , …, g k называется определяющей последовательностью для f . Если для всюду определенной частично рекурсивной функции f существует определяющая последовательность, состоящая только из всюду определенных функций, то f называется рекурсивной. В следующем параграфе будет доказано, что любая всюду определенная частично рекурсивная функция является рекурсивной. Из данного определения и приведенных выше замечаний о сохранении вычислимости операторами S , R , М легко следует, что всякая частично рекурсивная функция является вычислимой.

Обратное утверждение носит название тезиса Чёрча: любая вычислимая частичная частично рекурсивна.

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

Теорема 2 Класс частично рекурсивных' функций совпадает с классом функций, вычислимых, по Тьюрингу. Таким образом, тезис Тьюринга эквивалентен .тезису Чёрча. Пусть k , n w а — некоторое отображение множества {1 ,..., k }в множество {1,..., n } f — k -местная частичная функция. Будем говорить, что n -местная частичная функция g получена из f подстановкой ее, если для любых m 1 ,.., m n w имеет место соотношение: g(m 1 ,.., m n) )=(m a1 ,..,m ak ). Будем использовать в этом случае обозначение g = f a Предложение 1. Если f — частично рекурсивная функция и g получена из f подстановкой а, то g частично рекурсивна.

Доказательство 1. Легко проверить, что если g = f a , то g=S n,k-1 (f, I n a1 ,…, I n ak ) Предложение 2. Следующие функции рекурсивны: 1)Пулъместные функции n, n w ; 2)двухместная функция сложения +; 3)двухместная функция умножения • ; 4)двухместная функция усеченной разности •, определенная следующим образом: ___ 5)одноместные функции sg и sg , определенные следующим образом: двухместная функция идентификации 6, определенная следующим образом: Доказательство 2. Покажем рекурсивность нуль - местной функции { , n }} индукцией по n . Функция { , 0}} равна M (0). Если функция { , n }} рекурсивна, то рекурсивна функция S { , n }} = { , n +1}} . Так как n +0 = n и n +( m +1) то функция + равна R ( I 1 1 S ( I 3 3 )). Из равенств n •0=0 и n •( m +1) = n • m + n следует, что функция равна R (0, I 1 1 + I 3 3 ) Для того чтобы показать рекурсивность — усеченной разности рассмотрим одноместную функцию -- 1 определённую так: Она равна R (0, I 2 1 ) поэтому рекурсивна. Так как n — ( m +1)=( n — m ) — 1, т о функция -- равна R ( I 1 1 , I 3 3 – 1) следовательно, также является рекурсивной.

Рекурсивность функций следует из равенств sg = R ( o , s (0( I 2 1 ))) и sg = R (1,0( I 2 1 )). Пусть a :{1,2} ® {1,2}такого что a (1=2), a (2=1), a f — функция полученная из функции -- подстановкой а. Тогда для функции справедливо равенство = S ( sg ), S (+,--, f )). Из рекурсивности функций sg — и предложения получаем, что функция идентификации является рекурсивной. Для задания, рекурсивных функций и изучения их свойств удобнопользоваться специальным формальным языком R . Пусть V ={ U i I i w } — множество переменных, элементы лоторого будем обозначать буквами х, у, z , w , и, возможно с индексами. Пусть ( R,F,M) — некоторая конечная сигнатура такая, что F F 0 ={0, s ,+, •) где 0 символ нульместной функции, s — символ одноместной функции, +, • — символы двухместных функций; R R 0 ={ Определение выражений, (синтаксис) языка R будет зависеть еще и от семантики этого языка.

Поэтому определение синтаксиса и семантики будет вестись, одновременно, но прежде всего зададимся фиксированной алгебраической системой W сигнатуры с основным множеством w и такой, что значения символов сигнатуры 0 = ( R 0 , F 0 , M n ) совпадают с функциями и предикатом, обозначенными этими символами ранее (например, символу • соответствует операция умножения натуральных чисел). Итак, будем одновременной индукцией определять понятие - терма, -формулы (более точно было бы говорить об W термах и W - формулах), множества свободных переменных FV ( t ) и FV ( j ) - терма t и -формулы j соответственно, натуральное число t [ h ] и истин ностное значение j [ h ] {и,л} для всякой интерпретации ® w где Х V , FV ( t ) FV ( j ) X ; а) символ 0 является -термом, FV (0= ) и 0[ h =0]; б) переменная х У является -термом, FV ( x )={ x }, x [ h ]= h ( x ); в) если f F — n -местный функциональный символ, t 1 ,…,t n - термы; то - терм f(f 1 ,..., t n ); FV ( f ( t 1 ,…, t n ))= FV ( t 1 ) U … U FV ( t n ); F ( t 1 ,…,t n ) [ h ]= f W ( t 1 [ h ],…, t n [ h ]) здесь f W - n местная операция Алгебраической системы W соответствующая сигнатурному символу f ; г) если ( Q — n -местный предикатный символ из Ra t 1 ,…, t n -термы, то Q ( t 1 ,…, t n ) -формула, FV ( Q ( t 1 ,…, t n ))= FV ( t 1 ) U … U FV ( t n ) ; Q( t 1 ,…, t n ) [ h ] здесь Q W — n -местный предикат, соответствующий в алгебраической системе W предикатному символу Q ; д)Если t 1 ,…, t 2 -термы, t 1 t 2 -формула, FV ( t 1 t 2 ) = FV ( t 1 ) U FV ( t 2 ), ( t 1 t 2 ) [ h ] = и t 1 [ h ]= t 2 [ h ]; е)Если j и -формула то j ,( j , t , ) для t { , , ® } - формулы, fV ( j ) = FV ( j ), FV ( j , t , ) = FV ( j ) U FV ( ) и ( j ) [ h ] = ( j [ h ] ) где , , ® операции определены на множестве {и,л}таблицей (1) c заменой «о» на «л» и «1» на «и» ж)П усть j -формула, x V и для любой интерпретации h 1 : X ® w для которой x X и FV ( j ) X U{ x } c существует такое же n , что j [ h ] = и для h = h 1 U { x , n }}; тогда m x j -терм, FV ( m x j ) = FV ( j ) { x }и ( m x j ) [ h ] - наименьшее n 0 w для которого j [ h ’ ]= и где h ’=( h { x , h x}}) U{ x , n 0 }} Индукцией по построению -терма ( -формулы) Q легко устанавливается, что для любых интерпретаций h 0 : x 0 ® w , h 1 : x 1 ® w с таких, что FV ( Q ) x 0 x 1 и для всех x FV ( Q ) h 0 ( x )= h 1 ( x ) и для всех выполняется равенство Q [ h 0 ]= Q [ h 1 ]. Как обычно, в место +( t 1 , t 2 ) •( t 1 , t 2 )) будем писать ( t 1 + t 2 )(( t 1 • t 2 )) и ( t 1 t 2 ). Вместо t 1 , t 2 ). Кроме того, будем пользоваться обычными сокращениями для термов и формул, принятыми в арифметике и исчислении высказываний (например, вместо ( x +(( z • z )+( x • y ))) и (( j ) ® j будем писать соответственно x + z 2 + xy и ( j ) ® j ). Для -формулы j и интерпретации h ; x ® w FV ( j ) x , часто вместо « j [ h ] = и» будем писать « j [ h ] истинно» или просто « j [ h ] ». А вместо « j [ h ] = » будем писать « j [ h ] ложно» или « j [ h ]». Пусть Q — -терм или ( - формула). Вхождение переменной x в Q называется свободным, если оно не находится в пол слове вида m x j являющемся -термом. Если вхождение переменной в не является свободным, то оно называется связанным. Легко проверить, что множество FV( Q ) состоит в точности из переменных, имеющих свободные вхождениям в Q . Пусть в Q -терм ( -формула), x 1 ,…,x n V - различные переменные, t 1 ,… t n -терм такие, что для любого i {1,…, n }и любого y V ( t 1 ) ни одно свободное вхождение в Q переменной X i не содержится в терме вида являющемся m y j под словом Q . будет обозначать результат замены всех свободных вхождений переменных х 1 ,..,х n на -термы - t 1 ,..., t n соответственно. Ю. Л. Ершов, Е. Л. Палютиа Индукцией по построению -терма и -формулы без труда устанавливается следующее.

Предложение 3. Если Q -терм ( -формула ) х 1 ,..,х n V — различные переменные, t 1 ,..., t n — -термы такие, что для Q , х 1 ,..,х n , t 1 ,..., t n выполнены сформулированные выше условия, то 1) Q 1 = является -т ep м ( -формулой), в такой для любой интерпретации h : x ® w . В такой, что ( FV ( Q ){ х 1 ,..,х n }) U … U FV ( t n ) x выполняется равенство Q 1 [ h ]= Q [ h ] где h ’ = { y , h ( y )>| y F V ( Q ) }. Про - терм ( -формулу) будем говорить, что Q получен из Q подстановкой - термов t 1 ,..., t n вместо переменных х 1 ,..,х n . К сожалению, условия для возможности подстановки -термов вместо переменных не всегда выполнены. Чтобы всегда иметь возможность для подстановки, введем следующие понятия. Будем говорить, что -терм ( - формула) Q получается из -терма ( -формулы) Q , заменой связанной переменной, если Q получается из заменой вхождения -терма m x j на m y ( j ) x y где y FV ( j ). -термы ( -формулы) Q и Q 1 называются конгруэнтными, если существует такая последовательность Q 0 ,…, Q n что Q o = Q 1 ; Q o = Q ’; Q I +1 , I n , получается из Q заменой связанной переменной.

Очевидно, что отношение конгруэнтности является эквивалентностью на множестве -термов и - формул.

Предложение 4. Если Q и Q ' — конгруэнтные -тёрмы или -формулы, то FV ( Q = FV ( Q ’)) для любой интерпретации h : FV ( Q ) ® w имеем Q [ h ]= Q ’[ h ]. Доказательство 3. Индукцией по длине Q легко показать, что если Q 1 получается из Q заменой связан ной переменной, то утверждение предложения истинно. Далее индукция по длине последовательности Q 0 ,…, Q n из предыдущего определения.

Отметим, что для любого -терма ( -формулы) Q , любого набора попарно различных переменных x 1 ,…,х n любых -термов t 1 ,..., t n существует - терм ( -формула) Q ' такой (такая), что Q ' конгруэнтен (конгруэнтна) Q и для Q ' выполнены условия для подстановки пользуясь этим свойством и предложением 4, будем впредь использовать запись , не заботясь о выполнении условий на связанные переменные считая, что если эти условия не выполнены, то есть для -терма ( -формулы) Q ', конгруэнтного (конгруэнтной) Q в, причём для Q ' все условия для подстановки уже выполнены.

Напомним, что подмножество X A n называется n -местным предикатом на А. В дальнейшем под предикатами будем понимать предикаты на w . Если n -местный предикат, то n -местная функция n x определенная следующим образом: для любых m 1 ,…, m n w случаев, называется представляющей функцией для X . Наряду с представляющей функцией p x предиката X часто используют характеристическую функцию X х предиката X , которая связана с функцией p x соотношением X x = sg ( p x ) п редикат X называется рекурсивным, если его пред уставляющая функция p x рекурсивна.

Алгебраическая система W называется рекурсивной, если все функции и предикаты, соответствующие символам сигнатуры , являются рекурсивными. В дальнейшем, говоря о -формулах и - термах (определение которых зависит от фиксированной алгебраической системы W , будем всегда предполагать, что W — рекурсивная алгебраическая система.

Заметим, что предикаты , являются рекурсивными, так как представляющей функцией для является функция идентификации а представляющей функцией для sg ( S ( I 2 1 ) – I 2 2 ). С каждым -термом ( -формулой) можно связать семейство функций (предикатов), которые реализуются этим -термом ( - формулой). Для обозначения этих функций (предикатов) будем использовать расширение языка, R добавив новую пару [,] символов квадратных, скобок.

Перейдем к точным, определениям. Если t - -терм для i ¹ j то через t [ x 1 ,…,х n ] будем обозначать n - местную функцию, принимающую на n -ке m 1 ,…, m n > значение t [ h ] , где h ={ x 1 , m 1 > I =1,…, n }. Если j - -формулой и FV ( j ) { x 1 ,…,х n } , x 1 ¹ x j , для i ¹ j , то через будем обозначать предикат { m 1 ,…, m n > j [ h ]= { x i , m i > I =1,…, h }}. Заметим, что один и тот же -герм + реализует много функций, например, если FV ( t ) {x,y}то [x,y], +[y,x] и [x,y, z ] , вообще говоря, различные функции символ [ x 1 ,…,х n ] играет роль, аналогичную кванторам, он связывает x 1 ,…,х n так, например, если FV ( t ) { x 1 ,…,х n }и y 1 ,…,y n попарно различные переменные, то имеет место равенство. t[ x 1 ,…, х n ] = [ y 1 ,…,y n ]. Заключение В этой курсовой было определено понятие рекурсивного предиката, как предиката, представляющая функция которого является рекурсивной. Таким образом, рекурсивные предикаты это в точности такие предикаты R W , для которых эффективно решается проблема вхождения, т. е. проблема определения по заданной n -ке чисел m 1 ,..., m n >. Так же рассмотрели частично рекурсивные функции совпадающие с классом функций, вычислимых, по Тьюрингу. В этом реферате мы привели способ уточнения понятия вычислимой функции который можно назвать алгебраическим, так как определяемый класс функций будет порождаться из некоторых простейших функций с помощью некоторых операций. Под частичной функцией мы понимаем f : X ® w , где Х w n для некоторого n х.