Нөмірлеу (есептеу теориясы) - Numbering (computability theory)

Жылы есептеу теориясы а нөмірлеу тағайындау болып табылады натурал сандар а орнатылды сияқты функциялар, рационал сандар, графиктер, немесе кейбір сөздер тіл. Нөмірлеу бастапқыда натурал сандар арқылы анықталатын есептеу және онымен байланысты ұғымдар идеясын беру үшін қолданыла алады есептелетін функциялар, осы объектілердің әр түрлі типтеріне.

Нөмірлеудің жалпы мысалдары жатады Gödel нөмірлері жылы бірінші ретті логика және рұқсат етілген нөмірлеу ішінара есептелетін функциялар жиынтығының.

Анықтама және мысалдар

A нөмірлеу жиынтықтың Бұл сурьективті ішінара функция бастап дейін S (Ершов 1999: 477). Сандағы ν нөмірлеудің мәні мен (егер анықталған болса) жиі жазылады νмен әдеттегі орнына .

Нөмірлеу мысалдары:

  • Барлық ақырғы ішкі жиындарының жиынтығы нөмірлеу бар , осылай анықталды және әрбір ақырғы бос емес жиынтық үшін , қайда (Ершов 1999: 477). Бұл нөмірлеу биекция болып табылады.
  • Gödel нөмірі есептелетін ішінара функциялардың нөмірленуін анықтау үшін пайдалануға болады W туралы рекурсивті түрде санауға болатын жиынтықтар, жіберу арқылы W(менthe домені болуы керекмен. Бұл нөмірлеу сурьективті болады (барлық нөмірлеу сияқты), бірақ инъективті емес: астында бірдей рекурсивті санақ жиынтығына сәйкес келетін нақты сандар болады W.

Нөмірлеу түрлері

Нөмірлеу барлығы егер бұл жалпы функция болса. Егер домен ішінара нөмірлеу болып табылады рекурсивті түрде санауға болады онда әрқашан эквивалентті жалпы нөмірлеу болады (нөмірлеудің эквиваленттілігі төменде анықталған).

Нөмірлеу. Болып табылады шешімді егер жиынтық болса шешімді жиынтық.

Нөмірлеу. Болып табылады бір мәнді егер η (х) = η (ж) егер және егер болса х=ж; басқаша айтқанда, егер η инъекциялық функция болса. Ішінара есептелетін функциялар жиынтығының бір мәнді нөмірленуі а деп аталады Фридберг нөмірлеу.

Нөмірлерді салыстыру

Бар ішінара тапсырыс беру барлық нөмірлеу жиынтығында. Келіңіздер және екі нөмірлеу болыңыз. Содан кейін болып табылады төмендетілетін дейін , жазылған , егер

Егер және содан кейін болып табылады балама дейін ; бұл жазылған .

Есептеу нөмірлері

Жиынтықтың объектілері болған кезде S жеткілікті «конструктивті», тиімді түрде декодтауға болатын нөмірлеуді қарау әдеттегідей (Ершов 1999: 486). Мысалы, егер S рекурсивті түрде есептелетін жиынтықтардан тұрады, нөмірлеу η болады есептелетін егер жұптар жиынтығы (х,ж) қайда ж∈η (х) рекурсивті түрде санауға болады. Сол сияқты, нөмірлеу ж ішінара функциялар, егер қатынас болса, есептелінеді R(х,ж,з) = "[ж(х)](ж) = з«ішінара рекурсивті болып табылады (Ершов 1999: 487).

Есептелетін нөмірлеу деп аталады негізгі егер сол жиынтықтың әрбір есептелетін нөмірленуі оған азайтылатын болса. Екі жиынтықтың екеуі де ішкі жиындар және барлық ішінара есептелетін функциялар жиынтығында принциптік нөмірлеу бар (Ершов 1999: 487). Ішінара рекурсивті функциялар жиынтығының принциптік нөмірленуі an ретінде белгілі рұқсат етілген нөмірлеу әдебиетте.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  • Y.L. Ершов (1999), «Нөмірлеу теориясы», Есептеу теориясының анықтамалығы, Elsevier, 473–506 бб.
  • В.А. Успенский, А.Л. Семенов (1993), Алгоритмдер: негізгі идеялар мен қолданбалар, Springer.