[계산 이론] Some languages are not Turing-recognizable

 

이번 증명을 통하여 Turing Machine이 recognize하지 못하는 Language가 있음을 보일 것 이다.

 

1. 모든 Turing Machine은 countable 하다

모든 튜링머신이 Countable함을 보이기 전에, 우선 모든 String의 집합(∑*)이 모든 alphabet ∑에 대하여 count할 수 있음을 보일것 입니다.

 

∑* 의 list를  길이가 0, 길이가 1, 길이가 2 ... 순으로 아래로 적어내려 갈 수 있습니다. 또한 각 lenght마다 finite한 수의 String이 있습니다.

이를 그림으로 살펴보면 다음과 같은데,

 

길이가 0인 String에는 입실론이, 1에는 0과 1, 등등 이 존재합니다.

모든 자연수 1, 2, 3, ... N에 대하여 mapping가능한 하나의 String을 지정할 수 있으니, 즉 ∑*는 자연수와 같다 할 수 있다. 
(하지만 Language의 수는 실수 R과 같다)

 

|∑*| 와 |Turing Machine, T| 은 둘다 countable로 자연수 N과 mapping이 되지만, ∑*에는 T와 mapping되지 않는 것도 분명 존재한다. 즉, T의 수는 적어도 |∑*| 보다 커지지는 않는다.

 

왜 그럴까?? 지금 부터 알아보자!

 

Turing Machine M 하나는 인코딩 된 하나의 <M> String으로 mapping이 가능하다.

즉 모든 Turing Machine을 인코딩 하여 하나의 String으로 변환이 가능한데, 이 부분이 다음 그림에서 빨간색 부분이다.

 

하지만 ∑* 안에는 분명 T.M 과 mapping되지 않는 영역도 있다.

즉, 어떠한 TM M'은 인코딩 되지 못하여 <M'>의 형태로 변환될수가 없다. 

이렇게 mapping되지 않는 부분을 전부 제거하면 모든 T.M은 자연수와 mapping이 가능하기 때문에 Countable이다.

 

2. Langauge의 수는 Uncountable 이다

우리는 set of all language is uncountable함을 보일 것 이다.

이를 위한 전략으로 B라는 녀석이 uncountable임을 우선 보인후에, B와 set of all language L이 동일한 size임을 보여 증명할 것 이다.

 

우리는 첫번째로, 모든 무한한 binary sequence(0과 1로 이루어진 무한한 sequence)는 uncountable함을 사용할 것 이다.

B를 the set of all infinite binary sequences 라고 하자.

 

우리는 대각화 + 귀류법 을 통하여 B가 uncountable함을 보일 것 이다.

 

따라서 B는 uncountable이다.

 

3. B와 모든 Language의 집합 L의 사이즈가 같다.

L을 the set of all languages over alphabet ∑라고 하자.

우리는 B로부터 L로 가는 전단사(Correspondence) 함수를 보임으로써 L와 B과 동일한 Size임을 보일 것 이다.

 

K를 1로 끝나는 String들의 집합 이라 했을때, 모든 ∑*의 원소중 1로 끝나는것을 1로, 아닌것을 0으로 mapping해보면 다음과 같다.

 

즉, Language 하나를 B의 infinite binary sequences로 Mapping이 가능한 것 이다.

 

즉, B(the set of all infinite binary sequences)의 수 == Language의 수

 

무한한 수의 이진 시퀀스만큼의 Language가 있으니, 이는 TM이 recognizable 하지 못하는 부분이 분명 존재한다는 의미 이다.

 

따라서 다음 과 같이 결론을 내릴 수 있다.