번호 매기기(계산성 이론)

계산가능성 이론에서 번호 매기는 함수, 이성적 숫자, 그래프 또는 어떤 공식 언어로 된 단어와 같은 개체 집합에 자연수를 할당하는 것이다. 번호 매기는 계산 가능한 함수를 사용하여 원래 자연수에 정의되어 있는 계산가능성^[1] 및 관련 개념의 사상을 이러한 다른 유형의 개체로 전달하는데 사용될 수 있다.

번호 매기기의 일반적인 예로는 1차 논리에서의 괴델 번호 매기기 및 부분 계산 가능한 함수 집합의 허용 번호 매기기 등이 있다.

정의 및 예제

세트 $S{\displaystyle }$ ${\displaystyle S}$의 번호 지정은$$ $N{\displaystyle \mathbb{}}$ ${\$에서 S(Erershov 1999:477)까지의$$ 돌출적 부분함수다. 숫자 i(정의된 경우)에서 숫자 ν의 값은 흔히 일반적인 $\nu {\displaystyle }$( ${\displaystyle i}$ )${\$ 대신 ν으로_i 표기된다$.$

번호 매기기의 예는 다음과 같다.

• The set of all finite subsets of ${\displaystyle \mathbb {N} }$ has a numbering ${\displaystyle \gamma }$ , defined so that ${\displaystyle \gamma (0)=\emptyset }$ and so that, for each finite nonempty set ${\displaystyle A=\{a_{0},\ldots ,a_{k}\}}$, ${\d$$isplaystyle \gamma(n_{A})$$=A}$ ${\displaystyle \underset{}{여기}}$서 $n{\displaystyle {}_{}}$ ${\displaystyle A_{}}$= ${\displaystyle \underset{}{}}$ i ${\displaystyle \underset{}{\le }}$ k ${\displaystyle {2{}_{}}^{}}$ ${\displaystyle {a_{}}^{}}$ ${\$$A}=\sum _{i\leq k}2^{a_{i}}}$에르쇼프 1999:477. 이 번호 매기는 편향이다
• 계산 가능한 부분함수의 고정$$ 괴델 번호 매기기 number ${\displaystyle i_{}}$ ${\$를 사용하여 W(i)를 φ의_i 도메인으로 하여 재귀적으로 열거할 수 있는 집합의 번호 매기기 W를 정의할 수 있다. 이 번호 매기는 (모든 번호와 마찬가지로) 굴절적이지만 주입되지는 않을 것이다. W에 따라 동일한 반복적으로 열거된 집합에 매핑되는 고유 번호가 있을 것이다.

번호 매기기 유형

총함수일 경우 번호 매기는 총합이다. 부분 번호 매기기 도메인이 재귀적으로 열거되는 경우, 항상 동등한 총 번호 매기기(숫자의 등가 정의)가 존재한다.

집합 { (${\displaystyle x}$, ${\displaystyle y}$) :${\displaystyle \eta }$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle \eta }$( y${\displaystyle }$)${\displaystyle }$}$${\$displaystyle$\{($x,y):$$\eta (x)=\eta (y)\}}}$은(는) 디커피 가능한 집합이다.

숫자 η은 =(x) = η(y)인 경우, x=y인 경우에만, 즉 other이 주입 함수인 경우 단일 값이다. 부분 계산 가능한 함수 집합의 단일 값 번호 부여를 Friedberg 번호 부여라고 한다.

번호 비교

모든 번호의 집합에 사전 주문이 있다. $\nu {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$: ${\displaystyle N\mathbb{}}$ ${\displaystyle \rightharpoonup }$ ${\displaystyle S}$ ${\displaystyle \nu _{1}:\mathb {N} \rstarpoonup S}$ 및$$ ${\displaystyle {\nu \mathrm{}}_{}}$ 2${\displaystyle {}_{}}$: ${\displaystyle N}$ ${\displaystyle \rightharpoonup }$ S ${\displaystyle \nu _{2}\mathb {N} \rstigitarpoop S}$을 두 개의 번호로 지정한다$$. 그 다음 $\nu {\displaystyle {}_{}}$ ${\$1}는 ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$$displaystyle \$${\displaystyle {nu\_\mathrm{}}_{}}$${2}}:$$q$ 1 nu 2 {\$displaystyle \nu_{1}\$leq $\nu_{2$}}:$$if로 축소할 수 있다$$.

${\displaystyle \exists f\in \mathbf {P} ^{(1)\,\all \in \mathrm {Domain}(\nu _{1}):\nu _{1}(i)=\nu _{2}\circu f(i).}$

If ${\displaystyle \nu _{1}\leq \nu _{2}}$ and ${\displaystyle \nu _{1}\geq \nu _{2}}$ then ${\displaystyle \nu _{1}}$ is equivalent to ${\displaystyle \nu _{2}}$; this is written ${\displaystyle \nu _{1}\equiv \nu _{2}}$.

계산 가능한 번호 지정

번호가 매겨지는 집합 S의 물체가 충분히 "건설적"일 때, 효과적으로 해독할 수 있는 숫자(Ershov 1999:486)를 보는 것이 일반적이다. 예를 들어 S가 재귀적으로 열거할 수 있는 집합으로 구성된 경우, y ∈ η(x)가 재귀적으로 열거되는 쌍 집합(x,y)이 있으면 숫자 ing을 계산할 수 있다. 마찬가지로 부분함수의 숫자 g는 관계 R(x,y,z) = "[g(x)](y) = z"가 부분 재귀적(Eershov 1999:487)이면 계산할 수 있다.

계산 가능한 번호 부여는 동일한 집합의 모든 계산 가능한 번호 부여가 축소될 수 있는 경우 주계약이라고 불린다. $N{\displaystyle \mathbb{}}$ ${\$의 모든 반복적으로 열거된 하위 집합 집합과 모든$$ 부분 계산 가능한 함수 집합에는 모두 원칙 번호가 있다(Eershov 1999:487). 부분 재귀 함수 집합의 원칙 번호 매기는 문헌에서 허용 가능한 번호 매기기라고 알려져 있다.

참고 항목

• 완전한 번호 매기기
• 원통형화
• 괴델 번호 매기기

참조

• Y.L. 에르쇼프(1999), "숫자의 이론", 계산가능성 이론 핸드북, Exvier, 페이지 473–506.
• V.A. Uspenskiĭ, A.L. 세메노프(1993), 알고리즘: 주요 아이디어와 응용 프로그램, 스프링거.