Loading [MathJax]/jax/output/HTML-CSS/jax.js

ABOUT ME

한 컴퓨터공학과 학생이 개인 공부 용도로 운영하는 블로그입니다.

Today
Yesterday
Total
  • [계산이론] #08. Enumerability
    2023-2학기/계산이론 2023. 10. 15. 21:17

    Rice's Theorem

    세상에 존재하는 모든 TM의 Binary Encoding의 집합, T를 정의합시다. Rice's Theorem은 아래와 같이 T의 부분집합 P를 정의하면 P는 Undecidable이라는 것입니다.

    1. Pπ
    2. PT
    3. L(M1)=L(M2)인 임의의 두 TM M1M2에 대해 M1P and M2P 이거나, M1P and M2P

     

    1, 2번 규칙은 P가 공집합도 아니고, 모든 TM을 포함하는 집합도 아니라는 조건을 위한 것입니다. 중요한 것은 3번째 규칙입니다. 이 규칙은 직관적으로 알 수 있듯 어떤 MP의 원소인지 아닌지는 M 그 자체가 아닌 L(P)에 따라서 결정된다는 뜻입니다.

    예를 들어, 아래 3개의 Language는 Rice's Theorem에 의해 전부 Undecidable입니다.

    P1={M:ϵL(M)}

    P2={M:L(M)={1011,00011000}}

    P3={M:L(M) is regular}

     

    이제 Rice's Theorem을 한번 증명해 보겠습니다. 먼저 P가 Decidable이라고 가정한 뒤에, Halt가 Decidable임을 보일 것입니다. 그러면 이는 모순이 되므로 P가 Undecidable임이 증명됩니다.

    P가 Decidable하다고 가정했으므로, P에 대응되는 TM이 존재할 것입니다. 이 TM을 H라고 하겠습니다. 그리고 M1은 첫 번째 단계가 진행되면 곧바로 Reject State로 전환되는 TM이라고 하겠습니다. 그러면 M1을 Accept 하는 문자열은 존재하지 않으므로 L(M1)=π가 됩니다. 이제 M1P라고 가정하겠습니다. (마지막 부분에 M1P인 경우에서도 증명을 진행합니다.) M2P 인 TM M2를 잡아줍시다.

    여기서 아래와 같이 동작하는 Turing Machine TMw(x)를 생각하겠습니다.

    1. Mw를 넣었을 때 M이 Terminate 될 경우
      1. M2x를 넣어 M2가 Accept 할 경우
        1. TMw(x)는 Accpet State로 Terminate
      2. M2x를 넣어 M2가 Reject 할 경우
        1. TMw(x)는 Reject State로 Terminate

     

    Mw를 넣었을 때 Terminate된다고 가정하겠습니다. (즉, M,wHalt) 그러면, L(TMw)=L(M2) 입니다. 그러면 Rice Theorem의 3번째 조건에 의해 M2P 이므로 MMwP가 됩니다. 

    이번에는 Mw를 넣었을 때 Terminate되지 않는다고 가정하겠습니다. (즉, M,wHalt) 그러면  TMw는 어떤 Input에도 Terminate 되지 않으므로, L(TMw)=π입니다. 따라서, L(TMw)=L(M1) 입니다. 그러면 Rice Theorem의 3번째 조건에 의해 M1P 이므로 MMwP가 됩니다. 

    여기서 아래와 같이 동작하는 Turing MachineH(M,w)을 생각하겠습니다.

    1. HTM2를 넣었을 때 H가 Accept 할 경우
      1. H은 Accept State
    2. HTM2를 넣었을 때 H가 Reject 할 경우
      1. H은 Reject State

     

    눈치가 빠르신 분들은 알겠지만, H은 주어진 TM에 주어진 문자열을 넣었을 때 그 결과가 Accept인지 Reject인지 판단하는 Halting Problem을 해결하는 TM입니다.

    이제 M,wHalt인 경우부터 다시 생각해 보겠습니다. MMwP로부터 HM,w를 Accept 합니다.

    반대로 M,wHalt인 경우를 생각해보겠습니다. 마찬가지로 MMwP로부터, H은Terminate되는 것은 당연하고,  M,w를 Reject 합니다.

    어라? Halting Problem을 해결하는 H이 생겼습니다. 근데 이런 H은 존재할 수 없으므로, 모순이 발생하게 됩니다.

    증명의 제일 첫 번째 과정에서 M1P라는 가정을 하고 증명을 전개해왔는데요, M1P인 경우도 완전히 똑같지만, PˉP로 바꾸어서 진행하게 되면 ˉP가 Undecidable임을 증명할 수 있습니다. 모든 Language L에 대해서 L이 Decidable이면 ˉL 역시 Decidable이기 때문에, P가 Undecidable임을 증명할 수 있습니다.

     

    Enumerability

    Alphabet Σ에 대한 Language A가 있다고 생각합시다. 이때, 모든 문자열 w에 대해 아래 조건을 만족하는 TM M이 존재하면, Language A를 Enumerable이라고 부릅니다.

    1. wA일 경우 Mw를 넣으면 Accept State로 Terminate 됩니다.
    2. wA일 경우 Mw를 넣으면 Terminate 되지 않거나, Reject State로 Terminate 됩니다.

     

    Enumerable Language와 Decidable Language의 차이점은, Decidable Language A의 경우 AwA를 입력받았을 때 항상 Reject State로 Terminate 되어야 하지만 Enumerable Language는 그렇지 않다는 것입니다. 따라서, 모든 Decidable Language는 Enumerable Language입니다.

     

    Hilbert's Problem

    Hilbert's Problem은 수학자 Hilbert가 제시한 23가지의 문제들을 다 같이 묶어서 부르는 말인데요, 저희는 그중에 하나인 11번 문제를 한번 볼 겁니다. (다른 문제들은 다루지 않을 예정이므로, 원래는 "힐베르트 문제 11번"이 맞는 말이지만 편의상 "힐베르트 문제"라고만 부르겠습니다.)

    힐베르트 문제는 정수 계수를 가진 다항방정식이 정수해를 가지는지, 가지지 않는지를 판별하는 문제입니다. 정수해를 가지는 정수 계수 다항방정식을 p라고 하고, 존재하는 모든 p를 Binary String으로 변환한 p의 집합을 Hilbert라 하겠습니다.

    이 전 글에서, 이 Hilbert는 Undecidable이라고 말한 적이 있었는데요, 이번 글에서는 HilbertEnumerable임을 보일 것입니다. 이를 증명하기 위해서 저희는 알고리즘 Hilbert를 만들 겁니다. 이 Hilbert는 p를 입력받아 만약 p가 정수해를 가지면 유한한 시간 내에 그 정수해를 찾아내고, 정수해가 없으면 우리에게 정수해가 없다는 사실을 알려주거나 Terminate 되지 않습니다. 이런 알고리즘 Hilbert를 만들면, Language Hilbert가 Enumerable임이 바로 증명되는 겁니다.

    알고리즘 Hilbert는 어떤 방식으로 동작하느냐? 간단합니다. 가능한 모든 Tuple (x1,x2,...,xn)Zn을 전부 p에 대입하고, 그 값이 0이면 알고리즘을 Terminate 시키고 Accept합니다. 이제 중요한 것은 어떤 순서로 모든 Zn을 시도해 보냐는 것입니다.

    먼저 $ \mathbb{Z}^2 .Hilbert(0,0).H_0$라고 표현하며, 그림으로 나타내면 아래와 같습니다.

    그다음으로 H1을 방문할 건데요, (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0) 등이 이에 해당합니다. 식으로 나타내면 H1={(x1,x2):1x11,1x21,(x1,x2)H0} 이며, 그림으로는 아래와 같습니다.

    그리고 아래는 다음에 방문할 H2를 나타낸 그림입니다.

    이렇게 순서대로 모든 Z2을 방문할 수 있습니다. 이는 Zn으로 쉽게 일반화가 가능합니다.

    따라서 위와 같은 알고리즘 Hilbert를 만들 수 있으므로, Language Hilbert는 Enumerable 합니다.

     

    ATM

    이 전 글에서 아래와 같은 Language ATM이 Undecidable이라는 사실에 대해 알아보았었습니다.

    ATM={M,w:M is TM that accepts w}

    이 Language는 Decidable하진 않지만 Enumerable이긴 합니다. 위의 예시와 같이 알고리즘 P를 만들어서 ATM이 Enumerable임을 한번 보여보도록 하겠습니다.

    PM,w를 입력받으면 아래와 같이 동작합니다.

    1. Mw를 넣어 시뮬레이션을 진행합니다.
    2. M이 Accept State에 도달하면, P는 Accept State로 Terminate 됩니다.
    3. M이 Reject State에 도달하면, P는 Reject State로 Terminate 됩니다.
    4. M이 Terminate 되지 않으면, P도 Terminat 되지 않습니다.

     

    이렇게 ATM이 Enumerable임을 쉽게 증명할 수 있었습니다.

     

    Enumerator

    Language A에 대해, 아래의 조건을 만족하는 Turing Machine EAEnumerator라 부릅니다.

    E에는 Print TapePrint State가 존재합니다. 각각의 Step에서 E는 Print Tape에 알파벳을 작성합니다. 그리고 E가 Print State에 들어가면 현재 Print Tape에 적힌 문자열이 Printer로 보내지고 Print Tape에 있는 알파벳은 전부 지워집니다.

    이때, 모든 문자열 wA는 적어도 한 번은 Printer로 보내지게 되며, 모든 문자열 wA는 Printer로 보내지지 않습니다. 즉, A의 Enumerator는 A의 모든 문자열을 Print 합니다. 정해진 순서는 없으며, 어떤 문자열은 여러 번 출력될 수도 있습니다. 만약 A가 무한 집합이라면 E는 Terminate 되지 않습니다. 그러나 A에 존재하는 모든 문자열은 언젠가 Print 됩니다.

     

    이 글로만은 감이 잘 오지 않으실 텐데, 예시를 한번 들어보겠습니다. A={0n:n0}의 Enumerator는 아래와 같이 작동합니다.

    1. n ← 0
    2. while True do
      1. for i ← 1, n do
        1. write 0 on Print Tape
      2. Enter the Print State
      3. n ← n + 1

     

    이 Enumerator의 가장 중요한 성질 중 하나는, Enumerator가 존재하는 Language는 항상 Enumerable이라는 사실입니다. 그 역도 성립합니다.

    먼저 Enumerator E와 Language A가 있을 때, A에 대응되는 Turing Machine M을 만들어 A가 Enumerable임을 증명해 보도록 하겠습니다.

    M(w)은 먼저 E를 작동시키고, E가 Print State로 들어갈 때마다 Print Tape에 적힌 문자열과 w를 비교합니다. 만약 같은 경우 M은 Accpet 상태로 Terminate 됩니다.

    만약 wA일 경우 E가 작동하는 동안 Print Tape에 적힌 문자열과 w가 같은 상황이 발생할 것이고, M은 Accept State가 됩니다. 하지만 wA일 경우 E가 계속 작동해도 Print Tape에 적힌 문자열과 w가 같은 상황은 일어나지 않으므로 M은 Terminate 하지 않습니다. 따라서, 이런 Turing Machine M이 존재하므로 A는 Enumerable입니다.

     

    반대로, A가 Enumerable 하다고 가정하고 E가 항상 존재함을 보이겠습니다. A가 Enumerable 하다는 뜻은, wA를 입력했을 때 Accept State로 Terminate 되고 wA를 입력했을 때 Terminate 하지 않거나 Reject State로 Terminate 되는 Turing Machine M이 존재한다는 뜻입니다.

    주어진 Alphabet으로 만들 수 있는 모든 문자열의 집합을 S={s1,s2,s3,} 라고 하겠습니다. 그러면 아래와 같이 동작하는 Turing Machine E를 만들 수 있습니다.

    1. n ← 1
    2. while True do
      1. for i ← 1, n do
        1. M을 Input si에 대해 n개의 Step만큼 작동시킴
        2. if M이 Accept
          1. Print Tape에 si를 작성
          2. Print State에 진입
      2. n ← n + 1

     

    이렇게 동작하는 EA의 Enumerator이므로 그 역도 성립함이 증명되었습니다.

     

    마무리

    이번 글에서는 Enumerability가 무엇인지, 그리고 Enumerable Language는 어떤 성질을 가지며 어떤 Language가 Enumerable 한 지 알아보았습니다.

    감사합니다.


    이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.
Designed by Tistory.