[계산이론](24)[non-recognizable language]

non-recognizable language

몇몇 language는 turing recognizable하지 않다.
왜냐하면 language의 개수가 TR보다 많기 떄문이다!

TR is countable

하나의 TR에는 여러개의 TM이 대응될 수 있다.
    즉, 하나의 language를 여러 방식의 TM으로 나타낼 수 있다
그러나, 하나의 TM은 여러개의 TR이 대응될 수 없다.
-> 즉, |TR| <= |TM|이다.
따라서 |TM|이 countable하면 TR도 countable하다

 

TM을 하나의 문자열인 <M>으로 인코딩 했다고 하자.
<M> ∈ $\sum^*$ 일 것이고 TM ⊆ $\sum^$일 것이다.
이떄, $\sum^*$는 유한 길이의 문자 집합이다.
    따라서 길이에 따라 정렬 후 자연수와 대응시킬 수 있다.
    (마치 N진법마냥 대응 가능하다.)
따라서 $\sum^*$은 countable 이고, TM은 무한집합이므로,
TM은 countable하다.
-> 따라서 TR은 countable하다.

 

language is uncountable

language를 무한한 길이의 binary sequance B로 표현하고
B가 uncountable하다는 것을 증명하겠다.

 

B의 원소는 하나의 language A에 대응되는 0,1의 무한한 나열으로,
$\sum^*$ 중 A에 있는 문자열은 1로, 아니면 0으로 표시하는 것이다.
예) A = {0 is odd}를 b로 나타내면 다음과 같다
    $\sum^*$ = { ε, 0, 1, 00, 01, 10, 11, 000, ...}
    A = { 0, 01, 10, 000, ...}
    b = 0 1 0 0 1 1 0 1 ...
이때, L-B 대응 과정은 일대일대응이므로, |L| = |B| 이다.
(참고: 칸토어의 정리: power set P(X)의 크기는 항상 X보다 크다 (재료 n개, 조합 2^n개))

 

B는 무한한 길이의 binary sequance이므로
B가 countable이라 가정하고 대각선 논법을 사용하면

n	f(n)
1	100101001...
2	100100101...
3	000001100...
4	101010110...
...	...

x = {n번째 자리 수는 f(n)의 n번째 자리 수와 같지 않다.}
    예) 0111...
이떄, x는 확실히 B의 원소이나, f(n)의 원소는 아니다.
따라서 전사성에 위배되므로, B는 uncountable하다.
-> L은 uncountable 하다.

 

따라서 |TR| <= |TM| < |L| 이므로,
TR에 포함되지 않는 language가 존재한다!

 

non-TR language

$\bar{A}$ = A에서 accept랑 reject&loop를 뒤집은 language
    accept: A is reject or loop
    reject: A is accept
즉, $\sum^*$는 A, $\bar{A}$로 분할된다

A is decidable ⇔ A is TR and $\bar{A}$ is TR

• A: TD -> A: TR and $\bar{A}$: TR
  A가 TD이면 accept랑 reject밖에 없다.
  따라서 A는 당연히 TR에 포함되며
  $\bar{A}$는 accept와 reject를 뒤집기만 하면 된다
• A: TR and $\bar{A}$: TR -> A: TD
  A가 TR = A가 accept를 loop에 빠짐 없이 모두 결정 가능
  $\bar{A}$가 TR = $\bar{A}$가 not accept (A의 reject, loop)를 loop 없이 모두 결정 가능
  즉, A: TR (M1), $\bar{A}$: TR (M2)를 포함하는 M을 다음과 같이 정의하면
      accept: M1 is accept
      reject: M2 is accept
  이걸로 A에 대한 decider M을 만들 수 있으므로,
  A는 decidable하다.

 

$\overline{A_{TM}}$ is unrecognizable

앞에서 증명한 정리의 대우를 사용해 증명하겠다.
    A가 TD가 아님 -> A또는 $\bar{A}$가 TR이 아님

 

$A_{TM}$은 TD가 아님은 이전에 보였고,
$A_{TM}$은 accept, reject, loop로 상태가 표현될 수 있으르로 TR이다.
따라서 정리에 의해
    TD가 아님 -> A는 TR임 -> $\bar{A}$는 TR이 아니어야 함
따라서 $\overline{A_{TM}}$는 TR이 아니다.

 

참고) 현재까지의 언어 계층구조
regular ⊆ context-free ⊆ decidable ⊆ turing-recognizable ⊆ turing-unrecognizable