라이스의 정리

계산 가능성 이론에서, 라이스의 정리는 프로그램의 모든 사소한 의미 특성은 결정할 수 없다고 말한다.시맨틱 속성은 구문 속성(예를 들어 프로그램이 if-then-else 문을 포함)과 달리 프로그램의 동작(예를 들어 모든 입력에 대해 종료)에 관한 것입니다.속성은 모든 부분 계산 가능 함수에 대해 참이 아니거나 모든 부분 계산 가능 함수에 대해 거짓이 아닌 경우 중요하지 않습니다.

Rice의 정리는 함수의 관점에서도 사용될 수 있다: 부분 함수의 사소한 성질에 대해, 어떤 일반적이고 효과적인 방법도 알고리즘이 그 성질을 가지고 부분 함수를 계산하는지 결정할 수 없다.여기서, 부분 함수의 속성은 모든 부분 계산 가능 함수에 대해 유지되거나 없는 경우 사소한 것으로 불리며, 효과적인 결정 방법은 모든 알고리즘에 대해 올바르게 결정되면 일반적인 것으로 불린다.이 정리는 1951년 시러큐스 대학에서 박사학위 논문을 통해 증명한 헨리 고든 라이스의 이름을 딴 것이다.

서론

허락하다p의미상 중요하지 않은 공식 언어의 속성이다

특성 p를 가진 재귀 열거 가능한 언어가 존재한다.
특성 p를 가지지 않는 반복 열거 가능한 언어가 존재한다.

(즉, p는 재귀적으로 열거할 수 있는 모든 언어에 대해 균등하게 참이거나 균등하게 거짓이 아닙니다).

그러면 주어진 튜링 기계 M에 대해, 그것에 의해 인식되는 언어인 L(M)이 특성 p를 가지고 있는지 아닌지를 결정하는 것은 불가능하다.

실제로, 이것은 주어진 튜링 기계의 언어가 특정한 중요하지 않은 속성을 가지고 있는지 여부를 항상 결정할 수 있는 기계가 없다는 것을 의미한다.특별한 경우로는 예를 들어 튜링 기계에 의해 인식된 언어가 유한 오토마톤과 같이 단순하지 않은 기계에 의해 인식될 수 있는지의 판별 불가능성이 포함된다(즉, 튜링 기계의 언어가 규칙적인지 여부는 판별할 수 없다).

라이스의 정리가 기계나 프로그램의 속성과 관련이 없다는 것을 주목하는 것은 중요하다. 그것은 기능과 언어의 속성과 관련이 있다.예를 들어 기계가 특정 입력에서 100단계 이상 실행되는지 여부는 중요하지 않지만 결정 가능한 속성입니다.정확히 동일한 언어를 인식하는 두 개의 서로 다른 시스템에서 동일한 입력 문자열을 인식하기 위해 서로 다른 수의 단계가 필요할 수 있습니다.마찬가지로, 기계가 5개 이상의 상태를 가지고 있는지 여부는 단순히 상태 수를 셀 수 있기 때문에 기계의 결정 가능한 특성입니다.튜링 기계와 관련이 있지만 튜링 기계로 인식되는 언어가 아닌 이런 종류의 속성에는 라이스의 정리가 적용되지 않는다.

허용 가능한 프로그래밍 시스템의 로저스의 특성을 이용하여, 라이스의 정리는 본질적으로 튜링 기계에서 대부분의 컴퓨터 프로그래밍 언어로 일반화 될 수 있다: 컴퓨터 프로그램의 동작에 대한 일반적이지 않은 질문으로 결정하는 자동 방법은 존재하지 않는다.

