Turing Machine은 Input을 Accept·Reject하는 장치뿐 아니라 Output을 계산하는 Transducer로 사용할 수 있다. Algorithm은 본질적으로 Input과 Output 사이의 함수 관계를 계산하므로 이 관점이 실제 Programming과 더 직접적으로 연결된다.
함수 계산
함수
에 대해 TM이 모든 Input 에서 Halt하고 Tape에 를 남기면 를 Turing-computable 또는 Computable Function이라고 한다.
어떤 Input에서는 정의되지 않을 수 있는 함수는 Partial Function이다. 정의역의 모든 Input에서 Halt하면 Total Computable Function이다.
Encoding
TM은 String만 직접 다루므로 숫자, Graph, Program 같은 대상을 String으로 Encoding해야 한다.
- Unary Encoding: 자연수 을 으로 표현한다.
- Binary Encoding: 일반적인 Binary Representation을 사용한다.
- 여러 값을 구분하려면 Separator 등을 사용한다.
Encoding은 유일하게 Decoding 가능해야 한다.
예제: Unary Addition
Input을
으로 Encode하고 Output을
으로 만든다고 하자.
간단한 Algorithm은 Separator 를 지우고 오른쪽 Block을 한 칸 왼쪽으로 이동하는 것이다. 또는 를 1로 바꾸고 전체 끝의 1 하나를 지우면 합의 길이를 맞출 수 있다.
예제: Binary Increment
Binary Number에 1을 더하려면 오른쪽 끝으로 이동한 뒤 Carry를 처리한다.
- 오른쪽 끝 Blank까지 이동한다.
- 왼쪽 Symbol이 0이면 1로 바꾸고 Halt한다.
- 1이면 0으로 바꾸고 왼쪽으로 Carry를 계속한다.
- 가장 왼쪽까지 모두 1이었다면 새 1을 추가한다.
예를 들어
이다.
Acceptor와 Transducer 관계
Language 의 Characteristic Function을
로 정의한다. 이 Decidable이면 은 Total Computable이다. 반대로 을 계산할 수 있으면 결과로 Membership을 판정할 수 있으므로 은 Decidable이다.
Multi-output와 Tape Convention
Output은 같은 Tape에 남길 수도 있고 별도의 Output Tape를 사용할 수도 있다. 표준 모델이 달라도 적절히 Simulation할 수 있으므로 계산 가능한 함수의 Class는 바뀌지 않는다.
Partial Computation
Recognizer를 함수 관점에서 보면 Member Input에서는 1을 출력하고 Non-member에서 정의되지 않은 Partial Function으로 볼 수 있다. Loop는 함수가 그 Input에서 Undefined인 상태에 대응한다.
정리
- TM은 Language를 판정하거나 String Function을 계산할 수 있다.
- 계산 대상은 먼저 String으로 Encoding한다.
- 모든 Input에서 Halt하면 Total Computable Function이다.
- Decidable Language와 Total Computable Characteristic Function은 서로 대응한다.
연습 문제
1번
Unary Input 에 Unary Addition Transducer를 적용한 Output을 구한다.
2번
Binary Increment Algorithm이 을 처리하는 과정을 설명한다.
풀이
1번
왼쪽 수는 3, 오른쪽 수는 2이므로 합은 5이다.
2번
오른쪽부터 모든 1을 0으로 바꾸며 Carry가 왼쪽 끝을 넘어간다. 맨 앞에 1을 추가하므로
이다.