이것이 잘못된 튜링 머신 인 이유는 무엇입니까?

Question

시험 개정을 수행하는 동안 Sipser의 "계산 이론 소개"에서 다음 질문에 답하는 데 어려움이 있습니다. 불행히도이 질문에 대한 해결책은 없습니다.

다음이 합법적 인 튜링 머신이 아닌 이유를 설명하십시오.

m = {

입력은 변수 x1, ..., xn에 대한 다항식 P입니다.

1. x1, ..., xn to Integer 값의 가능한 모든 설정을 시도해보십시오.
2. 이 모든 설정에서 P를 평가하십시오
3. 이러한 설정 중 하나가 0으로 평가되면 수락하십시오. 그렇지 않으면 거부하십시오. }

이것은 나를 미치게합니다! 정수 세트가 무한대라고 생각합니까? 이것은 어떻게 든 알파벳의 허용 크기를 초과합니까?

Answer 1

이것은 튜링 머신을 묘사하는 비공식적 인 방법이지만 문제는 다음 중 하나라고 말하고 싶습니다.

• otherwise reject - 나는 그것에 대해 Welbog에 동의합니다. 가능한 무한한 설정 세트가 있으므로 기계는 0으로 평가하는 설정이 여전히 올 것인지 여부를 알 수 없으며, 그러한 설정이 발생할 때만 찾을 수없는 경우 영원히 루프 할 수 있습니다. 기계가 멈출 수 있습니다. 마지막 진술은 쓸모없고 결코 사실이 될 수 없습니다. 물론 기계를 유한 한 정수 세트로 제한하지 않는 한.

• 코드 순서 :이 유사 코드를 "가능한 모든 설정을 적어 놓은 다음 각각에 대한 P를 평가하는"것으로 읽습니다. 문제가 있습니다. 다시 말하지만, 첫 번째 부분조차 끝나지 않을 수있는 무한한 설정 세트를 가질 수 있습니다. 다음 단계를 기록하고 계속하는 마지막 설정은 없기 때문입니다. 이 경우, 기계가 "0 설정이 없다"고 말할 수는 없지만, 찾기 위해 평가를 시작할 수는 없습니다. 이것은 정수 세트를 제한하여 해결 될 것입니다.

어쨌든, 나는 문제가 알파벳의 크기라고 생각하지 않습니다. 정수는 10 진수 / 이진 / 등으로 작성할 수 있기 때문에 무한 알파벳을 사용하지 않을 것입니다.

Answer 2

나는 튜링 머신에 약간 녹슬었지만, 당신의 추론이 옳다고 생각합니다. 즉, 정수 세트는 무한대이므로 모든 것을 계산할 수는 없습니다. 그래도 이론적으로 증명하는 방법을 잘 모르겠습니다.

그러나 튜링 머신을 둘러싼 가장 쉬운 방법은 "실제 컴퓨터가 계산할 수있는 모든 것, 튜링 머신도 계산할 수있는 것"을 기억하는 것입니다. 따라서 다항식이 주어지면 3 가지 질문을 해결할 수있는 프로그램을 작성할 수 있다면 튜링 머신을 찾을 수 있습니다.

Answer 3

문제는 마지막 부분이라고 생각합니다. otherwise reject.

에 따르면 계산 된 세트 기본 사항, 셀 수있는 세트의 벡터 공간은 그 자체로 셀 수 있습니다. 귀하의 경우에는 크기의 정수 위에 벡터 공간이 있습니다. n, 계산할 수 있습니다. 따라서 정수 세트는 계산할 수 있으므로 모든 조합을 시도 할 수 있습니다. (즉, 조합이 없으면 말합니다.)

또한 결과를 계산합니다 p 주어진 입력 세트에서도 가능합니다.

그리고 언제 수락 상태에 입력 p 0으로 평가하는 것도 가능합니다.

그러나 무한한 수의 입력 벡터가 있으므로 절대 입력을 거부하십시오. 따라서 튜링 머신은 질문에 정의 된 모든 규칙을 따를 수 없습니다. 마지막 규칙이 없으면 가능합니다.