계산할 수없는 계산 가능한 집합이 있습니까? 계산 가능한 집합은 계산할 수

세트는 자연수와 함께 bijection 이 있는 경우 셀 수 있으며 멤버를 열거하는 알고리즘이있는 경우 계산 가능합니다 (ce) .

열거 할 수없는 계산 가능한 집합은 계산할 수 있어야합니다.

계산할 수없는 계산 가능한 집합의 예가 있습니까? 즉,이 세트와 자연수 사이에 궤적이 존재하지만이 궤적을 계산할 수있는 알고리즘은 없습니다.

답변

열거 할 수없는 셀 수있는 집합의 예가 있습니까?

예. 자연수의 모든 부분 집합은 셀 수 있지만 모두 열거 할 수는 없습니다. (증명 : 하위 집합은 셀  수없이 많지만 열거 자 역할을 할 수있는 수많은 Turing 머신 만 있습니다.) 이미 알고 있는 하위 집합은  재귀 적으로 열거 할 수 없습니다. 모든 입력에 대해 정지하는 튜링 기계를 코딩하는 모든 숫자의 집합으로.

N

N

답변

예, 모든 결정 불가능한 (반 결정 불가능한) 언어에는이 속성이 있습니다.

예를 들어, 세트 에서 정지되지 않는  것을 고려하십시오 .

L={(x,M)∣M does not halt on input x}

이 세트의 멤버를 열거 할 수있는 알고리즘이 있다고 가정하십시오. 이러한 알고리즘이 존재 하면 다음 알고리즘을 사용하여 입력 의 정지 문제를 해결하는 데 사용할 수 있습니다 .

x,M
  • x 에서 n 단계 동안 머신 을 실행 하고 L 의 n 번째 멤버를 열거하는 것의 대안 .
    M

    n

    x

    n

    L

은 중단되거나 x에서 중단되지 않습니다. 정지하면 결국정지 상태에 도달하는 n 을 찾습니다. 멈추지 않으면 결국열거에서 ( M , x ) 에도달합니다.

M

x

n

(M,x)

따라서 우리는 축소가 있으며 그러한 열거가 존재하지 않는다고 결론 내릴 수 있습니다.

이러한 결정은 반 결정 가능한 문제에 대해 존재할 수 있습니다. 예를 들어, 단계 후 모든 Turing Machine 실행의 모든 ​​가능한 추적을 열거하여 모든 중지 시스템 입력 쌍 세트를 열거 하고 정지 상태로 끝나지 않는 항목을 필터링 할 수 있습니다.

n

답변

계산 이론에서 우리는 , Σ = { 0 , 1 }의 부분 집합을 다룬다 . 이 언어는 셀 수없이 무한하므로 모든 하위 집합 L ⊆ Σ ∗ 는 셀 수 있습니다. 또한, 보충은 재귀 적으로 열거 할 수없는 많은 결정 불가능하지만 재귀 적으로 열거 가능한 언어가 있습니다. 이 언어는 Σ *의 하위 집합 이므로 계산할 수 있습니다.

Σ∗

Σ={0,1}

L⊆Σ∗

Σ∗

답변