예를 들어, 정지 문제의 다음 변형에 대해 생각해 보겠습니다.P를 하나의 인수의 부분 함수 F의 다음 속성으로 합니다. P(F)는 F가 인수 '1'에 대해 정의됨을 의미합니다.1에 정의되어 있는 부분 함수와 1에 정의되어 있지 않은 함수가 있기 때문에 이는 분명 중요하지 않습니다.1-할팅 문제는 이 속성을 가진 함수를 정의하는지 여부(즉, 알고리즘이 입력 1에서 정지하는지 여부)를 결정하는 문제입니다.라이스의 정리에 따르면, 1-할팅 문제는 결정할 수 없다.마찬가지로 튜링 기계 T가 (완전 정지 문제에서처럼 T에 대한 설명 외에 두 번째 인수로 주어지는 첫 번째 단어 w가 아니라) 처음에 비어 있는 테이프에서 끝나는지에 대한 질문은 여전히 결정할 수 없다.

형식적 진술

$(\$ 은 $\mathbb N$ 자연수, P $)$ 는 1(\displaystyle $\mathbf {P}^{(1)})$ 는 $\mathbf {P} ^{(1)}$ 단항(부분) 계산 가능 함수의 클래스를 나타낸다. $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ : $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ ( $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ ) { $displaystyle \phi$ \displaybb ${N}$ \ $to \mathbf {P}$ ^{( $1)}}$ 을 $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ 계산 가능 함수의 허용 번호 부여로 한다. $\phi _{e}:=\phi (e)$ e : $\phi _{e}:=\phi (e)$ （ $\phi _{e}:=\phi (e)$ ） \ $displaystyle \phi$ _ { $\phi _{e}:=\phi (e)$ : $=\phi$ (e $)}$ 번째 (최소) 계산 가능 함수.

