Цель данной работы заключается в проверке, обладают ли машинно распознаваемые семейства позитивными и разрешимыми вычислимыми нумерациями.
Приведем основные сведения и определения из теории формальных языков и теории алгоритмов, которые будут использоваться в данной работе.
Зафиксируем конечный алфавит
A {ц0, a1, ..., an}.
Как обычно, через A* обозначим множество всех слов в алфавите A Произвольное подмножество L С A* будем называть языком в алфавите A. Слова конечного алфавита всегда можно взаимно однозначно и эффективно пронумеровать натуральными числами. Например, можно задать номер каждой буквы ai £ A равным (0, г), где
взаимно однозначная вычислимая функция, нумерующая пары, и осуществляющая взаимно однозначное отображение N2 на N. Номер буквы ai £ A будем обозначать через . Номер слова w = b0... bm в алфавите A определим как #w = p#bo.. .рп^ гДе Pi ~ i-ое простое число. Поэтому в дальнейшем изложении все рассматриваемые языки будем отождествлять с подмножествами N. В ходе работы нас будут интересовать только рекурсивно-перечислимые языки, которые также называют вычислимо-перечислимыми.
Как показывают результаты работы, существует достаточно тесная взаимосвязь машинно распознаваемых семейств и теории нумераций. Из предложения 1 следует, что каждое машинно распознаваемое семейство обладает нумераций с Д^-нумерационной эквивалентностью. С помощью критерия позитивности из работы [7] приходим к выводу, что
Машинно распознаваемые семейства имеют позитивные вычислимые нумерации,.
С другой стороны, из теоремы 3 вытекает, что предыдущее утверждение не может быть усилено в следующем смысле
Машинно распознаваемые семейства могут не иметь разрешимых вычислимых нумераций.
[1] Соар, Р. И. Вычислимо-перечислимые множества и степени / Р.И. Со- ар. Пер. с англ. - Казань: Казанское математическое общество, 2000. - 576 с., ил.
[2] Роджерс, X. - Теория рекурсивных функций и эффективная вычислимость / X.Роджерс. Пер. с англ. В.А. Душского, М.И. Кановича. Е.Ю. Ногиной. - М.: Издательство ’’Мир”, 1972. - 624 с.
[3] Ambos-Spies, К.; Badaev, S.; Goncharov, S. - Inductive inference and computable numberings / K. Ambos-Spies - University of Heidelberg, Germany, S. Badaev - Al-Farabi Kazakh University, Kazakhstan, S. Goncharov - Sobolev’s Math Institute, Russia, 2010. - 18 c.
[4] Odifreddi, P.G. Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 1 / P.G. Odifreddi. - University of Turin, Italy, 1989. - 668 c.
[5] Odifreddi, P.G. Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 2 / P.G. Odifreddi. - University of Turin, Italy, 1989. - 668 c.
[6] Ершов, Ю.Л. - Теория нумераций / Ю.Л. Ершов. - М.: Издательство ’’Наука”, 1977. - 416 с.
[7] Бадаев, С. А. - О позитивных нумерациях семейств множеств иерархии Ершова / С.А. Бадаев - Сиб. матем. ж., 18, Л‘°3 (1977), 483-496.