Cтраница 2
Каждая стандартно заданная частично рекурсивная функция вычислима путем определенной процедуры механического характера. [16]
ОБЩЕРЕКУРСИВНАЯ ФУНКЦИЯ - частично рекурсивная функция, определенная для всех значений аргументов. [17]
Вполне перечислимые семейства частично рекурсивных функций Ниже мы хотим построить систему полных нумераций, имеющих весьма естественный вид, и доказать, что эти нумерации не являются изоморфными. [18]
Клини ввел понятие частично рекурсивной функции и высказал гипотезу, что все частичные функции, вычислимые посредством алгоритмов, являются частично рекурсивными. Эта гипотеза также недоказуема, как и гипотеза Черча. [19]
Точное описание класса частично рекурсивных функций вместе с тезисом Черча дает одно из возможных решений задачи об уточнении понятия алгоритма. Однако это решение не вполне прямое, так как понятие вычислимой функции является вторичным по отношению к понятию алгоритма. [20]
Клини ввел понятие частично рекурсивной функции и высказал гипотезу, что все частичные функции, вычислимые посредством алгоритмов, являются частично рекурсивными. Частичной функцией называется функция, определенная не для всех значений аргументов, а только на некотором подмножестве значений аргументов. В дальнейшем под тезисом Черча стали понимать гипотезу Черча в том расширенном виде, который был придан ей С. [21]
Для любой п-местной частично рекурсивной функции f ее область определения Af является рекурсивно перечислимым предикатом. [22]
Итак, понятие частично рекурсивной функции является уточнением понятия интуитивно вычислимой числовой функции. [23]
Классом Кчр всех частично рекурсивных функций называется множество всех функций, которые могут быть получены из простейших функций с помощью операций суперпозиции, примитивной рекурсии и минимизации. [24]
Так как класс частично рекурсивных функций принадлежит классу МНР-вычислимых функций, он тем более принадлежит классу вычислимых функций. [25]
Доказать, что всякая частично рекурсивная функция / имеет бесконечно много клиниевских номеров. [26]
Доказать, что любая частично рекурсивная функция правильно вычислима по Тьюрингу. [27]
Каждая нумерация совокупности одноместных частично рекурсивных функций, имеющая рекурсивно перечислимое номерное множество и чр-эквивалентная геделевской нумерации чр-изоморфна геделевской нумерации. [28]
Рассмотрим некоторую формализацию теории частично рекурсивных функций. [29]
Таким образом, каждая заданная частично рекурсивная функция вычислима путем определенной процедуры механического характера, и наоборот - числовые функции, вычислимые посредством алгоритмов, являются частично рекурсивными. В соответствии с тезисом Черча класс алгоритмически ( или машинно) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивцых функций. [30]