[암호학] Berry Paradox

암호학 수업 중간 이해가 안 가는 부분이 있었는데, 마침내 이해가 되어 정리해보려 한다.

 

Berry paradox

‘19글자 이내로 표현할 수 없는 최소의 자연수’

위 문장 자체가 19글자 이내로 표현을 하고 있기 때문에 존재한다 따라서 ‘빨간 부분’은 존재할 수가 없으므로 역설이다.

이런 류의 역설을 Berry Paradox 라고 한다. 

https://surpriser.tistory.com/789

자기 언급의 역설

위 링크에서 참고하였다.

---

Berry paradox 는 complexity theory 와 연결이 되어 있다.

(Number theory 와 complexity theory 가 암호학의 두 축)

Halting problem은 complexity에서 유명한 문제

 

Halting is proved by Berry Paradox

Machine M(Program) , Input X(any String) 가 M(X) 가 멈추는지 안 멈추는지 판단한다

예를 들어,

아래와 같은 프로그램이 있다고 가정하자.

아래 프로그램은 길이가 300이하인 모든 프로그램을 다 돌리는 프로그램이다.

for all program of length at most 300
//if program halts (halting이 풀린다면)
run program

mark Integer with output of program

output smallest unmarked integer

아래와 같이 위 프로그램을 실행한 결과를 테이블로 표현한다.

두 가지 가정으로 위 프로그램 문제로 halting 이 안 풀리는 문제인 것을 증명한다.

• halting 이 안 풀린다면
  • 위 프로그램에 돌렸을 때, 안 끝나는 프로그램이 있어서 위 프로그램에서 ' output smallest unmarked integer' 까지 갈 수가 없다
• halting 이 풀린다면 (= halting 임을 판별할 수 있는 알고리즘이 있다면)
  • 위 프로그램에서 멈추는 프로그램만 돌려서 나온 smallest unmarked integer 를 X 라 하자.
  • 위 자체 프로그램 또한 300 이하 프로그램이므로 X 가 'mark integer with output of program' 의 대상이 되어야 하는데 X는 이미 smallest unmarked integer 로 선택되었으므로 모순이 발생한다.
  • 또한, 위 테스트 프로그램 또한 300 이하 프로그램이므로, 
    • 위 프로그램 자체를 자기 참조 하여 다시 한번 더 실행하면, X 가 marked integer 가 되어 후에 실행한 프로그램은 다른 값 (Y) 을 출력하게 된다. -> 같은 프로그램이 다른 값을 출력하게 되는 모순 이 발생한다.

 

---

따라서 halting 이 풀린다면 Berry Paradox 를 구현할 수 있기 때문에 ( ex. 테이블에서 20이하 output을 다 지워 맨 처음 나오는 output 값을 얻을 수 있음 ) 

halting 이 풀리면 안된다. 

 

---

이해하기 위해서 3분 구간 동영상 강의를 한 6번은 본 것 같다.. 

그래도 이해되니 암호학이 좀 괜찮은 느낌.