Cтраница 1
Класс частично рекурсивных функций совпадает с классом функций, вычислимых по Тьюрингу. [1]
Определение класса частично рекурсивных функций легко модифицировать для случая вычислимости с оракулом. Пусть имеется некоторая всюду определенная функция а. F [ a ], который состоит из базисных функций, функции а и всех других функций, которые могут быть из них получены с помощью подстановки, примитивной рекурсии и минимизации. [2]
Так как класс частично рекурсивных функций принадлежит классу МНР-вычислимых функций, он тем более принадлежит классу вычислимых функций. [3]
Точное описание класса частично рекурсивных функций вместе с тезисом Черча дает одно из возможных решений задачи об уточнении понятия алгоритма. Однако это решение не вполне прямое, так как понятие вычислимой функции является вторичным по отношению к понятию алгоритма. [4]
В самом деле, класс частично рекурсивных функций принадлежит классу МНР-вычислимых функций ( см. § 2.3), который в свою очередь входит в класс вычислимых функций. А последний класс, согласно теореме 2.1, принадлежит классу частично рекурсивных функций. Следовательно, все классы совпадают. [5]
Класс эффективно вычислимых функций можно также охарактеризовать как класс частично рекурсивных функций, которые строятся из некоторого множества базисных функций с помощью операций суперпозиции, примитивной рекурсии и минимизации. Себелик и Степанек ( 1980) показали, что все частично рекурсивные функции являются вычислимыми в логике хорновских дизъюнктов; они получили свое доказательство, просто представив базисные функции и правила построения частично рекурсивных функций в логике хорновских дизъюнктов. Они, а также Тернлунд показали, что вычислительная универсальность достижима даже в ограниченной форме логики хорновских дизъюнктов ( бинарной форме), в которой процедуры могут иметь не более одного вызова. Аналогичным образом ван Эмденом ( 1977Ь) и Ковальским ( 1983Ь) были даны хорновские формулировки вычислимых функций, представимых с помощью рекурсивных равенств Клини и равенств Эрбрана. [6]
Тьюринга, Поста, Маркова и других) и который, если ограничиться числовыми функциями, оказался совпадающим с классом частично рекурсивных функций. [7]
Колмогорова являются не числа, а совсем другие конструктивные объекты, на первый взгляд неясно, как можно сравнивать, скажем, класс функций, вычислимых алгоритмами Колмогорова, и класс частично рекурсивных функций, у которых аргументами и значениями являются по определению только натуральные числа. Конечно, эта трудность-возникает не только в связи с алгоритмами Колмогорова, но и при изучение других вычислительных моделей. Рассмотрим, например, семейство всех машин Тьюринга, у которых входной и выходной алфавит есть я, Ь, с, d, и попытаемся объяснить, что значит, что класс вычислимых такими машинами-функций не шире класса частично рекурсивных функций. Для этого фиксируем какое-либо естественное - и потому заведомо вычислимое в обе стороны - взаимно однозначное соответствие между множеством всех слов в алфавите а, Ь, с, d ] и некоторым множеством натуральных чисел. Это соответствие позволяет сопоставить со всякой функцией, перерабатывающей слова в алфавите а, Ь, с, d в слова в том же алфавите, некоторую одноместную числовую функцию. Пусть оказалось ( а на самом деле так и оказывается) г что при этом сопоставлении всякой функции, вычислимой машиной Тьюринга, соответствует частично рекурсивная функция. [8]
В самом деле, класс частично рекурсивных функций принадлежит классу МНР-вычислимых функций ( см. § 2.3), который в свою очередь входит в класс вычислимых функций. А последний класс, согласно теореме 2.1, принадлежит классу частично рекурсивных функций. Следовательно, все классы совпадают. [9]
Если, сохранив условие однозначности, не требовать определимости значений входящих в схему функций для всех, значений аргументов, можно задавать подобными схемами частично рекурсивные функции. Существенно, что никакими рекурсивными определениями ( с помощью конечных схем) не удается выйти за пределы класса частично рекурсивных функций. [10]
Колмогорова являются не числа, а совсем другие конструктивные объекты, на первый взгляд неясно, как можно сравнивать, скажем, класс функций, вычислимых алгоритмами Колмогорова, и класс частично рекурсивных функций, у которых аргументами и значениями являются по определению только натуральные числа. Конечно, эта трудность-возникает не только в связи с алгоритмами Колмогорова, но и при изучение других вычислительных моделей. Рассмотрим, например, семейство всех машин Тьюринга, у которых входной и выходной алфавит есть я, Ь, с, d, и попытаемся объяснить, что значит, что класс вычислимых такими машинами-функций не шире класса частично рекурсивных функций. Для этого фиксируем какое-либо естественное - и потому заведомо вычислимое в обе стороны - взаимно однозначное соответствие между множеством всех слов в алфавите а, Ь, с, d ] и некоторым множеством натуральных чисел. Это соответствие позволяет сопоставить со всякой функцией, перерабатывающей слова в алфавите а, Ь, с, d в слова в том же алфавите, некоторую одноместную числовую функцию. Пусть оказалось ( а на самом деле так и оказывается) г что при этом сопоставлении всякой функции, вычислимой машиной Тьюринга, соответствует частично рекурсивная функция. [11]
Попытаемся уточнить введенное выше понятие сложности или случайности. В 1965 г. Колмогоров предложил для описания этих свойств новое понятие энтропии - так называемую алгоритмическую энтропию. Это новое понятие имеет большое значение для исследования последовательностей ( слов), поскольку позволяет различать случайные последовательности от регулярных. Правда, Колмогоров использовал вместо понятия программы или алгоритма понятие частично рекурсивных функций, исходя из предположения о том, что класс алгоритмически вычислимых функций эквивалентен классу частично рекурсивных функций. Понятие функции применимо к нашей проблеме, если мы исходим из существования взаимно однозначных отображений последовательностей на натуральные числа. [12]
Колмогорова являются не числа, а совсем другие конструктивные объекты, на первый взгляд неясно, как можно сравнивать, скажем, класс функций, вычислимых алгоритмами Колмогорова, и класс частично рекурсивных функций, у которых аргументами и значениями являются по определению только натуральные числа. Конечно, эта трудность-возникает не только в связи с алгоритмами Колмогорова, но и при изучение других вычислительных моделей. Рассмотрим, например, семейство всех машин Тьюринга, у которых входной и выходной алфавит есть я, Ь, с, d, и попытаемся объяснить, что значит, что класс вычислимых такими машинами-функций не шире класса частично рекурсивных функций. Для этого фиксируем какое-либо естественное - и потому заведомо вычислимое в обе стороны - взаимно однозначное соответствие между множеством всех слов в алфавите а, Ь, с, d ] и некоторым множеством натуральных чисел. Это соответствие позволяет сопоставить со всякой функцией, перерабатывающей слова в алфавите а, Ь, с, d в слова в том же алфавите, некоторую одноместную числовую функцию. Пусть оказалось ( а на самом деле так и оказывается) г что при этом сопоставлении всякой функции, вычислимой машиной Тьюринга, соответствует частично рекурсивная функция. Это и означает, что класс вычислимых на машинах Тьюринга функций не шире класса частично рекурсивных функций. [13]