해결을위한 Oracle 호출 수의 하한 어렵지 않습니다. 로그( n + 1

나는 쉬운 운동 (아래 스포일러) 인 다음과 같은 질문에 직면했다.

우리는 주어진다 $n$

정지 문제의 사례 (즉, TM) $M_{1}, . . ., M_{n}$

M1,...,Mn

), 우리는 정확히 어느 것이 중단되는지 결정해야합니다. $ϵ$

. 즉, 우리는 출력해야합니다 ${i : M_{i} halts on ϵ}$

{i:Mi halts on ϵ}

. 중지 문제에 대한 오라클이 제공되지만 최소한의 횟수 만 사용해야합니다.

그것이 할 수 있음을 보여주는 것은 어렵지 않습니다. $\log (n + 1)$

log⁡(n+1)

전화.

내 질문은 : 우리는 하한을 증명할 수 있습니까? 그러한 경계를 찾기가 매우 어렵다고 의심 할만한 이유가 있습니까?

질문 자체에 대한 답변 (스포일러, 호버 마우스) :

의 경우를 고려 $3$
3
TM. TM을 만들 수 있습니다 $H_{2}$
H2
그 실행 $M_{1}, M_{2}, M_{3}$
M1,M2,M3
동시에 두 개 이상이 정지되면 정지합니다 (그렇지 않으면 멈춤). 마찬가지로 TM을 구성 할 수 있습니다 $H_{1}$
H1
그들 중 적어도 하나가 정지하면 정지합니다. 그런 다음 오라클을 호출 할 수 있습니다 $H_{2}$
H2
. 정지하면 머신을 병렬로 실행하고 정지 할 때까지 기다릴 수 있습니다. 그런 다음 마지막 오라클에서 오라클을 호출 할 수 있습니다. 오라클이 “아니오”라고 말하면 오라클을 실행합니다 $H_{1}$
H1
. 정지하면 기계가 정지 할 때까지 기계를 작동 시키며 정지하는 유일한 기계입니다. 만약 $H_{1}$
H1
멈추지 않으며, 아무도 멈추지 않습니다. 이것을 확장 $n$
n
기계는 쉽다.

이 질문에 대한 첫 번째 관찰은 정보 이론 도구를 사용하여 해결하는 것이 불가능 해 보인다는 것입니다. 오라클없이 기계를 실행하여 정보를 얻는 능력에 결정적으로 의존하기 때문입니다.

답변

결과는에서 찾을 수 있습니다

Beigel, R., Gasarch, WI, Gill, J. 및 Owings, J. Terse, superterse 및 verbose 세트 . 알립니다. 그리고 계산. 103 (1993), No. 1, 68 ~ 85 쪽.

그들의 증거는 실제로 당신의 문제를보다 적은 것으로 해결할 수 없다는 것을 보여줍니다 $\log_{2} n$

log2⁡n

모든 세트 에 대한 쿼리 $X$

멈춤 문제 자체는 물론이다. 일부 표기법의 경우 문제가 때때로 표시됩니다. $C_{n}^{K}$

CnK

또는 $C_{n}^{H A L T}$

CnHALT

(정지 문제에 대해 가장 좋아하는 표기법에 따라 다름).

이것과 많은 관련 결과는 다음을 참조하십시오.

Gasarch의 설문 조사
이 책 재귀 이론의 경계 쿼리 Gasarch와 마틴.

답변

편집 : 내가 대답 한 주장은 잘못이 아니었지만 약간 오해의 소지가 있었는데, 일부 는 상한이 타이트해야한다는 것을 보여주었습니다. $n$

(실제로는 빡빡해야하기 때문에 실제로는 사소합니다. $n = 2$

n=2

바운드는 1)입니다.

보다 정확한 주장은 다음과 같습니다. 상한의 경우 $\log_{2} n$

log2⁡n

어떤 특정에 대한 느슨한 $n$

그런 다음 모두 를 위해 $n$

필요한 오라클 호출 수는 $O (1)$

O(1)

(확실히 아닙니다 $O (1)$

O(1)

따라서 상한이 결코 풀리지 않습니다! 그러나 나는 실제로 여기에서 그것을 증명하지 못하고 문제에 대한 다른 대답을 고려할 때 추구 할 가치가없는 것 같습니다.)

최대 출력 을 계산 하는 문제를 고려하십시오 .

주어진 $n$
n
튜플 $(M_{1}, \dots, M_{n})$
(M1,…,Mn)
튜링 머신의 최대 출력을 계산합니다. $ϵ$
ϵ
). 정지 된 것이 없으면 0을 반환합니다.

의 기능으로 $n$

이 함수를 계산하는 데 필요한 최악의 Oracle 호출 수는 다음 중 어느 것을 결정하는 데 필요한 수와 같습니다. $n$

