[알고리즘] TM transition function (halting, crashing, looping)

(2021.12.07)

알고리즘 수업 들으면서 정리하기 24탄

 

w14-2, w14-3 녹강 정리

TM transition function, crashing, halting 에 대해 배웠다

저번 실강이랑 겹치는 내용이 많아서 정리할 내용이 거의 없다

---

 

 

TM transition function

 

출처: 교수님 강의노트

(여기서 Q의 정의부분이 틀렸다. halt 를 포함하지 않는다고 되어있는데 halt state도 포함한다)

 

 

이렇게 표현할 수 있다

 

 

 

example)

 

 

 

 

 

Processing a string

> string의 가장 왼쪽과 가장 오른쪽에는 blank symbol을 두고, blank가 아닌 string의 가장 첫번째 cell에 tape head를 두고 과정을 진행한다.

> input string w에서 transition 과정이 진행되어 final state까지 도달하면, 해당 input string w는 TM에 의해서 accepted 된다고 말한다.

> 위의 예시 TM에서는 w=0011이 TM에 의해 accepted 된다고 할 수 있음

 

 

Halting

 

 

 

crashing과 looping