Turing Machine이 Language를 처리한다고 해도 Non-member Input에서 반드시 결과를 내는지는 별개의 문제이다. 이 차이에 따라 Turing-recognizable과 Decidable Language를 구분한다.
Turing-recognizable Language
Language 에 대해 TM 이 다음을 만족하면 을 Recognize한다고 한다.
- 이면 은 를 Accept한다.
- 이면 은 Reject하거나 영원히 Loop할 수 있다.
이러한 Language를 Turing-recognizable, Recursively Enumerable(RE)라고 한다.
Decidable Language
TM 가 모든 Input에서 Halt하고
- 이면 Accept
- 이면 Reject
하면 를 Decider라고 하고 을 Decidable 또는 Recursive Language라고 한다.
모든 Decider는 Recognizer이지만 모든 Recognizer가 Decider인 것은 아니다.
Complement와 Decidability
이 Decidable이면 Accept와 Reject를 뒤집어 의 Decider를 만들 수 있다. 따라서 Decidable Language는 Complement에 닫혀 있다.
Recognizer는 Non-member에서 Loop할 수 있으므로 단순히 Accept와 Reject를 뒤집으면 Complement Recognizer가 되지 않는다.
양쪽이 Recognizable이면 Decidable
중요한 정리이다.
오른쪽 방향은 Complement Closure로 분명하다. 왼쪽 방향은 의 Recognizer 과 의 Recognizer 를 Input 에 대해 병렬로 Simulation한다.
- 을 한 Step 실행한다.
- 를 한 Step 실행한다.
- 반복한다.
- 이 Accept하면 Accept하고 가 Accept하면 Reject한다.
는 둘 중 정확히 하나에 속하므로 하나의 Machine은 결국 Accept한다. 이 방식을 Dovetailing이라고 한다.
예제: DFA Acceptance
는 Decidable이다. DFA를 Description에서 복원하고 의 각 Symbol에 대해 Transition을 한 번씩 Simulation하면 반드시 유한 시간에 종료한다.
예제: TM Acceptance
는 Turing-recognizable이다. 을 에서 Simulation하여 Accept하면 Accept한다. 그러나 이 Reject하거나 Loop하는 경우를 일반적으로 모두 유한 시간에 구분할 수 없으므로 Decidable하지 않다.
언어와 Machine Description
Machine 자체를 Input으로 주려면 유한 String으로 Encoding한다. 는 TM Description과 Input을 함께 Encoding한 String을 뜻한다. Universal Turing Machine은 Description을 읽고 다른 TM을 Simulation한다.
정리
- Recognizer는 Member Input에서만 Halt·Accept가 보장된다.
- Decider는 모든 Input에서 Halt한다.
- Decidable Language는 Complement에 닫혀 있다.
- , 이 모두 Recognizable이면 Dovetailing으로 Decide할 수 있다.
연습 문제
1번
어떤 TM이 Member Input에서는 Accept하고 Non-member Input에서는 항상 Loop한다. 이 Machine은 Recognizer인지 Decider인지 판단한다.
2번
과 의 Recognizer를 순서대로 하나씩 완전히 실행하는 방식이 Decider를 만들지 못하는 이유를 설명한다.
풀이
1번
의 Recognizer이지만 Non-member에서 Halt하지 않으므로 Decider는 아니다.
2번
첫 번째 Recognizer가 Input에 대해 Loop하면 두 번째 Recognizer를 영원히 시작하지 못한다. 두 Machine을 한 Step씩 번갈아 실행하는 Dovetailing이 필요하다.