모든 언어는 튜링-인식(Turing-recognizalbe)한가? 답은 "아니다". 전체적인 증명 과정을 먼저 소개하고, 하나하나 관련 개념을 설명해보도록 하겠다.
$\{0,1\}$의 알파벳에서
1. $\{0,1\}^*$, 혹은 가능한 모든 튜링머신들의 집합은 $\mathbb{N}$과 같은 크기를 같는다.
2. $\{0,1\}$으로 만들 수 있는 모든 문자열의 집합, 혹은 가능한 모든 언어들의 집합은 $2^\mathbb{N}$과 같은 크기를 같는다.
3. $2^\mathbb{N}$은 불가산집합(uncountable set)이지만, $\mathbb{N}$은 가산집합(countable set)이다.
4. 따라서, 가능한 모든 언어가 가능한 모든 튜링머신보다 그 종류가 많다.
5. 따라서, 튜링-인식기(Turing-recongizer)가 없는 언어가 존재한다.
countable과 uncountable의 정의
1. $\{0,1\}^*$, 혹은 가능한 모든 튜링머신들의 집합은 $\mathbb{N}$과 같은 크기를 같는다.
2. $\{0,1\}$으로 만들 수 있는 모든 문자열의 집합, 혹은 가능한 모든 언어들의 집합은 $2^\mathbb{N}$과 같은 크기를 같는다.
3. $2^\mathbb{N}$은 불가산집합(uncountable set)이지만, $\mathbb{N}$은 가산집합(countable set)이다.
4. 따라서, 가능한 모든 언어가 가능한 모든 튜링머신보다 그 종류가 많다.
5. 따라서, 튜링-인식기(Turing-recongizer)가 없는 언어가 존재한다.