Решение 23 заданий с множествами и подмножествами (Вариант 31), страница 4

s(x) =

s(x) =

f(x,1 ) =

………………………………….

f(x,y+1) = s(x) =f(x,x) - примитивно рекурсивна.

(д) lh(x) – число простых делителей числа x, где lh(0) = 0;

Т(х)=

 - примитивно рекурсивна

(е) p(x) – число простых чисел, не превосходящих x;

Примитивная рекурсия

20. Доказать, что если функции gⁿ⁺¹ и  hⁿ⁺¹ частично рекурсивны, то следующая функция частично рекурсивна:

my [g(x₁, x₂, …, x_n, y) ≤ h(x₁, x₂, …, x_n, y)];

my [ h(x₁, x₂, …, x_n, y) -g(x₁, x₂, …, x_n, y)≥0];

Разность 2^х частично рекурсивных функций - частично рекурсивная функция . Частично рекурсивная функция конечное применение операторов ($,R,µy) и мы применяем еще раз оператор  my ® осталось так же конечное применение операторов ($,R,µy)  ® my [g(x₁, x₂, …, x_n, y) ≤ h(x₁, x₂, …, x_n, y)]; функция частично рекурсивна.

21. Написать спецификацию автомата «А». Описать автомат «А». Выполнить процедуру проверки соответствия спецификации. Описать автомат «Б». Описать параллельное взаимодействие описанных автоматов.

А = «Трактор»

Б = «Тракторист»

Тракторист : { пить , курить }

Общие         : { завести , поездка , остановка}

Трактор       : { шуметь , дворники}

Тракторист  = курить ® завести ® поездка ® пить ® остановка ® СТОП _{тракторист}

Трактор = пуск ® шуметь ® поездка ® дворники ® остановка ® СТОП _{трактор}

Тракторист || Трактор = курить ® завести ® шуметь ® поездка ® пить ® дворники ®

                                                                                            остановка ® СТОП _{тракторист || трактор}

                                           курить ® завести ® шуметь ® поездка ®  дворники ® пить ®

                                                                                            остановка ® СТОП _{тракторист || трактор}

 prot ( тракторист) :{

                                    < >, < курить > , < курить ® завести > , < курить ® завести ® поездка > ,

                                    < курить ® завести ® поездка ® пить > ,                                  

                                    < курить ® завести ® поездка ® пить ® остановка >

                                                                                                                                          }

 prot ( трактор) :{

                                    < >, < завести > , < завести ® шуметь > , < завести ® шуметь ® поездка > ,

                                    < завести ® шуметь ® поездка ® дворники > ,

                                    < завести ® шуметь ® поездка ® дворники ® остановка >

                                                                                                                                          }

  sp ( тракторист) :{

                                    < >, < курить > , < курить ® завести > , < курить ® завести ® поездка > ,

                                    < курить ® завести ® поездка ® пить > ,

                                    < курить ® завести ® поездка ® пить ® остановка >

                                                                                                                                          }   

 sp ( тракторист) = prot ( тракторист)

 sp  ( трактор) :{

                                    < >, < завести > , < завести ® шуметь > , < завести ® шуметь ® поездка > ,

                                    < завести ® шуметь ® поездка ® дворники > ,

                                    < завести ® шуметь ® поездка ® дворники ® остановка >