Cтраница 3
Доказать, что существует двуместная частично рекурсивная функция U ( t, с), универсальная для семейства всех одноместных частично рекурсивных функций. [31]
Доказать, что множество значений частично рекурсивной функции рекурсивно перечислимо. [32]
Докажите, что класс 91й частично рекурсивных функций на 2, определенных на примере 6.2, тождествен классу функций на 2, вычислимых по Посту. [33]
Доказать, что не существует частично рекурсивной функции, универсальной для семейства всех л-местных общерекурсивных функций. [34]
В самом деле, класс частично рекурсивных функций принадлежит классу МНР-вычислимых функций ( см. § 2.3), который в свою очередь входит в класс вычислимых функций. А последний класс, согласно теореме 2.1, принадлежит классу частично рекурсивных функций. Следовательно, все классы совпадают. [35]
Понятие частично рекурсивного предиката позволяет охарактеризовать частично рекурсивные функции, исполь зуя понятие графика. [36]
Ясно, что если f - частично рекурсивная функция, то и fk - частично рекурсивна для любого k e со. [37]
Колмогорова; указывается, что каждая частично рекурсивная функция вычислима некоторым алгоритмом Колмогорова; в § 3 показывается, что всякая числовая функция, вычислимая каким-либо алгоритмом Колмогорова, является частично рекурсивной. [38]
Этот тезис дает алгоритмическое толкование понятию частично рекурсивных функций. Практически понятие частично рекурсивных функций используют для доказательства алгоритмической разрешимости или неразрешимости проблем. Использование же частично рекурсивных функций для представления того или иного конкретного алгоритма практически нецелесообразно ввиду сложности такого процесса алгоритмизации. [39]
Доказать, что если область определения частично рекурсивной функции fn есть рекурсивное множество, то / л имеет рекурсивное доопределение. [40]
Отметим теперь, что существование универсальных частично рекурсивных функций является следствием существования универсальных рекурсивно перечислимых предикатов. [41]
Пусть / ( х) - произвольная частично рекурсивная функция. [42]
Для понимания определения важно заметить, что частично рекурсивные функции, вообще говоря, не являются всюду определенными. Не существует регулярного процесса для выяснения того, приведет применение программы р к объекту х к какому-либо результату или нет. [43]
Пусть 4 - некоторое непустое семейство одноместных частично рекурсивных функций, отличное от семейства всех таких функций. [44]
Всякий алгоритм сводится к вычислению значений некоторой частично рекурсивной функции. Это доказывается так называемым методом арифметизации. [45]