[컴퓨테이션 이론] Turing Machine 의 Decidable, Recognizable

인트로

본 글을 보시는 분께.

컴테 강의를 들으시나보군요..

(초록색 마크 학교이시다면)

시험은 꽤나 어렵게 나옵니다. 공부를 많이 하셔야 합니다.

~~(그러나 언제나 공부를 다하면 잘 볼 수 있다는게 학계의 정석이죠)~~

그럼, 화이팅하세요! :)

Turing machine의 Decidable, Recognizable

튜링머신(Turing maching) 은 멈추지 않을 수 있다(infinite 성질).

input이라는 것이 읽고 끝이 아니라,

수정하면서 왔다갔다 할 수 있어서 안 멈추고 동작할 수 있다.

Turing decidable은 꼭 멈춰야 되는것이고,

Turing recognizable은 멈추지 않아도 되는것이다.

Turing recognizable은 Turing decidable을 포함한다.

모든 string을 모아놓으면 ∑*이다.

turing machine에서accept state에 가면 accept하는 것이다.

그러나 reject하는 경우는,

'내 튜링머신이 reject state에 가서 reject합니다' 라고 할 수있지만,

멈추지 않고 계속 움직일 수 있다. (종료하지 않는 경우)

이 두 state를 계속 움직이면서

accept 도아니고, reject도 아닌 계속도는 경우가 발생한다.

왜 이런 얘기가 FA나 PDA에서는 없었나?

FA(Finite Automata)는 (종료하는 Automata)

input string을 맨끝까지 갔을 때까지 한칸 한칸 옆으로 가기때문에 어찌됐든 다 보면 끝나는것이다.

즉, input을 다 읽었다는 개념이 없다.

loop은 머신이 움직이지 않고 계속 움직이는 것을 말한다.

얘가 accept할것인지 아닌지 모르기때문에 일단 줘놓고 기다린다.

결국 이 string이 language안에 들어가는지 판단하는 것이 목표이다.

10시간을 기다려도 멈추지 않으면 reject라고 하는건가? 아니다.

~~11시간을 기다려야 되는지 12시간을 기다려야되는지 모른다.~~

그랬을 때,

그것이 reject할것인지 accept할것인지 모른다. (계속 도는 경우)

머신이 계속 돌고 있는 건지 아니면 단순히 시간이 오래걸리는 것인지 구별하기 어렵다.

Decider의 정의

Turing machine들 중에 모든 input에 대해 꼭 멈추는 머신을 decider이라고 한다.

모든 input 에 대해 멈추고 yes인지 no인지 판단해 주는 것이다.

Turing-decidable

decider가 recognize하는 language를 Turing - decidable이라고 부를 것이다.

대신에 어떤 language는 undecidable 하지만, turing-recognizable은 turing machine한 것이 있다.

--> reject하는 것에 대해 무한 루프를 도는 string들

예시)

0의 개수가 2의 몇 승 꼴이냐를 가지고 판단한다.

0의 개수가 1을 제외한 홀수인 경우 accept가 되지 않는다.

(1) 0의 개수가 1이면 accept하고

(2)  0의개수가 짝수이면 / 2 해서  (1)의 과정을 반복한다.

(3) 0의 개수가 홀수이면 reject한다.