언어 L={<M>, M은 유한한 양의 단어를 허용합니다}가 결정 가능합니까?

Question

~이다 $ l = {u003CM> | l (m) is imite } $ 결정 가능?M은 TM입니다.

나는 쌀의 정리로 증명하는 것이 상대적으로 간단하다고 생각합니다.하지만 나는 라이스 정리를 사용하지 않는 해법에 관심이 있습니다.

내 시도는 다음과 같습니다.f(<m,w>)를 다음과 같은 방식으로 작동하는 함수로 둡니다.

1. M에서 w 실행
2. M이 T M 구성을 수락하는 경우which accepts only the word w and return M
3. M이 거부하는 경우 T M 구성which accepts everything. Return M

그래서 만약 내가 안에 있다면 $A_{TM}= \{<M,w>|M \ 허용 \ w\}$ 우리는 f(<m,w>)가 L에 있다는 것을 알고 있습니다.m이 A에 없으면 f(<m,w>)는 모든 단어를 허용하므로 무한한 단어를 허용한다는 것을 알 수 있습니다.따라서 f(<m,w>)는 L에 없습니다.

이것이 올바른 매핑 축소입니까?

Answer 1

정의한 기능은 전혀 축소되지 않습니다. 중지되지 않을 수도 있습니다!

문제가 실행 중입니다. $m$ ~에 $w$:확신할 수 있나요 $m$ 무한 루프에 갇히지 않을 것입니다. $w$?당신은 할 수 없습니다.

다음과 같이 적절한 축소를 정의할 수 있습니다.(입력시 $<m,w>$)

머신 생성 $M_{m,w}$이는 다음 알고리즘을 수행하고 다음을 반환합니다.(입력시 $s$)

1. 에뮬레이트 $m$ ~에 $w$ ~을 위한 $|s|$ 단계.만약에 $m$ 그 시간에 멈춰, 거절해 $s$.그렇지 않으면 수락하세요. $s$.

이것이 적절한 감소라는 것을 증명할 수 있도록 남겨두겠습니다. $H_{TM}$ 에게 $L$ (좋은 운동이에요!)