Hierarchy

Basic

Transducer

다른 Machine처럼 accepter 역할도 하지만, 함수역할의 transducer도 수행

• Encoding이 필요하다

---

9.3 Turing Thesis

digital computer가 할 수 있는 일은 TM이 모두 할 수 있다.

Ch10. Other models of TM

1. TM with stay
2. TM with multiple track tape
3. semi infinite tape
4. off line machine
5. 2-Dimensional TM

10.4 Universal TM

simulate하는 TM

Machine Encoding

• Tape 1
  State Encoding
• Tape 2
  Tape alphabet Encoding
• Tape 3
  Transition Encoding

with enumericable

Countable Sets

countable = enumeric
proper order도 가능 = 사전식 나열 = numeric