Cтраница 1
Частично рекурсивные функции представляют собой наиболее-общий класс конструктивно определяемых арифметических функций. [1]
Частично рекурсивные функции представляют собой наиболее общий класс конструктивно определяемых арифметических функций, а понятие частично рекурсивной функции является одним из главных понятий теории алгоритмов. [2]
Частично рекурсивная функция является рекурсивной тогда и только тогда, когда она всю ду определена. [3]
Частично рекурсивные функции представляют собой наиболее общий класс конструктивно определяемых арифметических функций. Они охватывают, в частности, все арифметические функции, которые можно задать в виде конечных рекурсивных схем произвольного вида. Под конечной рекурсивной схемой здесь подразумевается любая конечная система равенств г s, где г и s - любые конечные ( содержащие конечное число символов) выражения, построенные из известных примитивно рекурсивных функций неизвестных функций с числовыми и буквенными аргументами, причем значения неизвестных функций для любых заданных значений аргументов должны определяться однозначно за конечное число шагов ( зависящее от выбора значений аргументов) в результате применения двух правил. Первое правило ( правило подстановки) состоит в подстановке в какое-нибудь из заданных равенств вместо одного из аргументов какого-либо его числового значения. [4]
Всякая частично рекурсивная функция вычислима на машине Тьюринга. [5]
Каждая частично рекурсивная функция получается из простейших арифметических функций с помощью операций суперпозиции, примитивной рекурсии и минимизации. [6]
Пусть частично рекурсивная функция f ( x) имеет непустой график. [7]
Каждая частично рекурсивная функция является интуитивно вычислимой, потому что исходные функции интуитивно вычислимы, и ясно, что операторы суперпозиции, примитивной рекурсии и минимизации, примененные к интуитивно вычислимым функциям, дают интуитивно вычислимые. Общепринято считать, что верно и обратное. [8]
Каждая частично рекурсивная функция конструируется из примитивно рекурсивных функций посредством применения операторов суперпозиции, примитивной рекурсии и наименьшего числа. Представляет интерес наименьшее число операторов, требующееся для образования частично рекурсивной функции из примитивно рекурсивных. A priori это число может быть сколь угодно велико. [9]
Класс частично рекурсивных функций совпадает с классом функций, вычислимых по Тьюрингу. [10]
Всюду определенная частично рекурсивная функция наз. Значение всякой частично рекурсивной функции может быть вычислено эффективно в интуитивном смысле. Обращение этого высказывания получило название тезиса Ч е р ч а: всякая функция, значение к-рой может вычисляться эффективно, является частично рекурсивной. Таким образом, согласно тезису Черча, в ы ч и с-лимыми функциями являются частично рекурсивные функции. [11]
Практически понятием частично рекурсивных функций пользуются для доказательства алгоритмической разрешимости или неразрешимости проблем. [12]
Использование же частично рекурсивных функций для представления того или иного конкретного алгоритма практически нецелесообразно ввиду сложности такого процесса алгоритмизации. [13]
Определение класса частично рекурсивных функций легко модифицировать для случая вычислимости с оракулом. Пусть имеется некоторая всюду определенная функция а. F [ a ], который состоит из базисных функций, функции а и всех других функций, которые могут быть из них получены с помощью подстановки, примитивной рекурсии и минимизации. [14]
Из свойств частично рекурсивных функций вытекает следующий простой факт. [15]