Математическая логика и теория алгоритмов. Сергиевская И.М. - 45 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

Составители: 

Рубрика: 

50
Минимизируем функцию по переменной
3
x . Рассмотрим уравнение
3
2
1
1 x
x
x
=− . (3)
Если левая часть соотношения (3) имеет смысл и равенство (3) выполнено, то
оно выполнено и при подстановке в это соотношение переменной y на первом
шаге, то есть при 0
=
y . В остальных случаях значение операции минимизации не
определено.
⎪
⎩
⎪
⎨
⎧
=−
=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=−
случаях.остальных в определено не
;1если,0
1
3
2
1
3
2
1
x
x
x
x
x
x
y
μ
Определение. Частично-рекурсивной функцией называется числовая
функция, получаемая за конечное число шагов из простейших примитивно-
рекурсивных функций с помощью операторов суперпозиции, примитивной
рекурсии и минимизации.
Определение. Числовая функция называется общерекурсивной, если она
частично-рекурсивна и всюду определена.
Определение.
Функция
(
)
n
xxxf ,...,,
21
называется эффективно вычислимой,
если существует алгоритм, позволяющий вычислить ее значения.
В данном определении алгоритм понимается в интуитивном значении,
следовательно, интуитивным является и понятие эффективно вычислимой функции.
Имеет место следующий тезис.
Тезис Черча.
Каждая интуитивно вычислимая функция является частично-
рекурсивной.
Тезис является недоказуемым, так как он связывает нестрогое понятие
интуитивно вычислимой функции и строгое математическое понятие частично-
рекурсивной функции.
Тезис может быть опровергнут построением примера интуитивно
вычислимой, но не частично-рекурсивной функции.
В Содержание.
Задачи. 
     Минимизируем функцию по переменной x3 . Рассмотрим уравнение
       x1
1−         = x3 .                                       (3)
       x2
          Если левая часть соотношения (3) имеет смысл и равенство (3) выполнено, то
оно выполнено и при подстановке в это соотношение переменной y на первом
шаге, то есть при y = 0 . В остальных случаях значение операции минимизации не
определено.
                     ⎧           x1
     ⎛     x1     ⎞ ⎪0, если 1 −    = x3 ;
μ y ⎜⎜1 − = x3 ⎟⎟ = ⎨            x2
     ⎝ x2         ⎠ ⎪не определено в остальных случаях.
                     ⎩

     Определение. Частично-рекурсивной функцией называется числовая
функция, получаемая за конечное число шагов из простейших примитивно-
рекурсивных функций с помощью операторов суперпозиции, примитивной
рекурсии и минимизации.

     Определение. Числовая функция называется общерекурсивной, если она
частично-рекурсивна и всюду определена.

      Определение. Функция f ( x1 , x 2 ,..., xn ) называется эффективно вычислимой,
если существует алгоритм, позволяющий вычислить ее значения.

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

     Тезис Черча. Каждая интуитивно вычислимая функция является частично-
рекурсивной.

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

В Содержание.




     Задачи.



                                         50

Страницы