주어진 기계가 정지합니다. (어떤 기계가 정지했는지 아는 경우 최대 출력을 쉽게 계산할 수 있습니다. 반대로, 어떤 기계가 정지했는지 알고 싶다면 문제 설명의 구성에 따라 기계를 구성 할 수 있습니다 ${M_{i}^{'}}$

{Mi′}

$(i = 1, 2, \dots, n)$

(i=1,2,…,n)

어디 $M_{i}^{'}$

Mi′

모든 실행 $n$

주어진 기계를 병렬로 멈춘 후 정지 및 출력 $i$

만약 $i$

그들 중 이제까지 중단되었습니다. 최대 출력은 중단되는 숫자를 알려줍니다. 그로부터 정확히 어떤 정지를 계산할 수 있습니다.)

자 이제 $n_{0}$

가장 작은 정수이다 $n$

(있는 경우) 다음을 보유합니다.

사용 $C (n) = max {k \in Z : 2^{k} < n}$
C(n)=max{k∈Z:2k<n}
오라클 전화, 하나의 최대 출력을 계산할 수 주어진 기계. (즉, 상한은 대해 엄격하지 않습니다 .) $n$
n
$n$
n

이므로 분명히 입니다. 실제로, 이므로 이기도 하지만 (Oracle 호출없이) 지정된 시스템 의 최대 출력을 계산할 수 없습니다. 이제 더 큰 고려하십시오 . $n_{0} > 1$

n0>1

$C (1) = - 1$

C(1)=−1

$n_{0} > 2$

n0>2

$C (2) = 0$

C(2)=0

$2$

$n$

제 : 경우 유한하고, 임의의에 대해 , 하나의 최대 출력을 계산할 수 에서 주어진 시스템 오라클 전화. $n_{0}$

$n$

$C (n_{0})$

C(n0)

( 이 유한이면 입니다.) $n_{0}$

$C (n_{0}) = O (1)$

C(n0)=O(1)

증명. . 우리는 에 유도함으로써 그것을 증명합니다 . 기본 사례는 이며 과 정의로 유지됩니다 . $n$

$n \leq n_{0}$

n≤n0

$n_{0}$

$C$

하자 주어진, 그 TM 될 튜링 기계만을 사용하여 최대 출력을 계산 오라클 호출한다. $Q_{0}$

$n_{0}$

$C (n_{0})$

C(n0)

수정하십시오 . 머신 주어지면 다음과 같이 최대 출력을 계산하십시오. $n > n_{0}$

n>n0

$n$

$M_{1}, \dots, M_{n}$

M1,…,Mn

첫 번째 기계에 . 실행 고려 다음에 기계. 참고 것을 하게 오라클을 호출하고, 거기에만 이러한 호출에 오라클 가능한 응답. 정의상 입니다. 하자 나타 일 수 응답. 각 , 건설 기계
시뮬레이션 다음과 같이 이들 머신을 : $M_{1}, \dots, M_{n_{0}}$

M1,…,Mn0

$Q_{0}$

$n_{0}$

$Q_{0}$

$C (n_{0})$

C(n0)

$n^{'} = 2^{C (n_{0})}$

n′=2C(n0)

$n^{'} = 2^{C (n_{0})} < n_{0}$

n′=2C(n0)<n0

$o_{i}$

$i$

$i = 1, \dots, n^{'}$

i=1,…,n′

$M_{i}^{'}$

Mi′

$Q_{0}$

TM (입력 ) : $M_{i}^{'}$
Mi′
$ϵ$
ϵ

시뮬레이션 온 기계 , 대신 오라클를 호출에 따라 오라클 응답을 가정 . $Q_{0}$ $n_{0}$ $(M_{1}, \dots, M_{n_{0}})$ $o_{i}$

이 시뮬레이션은 중단되지 않을 수 있습니다 (예 : 가 오라클이 실제로 반환하는 것이 아닌 경우 ). $o_{i}$

시뮬레이션이 멈추는 경우,하자 있는 최대 출력 될 주어질 것이라고 말했습니다. $h_{i}$ $Q_{0}$

모든 머신을 더브 테일하십시오 . 그중 하나가 출력하면 를 중지하고 출력 . $n_{0}$ $(M_{1}, \dots, M_{n_{0}})$ $h_{i}$ $h_{i}$

이제 주어진 머신 순서 에서 첫 번째 머신 을 이러한 머신 . 이 기계 순서에서 하여 계산 된 값을 리턴하십시오 . (오라클은 되풀이하기 전에 호출되지 않으므로 오라클은 기본 사례에 도달 한 후에 만 호출됩니다.) $n$

$n_{0}$

$M_{1}, \dots, M_{n_{0}}$

M1,…,Mn0

$n^{'} < n_{0}$

n′<n0

$M_{1}^{'}, \dots, M_{n^{'}}^{'}$

M1′,…,Mn′′

$n - (n_{0} - n^{'}) < n$

n−(n0−n′)<n

이 계산이 올바른 이유는 다음과 같습니다. 들어 되도록 오라클에 의해`올바른 '응답 인 쿼리에, 멈추고 원래의 정확한 최대 출력을 제공 할 기계. 따라서 기계 의 최대 출력
은 최소한 기계 의 최대 출력 입니다. 반면 4 단계에서는
가 의 최대 출력보다 큰 출력을 제공 할 수 없습니다 . 따라서, 기계 의 최대 출력 $i$

$o_{i}$

$Q_{0}$

$M_{i}^{'}$

Mi′

$n_{0}$

$n^{'}$

n′

$(M_{1}^{'}, \dots, M_{n^{'}}^{'})$

(M1′,…,Mn′′)

$n_{0}$

$(M_{1}, \dots, M_{n_{0}})$

(M1,…,Mn0)

$M_{i}^{'}$

Mi′

$(M_{1}, \dots, M_{n_{0}})$

(M1,…,Mn0)

$n^{'}$

n′

$(M_{1}^{'}, \dots, M_{n^{'}}^{'})$

(M1′,…,Mn′′)

은 대체 하는 머신 의 최대 출력과 같습니다 . QED $n_{0}$

How IT

언제든지 물어보세요.

해결을위한 Oracle 호출 수의 하한 어렵지 않습니다. 로그( n + 1

답변

답변

답변