Numeracja (teoria obliczalności)

W teorii obliczalności numeracja to przypisanie liczb naturalnych do zbioru obiektów, takich jak funkcje , liczby wymierne , wykresy lub słowa w jakimś formalnym języku . Numeracja może być wykorzystana do przeniesienia idei obliczalności i pokrewnych pojęć, które zostały pierwotnie zdefiniowane na liczbach naturalnych przy użyciu funkcji obliczalnych , na te różne typy obiektów.

Typowe przykłady numeracji obejmują numerację Gödla w logice pierwszego rzędu , numery opisowe wynikające z uniwersalnych maszyn Turinga oraz dopuszczalne numeracje zbioru częściowych funkcji obliczeniowych.

Definicja i przykłady

Numeracja zbioru jest suriekcją funkcji częściowej od $.$ ( Ershov 1999 $477$ ) Wartość numeracji ν pod numerem i (jeśli jest zdefiniowana) jest często zapisywana ν _ja zamiast zwykłego ${\ Displaystyle \ nu (i) \!$ }

Przykłady numeracji obejmują:

Zbiór wszystkich skończonych podzbiorów $numerację$ zdefiniowaną tak, że $Displaystyle \ gamma (0) = \ pusty zbiór}$ $\$ i tak że dla każdego skończonego niepustego zbioru ${\ Displaystyle A = \ {a_ {0}, \ ldots, a_ {k} \}}$ , ${\ Displaystyle \ gamma (n_ {A}) = A}$ gdzie ${\ Displaystyle n_ {A} = \ suma _ {i \ równoważnik k} 2 ^ {a_ {i}} }$ (Erszow 1999:477). Ta numeracja jest (częściową) bijekcją.
Ustalona numeracja Gödla $pozwalając$ funkcji częściowych może być użyta do zdefiniowania numeracji W przeliczalnych rekurencyjnie , przez W ( i ) być domeną φ _ja . Ta numeracja będzie surjektywna (jak wszystkie numeracje), ale nie iniekcyjna: będą różne liczby, które odwzorowują ten sam rekurencyjnie przeliczalny zbiór pod W .

Rodzaje numeracji

Numeracja jest całkowita , jeśli jest funkcją całkowitą. Jeśli dziedzina numeracji częściowej jest rekurencyjnie przeliczalna , to zawsze istnieje równoważna numeracja całkowita (równoważność numeracji jest zdefiniowana poniżej).

Numeracja η jest rozstrzygalna, jeśli zbiór ${\ Displaystyle \ {(x, y): \ eta (x) = \ eta (y) \}}$ jest zbiorem rozstrzygalnym.

Numeracja η jest jednowartościowa , jeśli η ( x ) = η ( y ) wtedy i tylko wtedy, gdy x = y ; innymi słowy, jeśli η jest funkcją iniekcyjną. Jednowartościowa numeracja zbioru częściowych funkcji obliczalnych nazywana jest numeracją Friedberga .

Porównanie numeracji

Na komplet wszystkich numeracji obowiązuje przedsprzedaż . Niech ${\ Displaystyle \ nu _ {1}: \ mathbb {N} \ rightharpoonup S}$ i ${\ Displaystyle \ nu _ {2}: \ mathbb {N} \ rightharpoonup S}$ będą dwiema numeracjami. Wtedy ${\ Displaystyle \ nu _ {1}}$ można zredukować do , napisanego ${\ Displaystyle \ nu _ {1}}$ ${\ Displaystyle \ nu _ {1} \ równoważnik \ nu _ {2}}$ , jeśli

{\ Displaystyle \ istnieje f \ w \ mathbf {P} ^ {(1)} \, \ forall i \ w \ operatorname {domena} (\ nu _ {1}): \ nu _ {1} (i) = \nu _{2}\circ f(i).}

Jeśli ${\ Displaystyle \ nu _ {1} \ równoważnik \ nu _ {2}}$ i ${\ Displaystyle \ nu _ {1} \ geq \ nu _ {2}} to ν 1 ≤$ ν ${\ Displaystyle \ nu _ {1}}$ jest równoważne z ${\ Displaystyle \ nu _ {2}}$ ; jest to napisane ${\ Displaystyle \ nu _ {1} \ równoważnik \ nu _ {2}}$ .

Numeracje obliczeniowe

numerowane obiekty zbioru S są wystarczająco „konstruktywne”, często patrzy się na numeracje, które można skutecznie zdekodować (Ershov 1999: 486). Na przykład, jeśli S składa się z zestawów przeliczalnych rekurencyjnie, numeracja η jest obliczalna, jeśli zbiór par ( x , y ), gdzie y ∈ η ( x ) jest przeliczalny rekurencyjnie. Podobnie numeracja g funkcji cząstkowych jest obliczalna, jeśli relacja R ( x , y , z ) = "[ g ( x )]( y ) = z " jest częściową rekurencją (Ershov 1999:487).

Numerację obliczalną nazywamy główną , jeśli każda numeracja obliczeniowa tego samego zbioru jest do niej redukowalna. Zarówno zbiór wszystkich rekurencyjnie przeliczalnych podzbiorów, $i$ zbiór wszystkich częściowych funkcji obliczeniowych mają numerację zasad (Ershov 1999: 487). Zasadnicza numeracja zbioru cząstkowych funkcji rekurencyjnych nazywana jest w literaturze numeracją dopuszczalną .

Zobacz też

YL Ershov (1999), „Teoria numeracji”, Handbook of Computability Theory , Elsevier, s. 473–506.
VA Uspenskiĭ , AL Semenov (1993), Algorytmy: główne idee i zastosowania , Springer.