Теория нумераций

реферат

О теории нумераций

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

Нумерация - это отображение некоторого подмножества множества натуральных чисел N на исследуемый класс конструктивных объектов (формул, слов, матриц и т.п.)

Теория нумераций является разделом теории алгоритмов призванным решить вопросы, связанные с приведением к «общему знаменателю» на основе понятия нумерованного множества. В теории нумераций разрабатывается необходимая система понятий, ставятся и решаются вопросы, такие как, например, зависимость или независимость тех или иных свойств множества от выбора нумерации, существование (единственность) нумерации с заданными свойствами.

Общая теория нумераций возникла в феврале 1954 года в результате замечания, сделанного Колмогоровым на семинаре по рекурсивной арифметике. Поводом послужило изучение на указанном семинаре так называемых конструктивных ординалов (конструктивных порядковых чисел), т.е. тех ординалов, которых можно снабдить именами, используя некоторую алгоритмическую процедуру. Основные понятия теории нумераций были сформулированы Колмогоровым при обсуждении этой темы.

Результаты теории нумераций оказались важными для прояснения ряда трудностей, возникающих при эксплуатации вычислительной техники. Например, одной из важных задач программирования является задача эффективного построения по программе вычисления функции на одной машине программы вычисления той же функции на другой машине. Практическая реализация этих «переводов» («трансляций») для двух универсальных машин оказывается весьма сложной, а часто и не осуществленной.

Под «универсальной вычислительной машиной» будем понимать машину, вычисляющую некоторую двуместную функцию , универсальную для класса всех одноместных частично рекурсивных функций, а под «программой вычисления одноместной частично рекурсивной функции » будем понимать ее номер (один из ее номеров), т.е. такое число n N, что таким образом, если имеются две универсальные вычислительные машины (т.е. две универсальные функции ), то «проблема перевода» может быть сформулирована как проблема существования одноместной общерекурсивной функции f такой что

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

Тем не менее, в классе так определенных универсальных машин существует «самая» универсальная (которую, по-видимому, только и стоит называть универсальной) в том смысле, что на язык этой машины может быть осуществлен перевод с любой другой универсальной машины. Если же рассматривать машины, которые вычисляют только общерекурсивные (всюду определенные) функции из некоторого достаточно богатого класса, то ситуация становится еще более плохой. Для любой такой машины существует другая машина, вычисляющая тот же класс функций, такая, что обе проблемы перевода неразрешимы. Указанный только что подход к разъяснению трудностей перевода может быть использован для определения понятия сложности класса функций (с помощью полурешетки вычислимых нумераций этого класса).

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

Делись добром ;)