제10장. Other Models of TM’s 학습목표 TM의 다양한 변형모델을 이해, Universal TM과 Linear Bounded Automata를 통하여 TM의 가능성 확인

개요 TM의 다양한 변형들 - Stay-option, Semi-infinite tape, Off-line tape 보다 강력한 Tape구조를 갖는 TM들 - Multi-tape, Multidimensional tape Nondeterministic TM Universal TM - Reprogrammable (general) TM Linear Bounded Automata - Tape사용에 제약을 가한 TM  그래 봐야 모두 같다!  뛰어봐야 벼룩! 이건 좀 이상해 보이지만 그래도 같다

Minor 변형 TM들 먼저 두 TM이 같음을 formal하게 정의합시다 그냥 적용하기는 좀 애매하니 택한 방법이  Simulation 자, 이제 TM의 변형과 그것이 power는 같음을 확인합시다

TM with a Stay-Option 변형 TM-1 Move할 때마다 헤드를 옮겨야 하는게 좀…  이거 앞에서 한번 본 것 같죠! cf) TM with multiple tracks = each tape symbol can be a composite of characters a b c Track 1 Track 2 Track 3

TM with Semi-Infinite Tape 테이프의 한쪽 끝으로만 무한히 쓸 수 있다면… Idea : partitioning the states into two parts → QU and QL b a Reference point # a b

Off-Line TM 변형 TM-3 입력용 테이프가 따로 있다면… Idea : using input file CU a b c 1 CU e f Tape a b c d Read-only input file g

Homework : Exercises 10.1 여러 가지 변형에 대한 연습문제가 주로인데, 모두 할 필요는 없고, 5번 9번 정도를 그냥 해봅시다.

Multitape TM’s TM with More Complex Storage q0 a b c d e f Tape 1  multi-track tape을 사용하면 간단히 해결!  왔다리 갔다리 하지 않고도 쉽게 해결이 가능하네요

Multidimensional TM’s TM with More Complex Storage 2D address scheme 1, -1 1, 1 1, 2 -1, 1 a 2 1 # b - 3

Homework : Exercises 10.2 전체적으로 detail한 유도가 까다로운 문제들이므로 기본 정의로부터 새로운 정의를 유도할 수 있는지 확인하는 정도에서 끝냅시다.

Nondeterministic TM (1) 이제까지의 경험에 의하면 이런 식의 nondeterminism이 해당 오토메타의 power에 영향을 끼칠 수도 있을텐데…

Nondeterministic TM (2) 실제로 TM의 경우에는 power에 영향을 못 미친다 Nondeterministic TM (2) # a q0 # a b c q1 q2

Homework : Exercises 10.3 3 : Nondeterministic solution이 훨씬 간단하게 얻어질 수 있음을 확인 4 : 세 부분으로 나누고 매칭을 시도

Universal TM 범용 컴퓨터로서의 TM으로 확장  인코딩 약속 필요 reprogrammable TM for general purpose machines Mu simulates the computation of M on w Standard way of describing TM CU (Mu) Description of M Tape contents of M Internal states of M

Set Theory : Countable 모든 TM이 0과 1의 스트링으로 표현된다는 사실  일반적 특성 유도 countable : 1-1 correspondence with positive integers ordering Countable이 아닌가? 아! 순서를 바꾸니 countable이네! if we can write the elements in some sequence → enumeration procedure

TM : Countable

Homework : Exercises 10.4 이 절의 내용도 따로 연습을 할 정도는 아니지만 7번 8번 정도의 문제를 해봅시다.

Linear Bounded Automata restriction : only a finite part of tape → FA only the part of tape occupied by input → LBA

LBA : 예 [ a a a a a a ] a’s [ a a a ] divisor (scratch space)

Homework : Exercises 10.5 LBA > PDA LBA 로 accept할 수 없는 L ? TM으로 accept할 수 없는 L ? 4(d) 4(e) 정도를 한번 해봅시다.