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

예를 들어, 세트 에서 정지되지 않는  것을 고려하십시오 .L={(x,M)∣M does not halt on input x}

$L = \{(x,M) \mid M \text{ does not halt on input } x \}$

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

$x,M$

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

  $M$n

  $n$

  $n$x

  $x$

  $x$n

  $n$

  $n$L

  $L$

  $L$

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

$M$x

$x$n

$n$(M,x)

$(M,x)$

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

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

$n$

답변