이동식 저장소

2-Tape DTM 테이프 2개를 사용하는 ``DTM``을 생각해보자. 이 기계는 테이프가 1개인 ``DTM``보다 더 많은 계산을 할 수 있을까? 결론부터 말하면, 실행 시간이 조금 빨라질 수는 있어도 두 기계의 계산능력 자체는 동일하다. 테이프가 2개인 ``DTM``의 전이함수는 다음과 같다. $(p,a,b) \rightarrow (q, c, d, s, t)$ $p$: 현재 상태 $a$: 첫 번째 테이프에서 읽은 글자 $b$: 두 번째 테이프에서 읽은 글자 $q$: 전이할 상태 $c$: 첫 번째 테이프에 쓸 글자 $d$: 두 번째 테이프에 쓸 글자 $s$: 첫 번째 테이프의 이동 방향(왼쪽, 오른쪽, 정지 중 하나) $t$: 두 번째 테이프의 이동 방향(왼쪽, 오른쪽, 정지 중 하나) 어쨌든 테이프가..

Class ``Class``는 문제의 집합을 말한다. 예를 들어 ``DFA``가 풀 수 있는 문제의 집합은 class이다. 그럼 class의 개수는 몇 개일까? $\sum = \{0, 1\}$일 때 $|\sum^{*}| = |N|$이고, 가능한 모든 문제의 수 $|2^{\sum^{*}}|=|2^{N}|=|R|$이므로 문제의 집합의 수는 $|2^{R}|$이다. 설명 가능한 문제의 수가 $|N|$이므로, 설명 가능한 class의 수는 $|2^{N}|$이다. Class DFA Class DFA는 ``DFA``로 풀 수 있는 문제의 집합이다. 여기서 헷갈리면 안 된다. 문제는 string의 집합이고, class는 문제의 집합이다. 예를 들어 $\{ 0, 10, 100, \cdots\}$는 ``DFA``가 풀 수..

모든 자연수는 흥미로운 성질을 가진다. pf) 집합 U를 흥미로운 성질이 없는 자연수의 집합이라고 하자. $ U \neq \emptyset $라고 가정하면, 자연수의 성질에 의해 U의 가장 작은 원소 $t \in U$가 존재한다. 그런데 t는 "U의 가장 작은 원소"라는 흥미로운 성질을 가진다. 따라서 $ t \notin U $이다. 증명 과정에 모순이 있으므로 $ U \neq \emptyset $라는 가정이 잘못되었다. 따라서 $ U = \emptyset $이고, 모든 자연수는 흥미로운 성질을 가진다. ..당연히 이 증명은 틀렸다. 증명조차 아니다. 이 문제에 대한 엄밀한 증명은 다음 시간에 생각한다.