우리는 계산 가능한 함수가 가질 수 있는 각 속성을 해당 속성을 가진 함수로 구성된 $\mathbf {P} ^{(1)}$ P ( $\mathbf {P} ^{(1)}$ ) $\mathbf {P} ^{(1)}$ \ $displaystyle \mathbf {P} ^{(1)}$ 의 $\mathbf {P} ^{(1)}$ 서브셋으로 식별한다.따라서 집합 $F\subseteq \mathbf {P} ^{(1)}$ P ( $F\subseteq \mathbf {P} ^{(1)}$ $){$ $displaystyle$ F $\subseteq \mathbf$ { $P$ } $^{$ ( $1$ 가 $\phi _{e}$ 지정되면 계산 가능한 함수 $(\$ _ ${$ $e})$ 는 각 $\phi _{e}\in F$ 의 $F\subseteq \mathbf {P} ^{(1)}$ $(\displaystyle \$ i { $e$ 인 $경우$ 에만 $속성$ F(\ $displaystyle$ F $)$ 를 $F$ 가집니다.}} 관련 $F\subseteq \mathbf {P} ^{(1)}$ 멤버십 $D_{F}$ 문제 $DF(\$ displaystyle $D_$ {F $})$ 는 e를 $지정$ 하면 $(\displaystyle$ \ $phi _{e$ }\ $in$ F $\phi _{e}\in F$ $\phi _{e}\in F$ 를 판단합니다 $.$

Rice의 정리는 F $F=\varnothing$ ${\$ \ $displaystyle$ $F =$ \ varnothing } $F=\mathbf {P} ^{(1)}$ F $=$ ( $1$ ) { \ $displaystyle$ F $=$ \ $mathbf$ { P $}$ ^ { (1 $F=\mathbf {P} ^{(1)}$ 인 $F=\varnothing$ 에만 결정 $D_{F}$ D $D_{F}$ {\ displaystyle D_{ $F$ $}$ 를 $D_{F}$ 결정할 수 있음을 나타냅니다.

예

라이스의 정리에 따르면, 부분 계산 가능 함수의 특정 클래스 C에 적어도 하나의 부분 계산 가능 함수와 C에 없는 다른 부분 계산 가능 함수가 있다면, 특정 프로그램이 C에서 함수를 계산하는지 여부를 결정하는 문제는 결정할 수 없다.예를 들어, Rice의 정리는 다음과 같은 부분 계산 가능 함수의 집합 각각은 결정할 수 없다는 것을 보여준다(즉, 집합은 재귀적이지 않거나 계산할 수 없음).

모든 입력에 대해 0을 반환하는 부분 계산 가능 함수의 클래스 및 그 보완입니다.
하나 이상의 입력에 대해 0을 반환하는 부분 계산 가능 함수의 클래스 및 그 보완입니다.
일정하고 보완적인 부분 계산 가능 함수의 클래스입니다.
주어진 부분 계산 가능 함수와 동일한 부분 계산 가능 함수의 클래스 및 그 보완입니다.
일부 입력에 대해 분기(즉, 정의되지 않음)되는 부분 계산 가능 함수의 클래스 및 그 보완입니다.
계산 가능한 함수의 ^[1]총 인덱스 클래스입니다.
공유한 재귀 열거 가능한 집합의 인덱스 클래스입니다.
재귀적인 반복 열거 가능한 집합의 인덱스 클래스입니다.

클라인의 재귀정리에 의한 증명

클리에네의 재귀정리에 따르면 모든 Gödel 번호 $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ : $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ ( $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ $)\$ { $N}\to \mathbf {P}$ $Q(x,y)$ 1 $\phi \colon \mathbb {N} \to \mathbf {P} ^{(1)}$ )}\computable 함수 Q ( $Q(x,y)$ , $Q(x,y)$ )\ $displaystyle$ Q $(x$ )\displaysty $Q(x,y)$ 에 대하여 다음과 같은 지수를 갖는다. ${\displaystyle$ \ $phi _{e}(y$ )}는 $\phi _{e}(y)$ $Q(e,y)$ y $)$ { $displaystyle Q(e$ ,y $Q(e,y)$ 를 $g(x)$ 반환합니다. ( $f(x)$ 에서는 $f(x)=g(x)$ f $f(x)=g(x)$ $)$ { $displaystyle f($ x)} $f(x)$ $g(x)$ " $)$ { $displaystyle g($ x)} 또는 f $f(x)=g(x)$ x $f(x)=g(x)$ 중 $f(x)=g(x)$ 일 $f(x)$ f $f(x)$ $x)$ { $displaystyledisplaystyle$ f $(x$ ) $=$ (x)}라고 합니다 $.$ 정의되어 있지 않습니다).직관적으로 $\phi _{e}$ e $\phi _{e}$ \ $displaystyle \phi$ _ ${e}$ 는 $\phi _{e}$ 자체 소스 코드(Gödel 번호)를 반환하는 함수인 Quine입니다. 단, $\phi _{e}$ e \ $displaystyle \phi$ _ ${e}$ 는 $\phi _{e}$ 직접 반환하지 않고 Gödel 번호를Q {\ $displaystyle$ Q $}$ 에 $Q$ 하고 $Q$ 결과를 반환합니다.

F{\ $displaystyle$ F $}$ 가 $F$ $\emptyset \neq F\neq \mathbf {P} ^{(1)}$ $\emptyset \neq F\neq \mathbf {P} ^{(1)}$ P ( $\emptyset \neq F\neq \mathbf {P} ^{(1)}$ $){$ $displaystyle \emptyset \neq F\neq \mathbf$ { $P}$ ^{( $1)}$ 와 같이 계산 가능한 $f\in F$ f $f\in F$ F {\ $display$ f $\in$ F $}$ 와 $f\in F$ G $\style$ F (\ $display$ style F\n)와 같이 계산 가능한 함수의 집합이라고 가정합니다. $splaystyle$ x $x$ }: $\phi _{x}\in F$ F $\phi _{x}\in F$ { $displaystyle$ $\phi _{x}\in F$ \ $phi _$ { $x$ $\phi _{x}\in F$ }\ $in$ F } { $displaystyle$ $\phi _{x}\in F$ \ $Q(x,y)$ $phi$ $_$ $g(y)$ { $Q(x,y)$ $g(y)$ $\phi _{x}\in F$ }\ $in F$ $f(y)$ $\phi _{x}\in F$ spl spl spl spl spl $f(y)$ spl $g(y)$ ( spl spl spl spl spl spl spl spl spl spl spl $Q(x,y)$ spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl $g(y)$ spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl spl재귀정리에 따라 $\phi _{e}(y)$ e ( $\phi _{e}(y)$ ) \ $displaystyle$ $\phi$ _ { e $\phi _{e}\in F$ } $Q(e,y)$ { e $\phi _{e}(y)$ $Q(e,y)$ $\phi _{e}\in F$ $\phi _{e}$ $displaydisplaydisplaydisplay$ $\phi _{e}$ displaydisplay displaydisplaydisplay displaydisplay displaydisplay display $\phi _{e}\in F$ displaydisplaydisplay $displaydisplaydisplaydisplay displaydisplaydisplaydisplaydisplaydisplay display$ display $\phi _{e}$ display $\phi _{e}$ displaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplay displaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplay displaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplay $Q(e,y)$ displaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplaydisplay $isplaystyle$ g $g$ 즉 " $\phi _{e}\notin F$ $\phi _{e}\notin F$ { $displaystyle \phi$ _ ${e}\notin$ $F$ 입니다. $,$ " $\phi _{e}\notin F$ F { $displaystyle \$ $phi$ $\phi _{e}\notin F$ $_{e}$ 의 $\phi _{e}$ 경우 $,$ " $\phi _{e}\in F$ \ $displaystyle$ f $f$ 는f $\displaystyle$ f}이며 $\phi _{e}\in F$ $\phi _{e}\in F$ " $e\$ displaystyle f" 가 됩니다 $.$

정지된 문제를 줄임으로써 입증

프루프 스케치

구체적으로는 프로그램 p를 검사하고 p가 정수 d를 가져와서 d를² 반환하는 제곱함수의 구현인지 아닌지를 확실히 판단하기 위한 알고리즘이 있다고 가정합니다.이 증명은 프로그램 동작의 다른 중요하지 않은 속성(즉, 의미적 속성 및 중요하지 않은 속성)을 결정하기 위한 알고리즘을 가지고 있는 경우에도 잘 작동하며, 일반적으로 아래에 제시되어 있습니다.

이 주장은 스쿼링 프로그램을 식별하는 알고리즘을 정지하는 함수를 식별하는 알고리즘으로 변환할 수 있다는 것입니다.입력 a와 i를 받아 입력 i가 주어졌을 때 프로그램 a가 정지되는지 여부를 결정하는 알고리즘을 설명합니다.

이것을 결정하는 알고리즘은 개념적으로 간단하다: 인수 n을 갖는 새로운 프로그램 t를 구성(설명)하고, (1) 먼저 입력 i에 대해 프로그램 a를 실행하고(a와 i 모두 t의 정의에 하드 코딩됨), 다음으로 (2) n의 제곱을 반환한다.a(i)가 영원히 실행되면 n에 관계없이 t는 스텝 (2)에 도달하지 않습니다.t는 (1)단계가 종료된 경우에만 제곱을 계산하는 함수입니다.제곱을 계산하는 프로그램을 확실하게 식별할 수 있다고 가정했기 때문에 a와 i에 의존하는 t가 그런 프로그램인지, a와 i마다 그런 프로그램인지를 판단할 수 있기 때문에 입력 i에 대해 프로그램이 중단되는지 여부를 결정하는 프로그램을 얻었다.정지판정 알고리즘은 t를 실행하지 않고 그 기술을 squaring-identification 프로그램에만 전달하는 것에 주의해 주십시오.이것은 가정에 의해 항상 종료됩니다.t의 설명의 구축도 항상 종료되는 방법으로 실행할 수 있기 때문에 정지판정도 중단되지 않을 수 없습니다.

halts(a,i) {define t(n) {a(i) return n×n} return is_a_squaring_function(t)}

이 방법은 제곱을 계산하는 함수를 인식할 수 있는지 여부에 따라 특별히 달라지는 것이 아닙니다. 일부 프로그램이 인식하려는 기능을 수행할 수 있는 경우 t를 얻기 위해 에 호출을 추가할 수 있습니다.제곱근 연산 프로그램이나 월급을 계산하는 프로그램, 입력이 있을 때 정지하는 프로그램을 인식하는 방법이 있을 수 있습니다.어느 경우든 마찬가지로 정지 문제를 해결할 수 있습니다.

정식 증명

사소한 속성을 결정하는 알고리즘이 있으면 정지 문제를 결정하는 튜링 머신을 구축할 수 있습니다.

형식 증명에서는 알고리즘은 문자열에 대해 부분 함수를 정의하는 것으로 간주되며, 그 자체가 문자열로 표현됩니다.문자열 a로 나타나는 알고리즘에 의해 계산된 부분 함수는 F로 표시됩니다_a.이 증명은 reductio ad furnum에 의해 진행됩니다.알고리즘에 의해 결정되는 사소한 속성이 있다고 가정하고, 그 결과 정지 문제를 결정할 수 있다는 것을 알 수 있습니다.그것은 불가능하며, 따라서 모순입니다.

이제 P(a)가 F의 사소한_a 성질을 결정하는 알고리즘이라고 가정하자.일반성의 손실 없이 우리는 P(no-halt) = "no"라고 가정할 수 있으며, no-halt는 절대 정지하지 않는 알고리즘의 표현이다.이것이 사실이 아닌 경우, 이것은 속성의 부정으로 간주됩니다.P는 비표준 특성을 결정하므로, 알고리즘을 나타내는 문자열 b가 있고 P(b) = "예"가 된다.다음으로 알고리즘 H(a, i)를 다음과 같이 정의할 수 있습니다.

1. 알고리즘 T(j)를 나타내는 문자열 t를 다음과 같이 구성합니다.

T는 먼저 F(i)의_a 연산을 시뮬레이션한다.
그런 다음 T는 F(j)의 계산을_b 시뮬레이션하고 결과를 반환합니다.

2. P(t)를 반환합니다.

이제 정지 문제를 H가 결정한다는 것을 알 수 있습니다.

입력 i에서 가 나타내는 알고리즘이 정지한다고 가정합니다.이 경우_t F = F이고_b P(b) = "yes"이고 P(x)의 출력은 F에만_x 의존하기 때문에 P(t) = "yes"이고 따라서 H(a, i) = "yes"가 된다.
가 나타내는 알고리즘이 입력 i로 정지하지 않는다고 가정합니다.이 경우_t F = F_no-halt, 즉 정의되지 않은 부분 함수입니다.P(no-halt) = "no"이고 P(x)의 출력은 F에만_x 의존하므로, P(t) = "no"가 되고 따라서 H(a, i) = "no"가 된다.

정지 문제는 판별할 수 없는 것으로 알려져 있기 때문에 이것은 모순이며, 에 의해 나타나는 함수의 사소한 속성을 결정하는 알고리즘 P(a)가 있다는 가정은 거짓이어야 한다.

라이스의 정리 및 지수 집합

라이스의 정리는 지수 집합의 관점에서 간결하게 설명할 수 있다.

${\mathcal {C}}$ {\ $displaystyle {C}}$ 을 ${\mathcal {C}}$ $($ 를) 인덱스 $집합$ C {\displaystyle C $C$ 의 부분 재귀 함수의 클래스라고 $합니다$ .C $C=\varnothing$ ${\$ \ $displaystyle$ C = \ $varnothing$ $}$ $C=\mathbb {N}$ $C=\mathbb {N}$ $=$ N \ $displaystyle$ C $=$ \ $mathbb {$ N $C=\mathbb {N}$ 인 경우에만C가 $C$ 재귀합니다.

$\mathbb {N}$ 서 N $(\$ 은 $\mathbb {N}$ 0을 포함한 자연수의 집합입니다.

재귀집합에 대한 라이스의 정리 유사체

라이스의 정리는 재귀적으로 열거할 수 있는 집합이 특정한 중요하지 않은 ^[2]속성을 가지고 있는지 여부를 효과적으로 결정하는 것이 불가능하다고 주장한다고 볼 수 있다.이 섹션에서는 반복 열거 ^[3]집합 대신 재귀 집합에 대한 라이스의 정리를 유사하게 제시한다.대략적으로 말하면, 아날로그는 모든 재귀 집합에 대해 특정 특성이 있는지 여부를 효과적으로 판단할 수 있다면, 최종적으로는 많은 정수만이 재귀 집합이 속성을 가지고 있는지 여부를 결정할 수 있다고 말한다.이 결과는 Rice의 원래 정리와 유사합니다. 왜냐하면 두 결과 모두 속성이 "결정 가능"한 것은 i $($ $원래$ 정리의 경우no( $i$ )\ $displaystyle$ $i$ i) $i$ 가 $i$ $t$ 에 속하는지 $i$ 를 조사하여 확인할 수 있는 경우에만 해당 특성이 "결정 가능"하기 때문입니다.그는 정해졌다.

W $(\displaystyle$ W $)$ 를 $W$ 재귀 집합의 클래스(단순 게임으로 불리며 속성으로 생각됨)로 $합니다$ .S $(\displaystyle$ S $)$ 가 $S$ 재귀 집합인 $경우$ , $e$ (\ $displaystyle$ e $e$ 에 대해 계산 가능한 함수 $\phi _{e}$ e(\ $displaystyle$ $\phi_{e$ })는 $\phi _{e}$ S $(\displaystyle$ S $S$ 의 특성 함수입니다. 우리는 e $($ $무한히$ 많은 e)라고 $e$ $부릅니다$ .\ $displaystyle$ e $.\$ $displaystyle$ W $.\displaystyle$ e $.\displaystyle$ $e$ .\ $e$ displaystyle e를 결정하는 $W$ 알고리즘(계산 가능 함수)이 있는 경우 $클래스$ W를 계산할 수 있다고 가정합니다(특징 인덱스는 아님).

e{\ $displaystyle$ e $e$ $}$ 가 W {\ $displaystyle$ W $W$ 에 속하는 재귀 집합의 특성 지표인 $경우$ 알고리즘은 "예"를 부여합니다.
e $e$ {\ $displaystyle$ e $}$ 가 $W$ W{\ $displaystyle$ W}에 속하지 않는 재귀 집합의 특성 색인인 $경우$ 알고리즘은 "아니오"를 지정합니다.

만약 kS∈{\displayst 집합 SN⊆{\displaystyle S\subseteq \mathbb{N}}는 10과 1의 모든 k에 &lt의 문자열τ{\displaystyle \tau};τ{\displaystyle k<, \tau}(τ의 길이{\displaystyle \tau}), τ{\displaystyle \tau}의 k{k\displaystyle}번째 요소 확대되고 있다.yle k\ $S$ 그 이외의 경우는 0 입니다.예를 들어, S $S=\{1,3,4,7,\ldots \}$ { $S=\{1,3,4,7,\ldots \}$ , $S=\{1,3,4,7,\ldots \}$ , $S=\{1,3,4,7,\ldots \}$ 4, $S=\{1,3,4,7,\ldots \}$ , $S=\{1,3,4,7,\ldots \}$ $}$ { $displaystyle$ S = \ { 1 $, 3, 4$ , 7, \ $ldots \$ } $W$ $S=\{1,3,4,7,\ldots \}$ 、 $01011001 {$ $display style \$ $display }$ 이 $\tau$ $\tau$ $($ ) $Wstyle$ 에 $속하는지$ 확인합니다 $.$ tau $}$ 이 $\tau$ (가) $"\displaystyle\tau"$ $\tau$ 가W {\ $displaystyle$ W $W$ 에 $\tau$ 속하지 않는지 여부를 판별할 수 없습니다.

이제 라이스의 ^[4]^[5]정리에 대한 다음과 같은 유사점을 말할 수 있다.

재귀 집합의 $클래스$ W(\ $displaystyle$ W $)$ 는 $W$ 재귀 집합 $(\$ 과 $T_{0}$ 재귀 집합 $(\$ 1})이 $T_{1}$ T에서 문자열을 확장하도록 재귀 집합 T0(\displaystyle T_{0})을 재귀 집합 $T_{0}\cup T_{1}$ (\displaystyle T_{1})에 재귀 $T_{1}$ 이 있는 경우에만 계산할 수 있습니다. $T_{0}\cup T_{1}$ $T_{0}\cup T_{1}$ $T_{0}\cup T_{1}$ 1 (\ $displaystyle T_{$ 0}\ $cup$ T_ ${1$

이 결과는 컴퓨터 사회 선택의 근본적인 문제(더 넓게는 알고리즘 게임 이론)에 적용되었다.예를 들면, 쿠마베씨와 미하라씨는^[5]^[6], 협동 게임 이론이나 사회 선택 이론의 심플 게임의 나카무라 번호의 조사에 이 결과를 적용하고 있다.

「」를 참조해 주세요.

메모들

^ Soare, Robert I. (1987). Recursively Enumerable Sets and Degrees. Springer. p. 21. ISBN 9780387152998.
^ $S\subseteq \mathbb {N}$ = $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ e : $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ dom $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ e : $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ { $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ : $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ e ( $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ ) $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ { $display style$ S = $W$ _ { e } = { $displaystyle S$ = W _ { dom} \ $phi$ _ { $e$ }일 경우 집합 S $S\subseteq \mathbb {N}$ N { $displaystyle$ S $\s$ \subseteq \ $mathb { N }$ 은 $S\subseteq \mathbb {N}$ 재귀적으로 열거됩니다. $=\{x$ :\ $phi _{$ $e$ x $)\downarrow$ \} 일부 $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ $e$ 의 $W_{e}$ $We$ (\displaystyle $W_{$ e})는 도메인 ${\textrm {dom}}\,\phi _{e}$ e $(\$ displaystyle { $dom},\$ phi $W_{e}$ _ ${e})($ $($ x $)$ 를 $\phi _{e}(x)$ 하는 $x(\displaystyle$ x) $_$ 의 $x$ 입니다. $\phi$ _ ${e$ 반복 열거 가능한 집합의 결과는 (부분) 계산 가능 함수에 대한 결과에서 클래스 { $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ e : $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ e $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ C $}(\display$ \{\ $phi$ _ ${e}):$ $\textrm {dom},\phi$ _ ${e}\in$ C $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ $C$ 서 C $\displaystyle$ C는 $C$ 재귀적으로 열거할 수 있는 집합의 클래스입니다.
^ 재귀 열거 가능한 $S\subseteq \mathbb {N}$ S $S\subseteq \mathbb {N}$ N \ $displaystyle$ S $\subseteq \mathbb {N}$ 은 $S\subseteq \mathbb {N}$ $,$ 그 보수가 재귀 열거 가능한 경우에 재귀적이다.마찬가지로 특성 함수를 계산할 수 있는 경우 S{\ $displaystyle$ S $}$ 는 $S$ 재귀적입니다.
^ Kreisel, G.; Lacombe, D.; Shoenfield, J. R. (1959). "Partial recursive functionals and effective operations". In Heyting, A. (ed.). Constructivity in Mathematics. Studies in Logic and the Foundations of Mathematics. Amsterdam: North-Holland. pp. 290–297.
^ ^a ^b Kumabe, M.; Mihara, H. R. (2008). "Computability of simple games: A characterization and application to the core". Journal of Mathematical Economics. 44 (3–4): 348–366. arXiv:0705.3227. doi:10.1016/j.jmateco.2007.05.012. S2CID 8618118.
^ Kumabe, M.; Mihara, H. R. (2008). "The Nakamura numbers for computable simple games". Social Choice and Welfare. 31 (4): 621. arXiv:1107.0439. doi:10.1007/s00355-008-0300-5. S2CID 8106333.

레퍼런스

Hopcroft, John E.; Ullman, Jeffrey D. (1979), Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, pp. 185–192
Rice, H. G. (1953), "Classes of recursively enumerable sets and their decision problems", Transactions of the American Mathematical Society, 74 (2): 358–366, doi:10.1090/s0002-9947-1953-0053041-6, JSTOR 1990888
Rogers, Hartley Jr. (1987), Theory of Recursive Functions and Effective Computability (2nd ed.), McGraw-Hill, §14.8

외부 링크

Weisstein, Eric W. "Rice's theorem". MathWorld.

[1] Soare, Robert I. (1987). Recursively Enumerable Sets and Degrees. Springer. p. 21. ISBN 9780387152998.

[2] $S\subseteq \mathbb {N}$ = $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ e : $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ dom $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ e : $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ { $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ : $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ e ( $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ ) $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ { $display style$ S = $W$ _ { e } = { $displaystyle S$ = W _ { dom} \ $phi$ _ { $e$ }일 경우 집합 S $S\subseteq \mathbb {N}$ N { $displaystyle$ S $\s$ \subseteq \ $mathb { N }$ 은 $S\subseteq \mathbb {N}$ 재귀적으로 열거됩니다. $=\{x$ :\ $phi _{$ $e$ x $)\downarrow$ \} 일부 $S=W_{e}:={\textrm {dom}}\,\phi _{e}:=\{x:\phi _{e}(x)\downarrow \}$ $e$ 의 $W_{e}$ $We$ (\displaystyle $W_{$ e})는 도메인 ${\textrm {dom}}\,\phi _{e}$ e $(\$ displaystyle { $dom},\$ phi $W_{e}$ _ ${e})($ $($ x $)$ 를 $\phi _{e}(x)$ 하는 $x(\displaystyle$ x) $_$ 의 $x$ 입니다. $\phi$ _ ${e$ 반복 열거 가능한 집합의 결과는 (부분) 계산 가능 함수에 대한 결과에서 클래스 { $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ e : $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ e $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ C $}(\display$ \{\ $phi$ _ ${e}):$ $\textrm {dom},\phi$ _ ${e}\in$ C $\{\phi _{e}:{\textrm {dom}}\,\phi _{e}\in C\}$ $C$ 서 C $\displaystyle$ C는 $C$ 재귀적으로 열거할 수 있는 집합의 클래스입니다.

[3] 재귀 열거 가능한 $S\subseteq \mathbb {N}$ S $S\subseteq \mathbb {N}$ N \ $displaystyle$ S $\subseteq \mathbb {N}$ 은 $S\subseteq \mathbb {N}$ $,$ 그 보수가 재귀 열거 가능한 경우에 재귀적이다.마찬가지로 특성 함수를 계산할 수 있는 경우 S{\ $displaystyle$ S $}$ 는 $S$ 재귀적입니다.

[4] Kreisel, G.; Lacombe, D.; Shoenfield, J. R. (1959). "Partial recursive functionals and effective operations". In Heyting, A. (ed.). Constructivity in Mathematics. Studies in Logic and the Foundations of Mathematics. Amsterdam: North-Holland. pp. 290–297.

[kumabe-m08jme-5] Kumabe, M.; Mihara, H. R. (2008). "Computability of simple games: A characterization and application to the core". Journal of Mathematical Economics. 44 (3–4): 348–366. arXiv:0705.3227. doi:10.1016/j.jmateco.2007.05.012. S2CID 8618118.

[6] Kumabe, M.; Mihara, H. R. (2008). "The Nakamura numbers for computable simple games". Social Choice and Welfare. 31 (4): 621. arXiv:1107.0439. doi:10.1007/s00355-008-0300-5. S2CID 8106333.

[1]

[2]

[3]

[4]

[5]

[6]

Search

라이스의 정리

네임스페이스

더

목차

서론

형식적 진술

예

클라인의 재귀정리에 의한 증명

정지된 문제를 줄임으로써 입증

프루프 스케치

정식 증명

라이스의 정리 및 지수 집합

재귀집합에 대한 라이스의 정리 유사체

「」를 참조해 주세요.

메모들

레퍼런스

외부 링크

Search

라이스의 정리

서론

형식적 진술

예

클라인의 재귀정리에 의한 증명

정지된 문제를 줄임으로써 입증

프루프 스케치

정식 증명

라이스의 정리 및 지수 집합

재귀집합에 대한 라이스의 정리 유사체

「 」를 참조해 주세요.

메모들

레퍼런스

외부 링크

「」를 참조해 주세요.