나는 확신 할 수없는 문제에 직면했다. 호기심 때문에, 다음과 같이 묻고 싶었습니다 :튜링 기계가 튜링 기계가 처리 할 수없는 문자열을 중단하고 암시 적으로 허용 할 수 있습니까?
나는 튜링 기계가 처리 할 수없는 문자열을 암시 적으로 거부 할 수 있다고 확신하지만 그 보완을 할 수 있습니까? 즉, 을 암시 적으로 처리 할 수없는 입력 인을 수락 할 수 있습니까? 이것이 어리석은 질문이라면 사과드립니다. 나는 이것에 대한 답을 찾지 못하는 것 같습니다.
그건 바보 같은 질문이 아니에요! "처리 할 수없는 문자열"은 실제로 "유효한 형식이 아닌 문자열"입니다.이 문자열은 "우리가 모르는 기호가 포함 된 문자열"을 의미합니다. (나는 this presentation의 슬라이드 14에서 벗어날 것이고, 이는 단지 인터넷 검색 Turing 'implicitly reject'으로 만 알 수있다.)
그런 정의를 사용한다면 유효한 세트에없는 심볼을 포함하고있는 입력을 받아들이는 튜링 기계를 간단하게 만들어야합니다.
예, "처리 할 수없는 문자열"에 대한 다른 가능한 해석이 있지만, 이것이 의미하는 것이 확실합니다. 그것은 분명히 제약이없는 정의가 될 수 없었습니다. 그렇지 않으면 "멈출 수있는 프로그램을 나타내는 문자열"처럼 "처리 할 수없는 문자열"을 정의 할 수있었습니다. 중단 문제를 해결했을 것입니다! (또는 중단 문제에 익숙하지 않은 경우 NP 완전 문제로 대체 할 수 있습니다.)
문자열을 거부하는 Turing 머신이 처리 할 수없는 이유는 처음부터 도입 된 것이기 때문에 모든 입력에 기계를 잘 정의 할 수 있다고 생각합니다. 예를 들어, "apple source"와 같은 bianry 번호가 아닌 입력 값을 전달할 경우, 바이너리 수를 3로 나눌 수있는 튜링 기계가 있다면, 출력에 대해서도 여전히 이유가 있습니다 프로그램의