0
즉, 튜링 기계가 공식 시스템 S를 입력으로 사용하여 S가 튜링 완료인지를 결정할 수 있습니까?튜링 기계가 정식 계산 모델이 튜링 완료인지 결정할 수 있습니까?
이것이 결정 불가능한 문제라고 생각합니다. 맞습니까?
결정 불가능한 경우 왜 우리는 (인간으로서) 튜링의 완전성을 결정할 수 있습니까?
A
답변
0
흠 :-) 튜링의 완전성을 결정하는 것은 인간의 두뇌가 완전한 TM인지 아닌지를 결정하는 데 중요하지 않습니다. 하나는 기계적 단계를 거쳐 완성도를 결정할 수 있습니다. 그것은 문제가되지 않습니다.
인간의 두뇌가 과도한 계산인지 또는 하이퍼 튜링인지 여부는 중요한 문제입니다.
하나의 테스트는 다음 질문 중 하나에 "예"라고 대답하는 것입니다. 인간이 튜링 기계가 멈출 때를 예측할 수 있습니까? (즉, 정지 문제를 푸십시오) 또는 인간의 두뇌가 라이스의 정리에 종속되지 않습니다.
무한히 긴 테이프가있는 TM을 상상할 수 있기 때문에 일반적으로 두 질문에 대한 대답이 아니오 인 것처럼 보입니다. 멈추라는 말을 셀에 부딪 힐 때를 알 수는 없기 때문입니다.
우리가 정상적인 컴퓨터/소프트웨어/기계 프로세스 등을 TM으로 착각 한 것처럼 보이는 하이퍼 컴퓨팅 기능이 있습니다.
라이스의 정리는 마르코프 속성을 나타내는 시스템의 "특별한 경우"에서 사이드 스텝핑 될 수 있으며 한정된 수의 장소 전환 그물 표현을 갖습니다. 우리의 일반적인 환경은 이러한 "특별한 경우"를 풍부하게 가지고 있기 때문에 인간의 두뇌가 하이퍼 컴퓨팅을 할 수있는 것처럼 보일 수 있습니다. 특별한 경우의 일반적인 결론으로 넘어 가기 쉽기 때문에 하이퍼 컴퓨팅이 가능할 수도 있습니다. 튜링 머신과의 상호 작용을 경험하십시오.
인간 (인간)도 알고리즘 중지에 대한 증명을 제공 할 수 있습니다. "어떤 경우에는 해결할 수 있다고해서 모든 경우에 해결할 수 있다는 것을 의미하지는 않습니다."라는 사실을 깨달을 필요가 있습니다. 일부 사례에 대해서는 중단 문제를 결정할 수있는 프로그램을 작성할 수도 있지만 결정 불가능하다는 것은 임의의 알고리즘에서 작동하는 일반적인 알고리즘이 존재하지 않는다는 것입니다. – Cruncher