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

Рефераты / Математика / Теория нумераций

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

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

Нумерация – это отображение некоторого подмножества множества

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

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

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

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

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

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

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

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

Предварительные сведения

Через O обозначим класс всех одноместных общерекурсивных функций, а через O – класс всех одноместных однозначных общерекурсивных функций.

Двуместная функция с определенная так , называется канторовской нумерующей функцией. Оно осуществляет взаимно-однозначное отображение . Существуют однозначно определенные функции r, такие что

для любых .

Используя канторовскую функцию с, можно определить последовательность общерекурсивных функций такую что - n‑местная функция, осуществляющая взаимно-однозначное отображение :

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

Функцию назовем сверткой, а набор – n‑разверткой.

Если Если f – функция, то график f множество . Будем говорить что множество А m‑сводится к В (символически ), если существует O такая что для любого . Всякую функцию O удовлетворяющую этому условию называют сводящей (А к В). Еще говорят что f m‑сводит к А к В.