두 개의 숫자를 더하는 튜링 기계

Question

#로 분리 된 두 개의 2 진수 합계를 계산하는 Turing Machine을 어떻게 만들 수 있습니까? 111 # 101B, 여기서 B는 공백입니까? 결과는 테이프 끝에 쓸 수 있습니다.

Answer 1

1. 두 이진수를 단항으로 변환하는 튜링 기계를 작성하십시오 (둘 사이에 공백을 유지하십시오).
2. 공백을 1로 바꾸고 끝에서 숫자를 자르도록 튜링 기계를 작성하십시오.
3. 튜링 기계를 작성하여 단항수를 2 진수로 변환하십시오.
4. 세 대의 기계를 함께 연결하십시오.

Answer 2

초등 학교에서 번호를 추가하는 방법을 배웠습니다. 같은 것을 여기서 구현하십시오. 순진한 접근 방식으로, 이것은 2 차 시간에 있습니다.

더욱 빨라질 수 있습니다.