L과 TM이 있을 때

• L의 모든 string을 accept, L이 아닌 걸 전부 reject (halt) → Decidable (recursive)
• L의 모든 string을 accept, L이 아닌 걸 전부 reject 또는 loop → semi-Decidable (recursively enumerable) 이 경우 튜링-recognizable이지만 Undecidable이다.
  • ex. 뒤에서 다룰 Universal Language
• L이 Decidable하지 않음 → Undecidable
  • ex. 뒤에서 다룰 Diagonalization Language $L_d$

Recursive Language (Decidable)

TM이 L을 accept 했을 때 무조건 정지하게 만드는 L이다

최종적으로 받아들이는지는 상관 없다.

• $L$이 recursive라면 $\bar L$도 recursive이다 pf) $\bar M$을 만든다.

  • non-accepting state를 전부 accept 하도록 하고, transition을 제거한다.
  • 만약 transition이 원래 없었다면 추가해준다.

  

  이러면 무슨 일이 있어도 정지하게 되며, 정확히 M에서 받아들이지 않는 L만 받아들인다.

Recursively Enumerable Language (Semi-Decidable)

L에 대해 어떠한 TM이 존재, L의 모든 string을 accept한다 final state에 도달한다.

즉 TM이 받아들이고 계산할 수 있는 모든 language의 집합이다

왜 “enumerable”이라고 부를까?

• Enumerator of Language TM that writes on tape #x1#x2#x3#…
  • 이때 L이 {x1, x2, x3, …}이었다.
  • 즉 L의 모든 string을 하나씩 출력하는 튜링머신=enumerator

Semi-decidable ↔ Enumerator enumerates L

<aside> 💡 알고 싶은 것: 이 TM이 이 input을 accept하는가? 그런 TM이 존재하지 않는다면 undecidable인 것이다.

</aside>

우선 input이 binary인 경우부터 살펴보자

Encoding Turing Machines