Полная нумерация

В теории вычислимости полных нумераций являются обобщением Гёделя нумерации первой введенной А. И. Мальцевым в 1963 г. Они изучали , потому что несколько важных результатов , как в теореме рекурсии Клини и теоремы Райса , которые были первоначально испытанной для Геделя-нумерованный набор вычислимых функций , все еще верны для произвольных множеств с полной нумерацией.

Определение

Нумерация множества называется полным (по отношению к элементу ) , если для каждой частичной вычислимой функции существует общая вычислимая функция так что (Ершов 1999: 482):${\ displaystyle \ nu}$${\ displaystyle A}$${\ displaystyle a \ in A}$ ${\ displaystyle f}$ ${\ displaystyle h}$

${\ displaystyle \ nu \ circ h (i) = {\ begin {case} \ nu \ circ f (i) & {\ mbox {if}} ~ i \ in \ operatorname {dom} (f), \\ a & {\ mbox {иначе}}. \ end {case}}}$

Ершов называет элемент a «особым» элементом для нумерации. Нумерация называется предполной, если выполняется более слабое свойство:${\ displaystyle \ nu}$

${\ displaystyle \ nu \ circ f (i) = \ nu \ circ h (i) \ qquad i \ in \ operatorname {dom} (f).}$

Примеры

• Любая нумерация одноэлементного набора завершена
• Функция идентичности натуральных чисел не является полной
• Гедель нумерации предполон

использованная литература

• Ю.Л. Ершов (1999), "Теория нумерации", Справочник по теории вычислимости , Э. Р. Гриффор (ред.), Эльзевьер, стр. 473–506. ISBN  978-0-444-89882-1
• А. И. Мальцев, Наборы с полной нумерацией . Алгебра и логика , 1963, т. 2, вып. 2, 4-29 (рус.)