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

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

Определение

Нумерация ​ $\nu$ из набора $A$ называется полным (относительно элемента $a\in A$), если для каждой частично вычислимой функции $f$ существует тотальная вычислимая функция $h$ so that (Ershov 1999:482):

$\nu \circ h(i)={\begin{cases}\nu \circ f(i)&{\mbox{if}}~i\in \operatorname {dom} (f),\\a&{\mbox{otherwise}}.\end{cases}}$

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

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

Примеры

• Любая нумерация одноэлементного набора является полной.
• Тождественная функция натуральных чисел не является полной.
• является Нумерация Гёделя предварительно полной.

Ссылки

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