챕터1, 부록1 정리

[myeongjae-kim]

Chapter 1

https://deering.slack.com/archives/C02R6LLJW5N/p1657896082893689

람다 계산법과 튜링 머신은 등치다

“the Church-Turing conjecture: at bottom, all computers are essentially equivalent.”

지금까지 다양한 프로그래밍 언어들이 고안되었고, 언어마다 유도하는 생각의 방식이 있다. 컴퓨터로 계산한다는 것을 무엇으로 보냐에 따라 다른 방식의 언어가 만들어졌다.

이게 무슨 말인가? 튜링(Alan Turing)이 정의한 소프트웨어는 튜링기계다. '기계적으로 계산 가능한 것'이 뭐냐를 정의한 것이 튜링의 경우 튜링기계였다. 원시적이지만, 구체적이고 명백한 기계다. 테이프가 있고 정해진 규칙표에 따라서 테이프에 문자를 읽고 쓰며 동작하는 기계.

튜링과 같은 시기에 처치(Alonzo Church)는 '기계적으로 계산 가능한 것'을 다른 스타일로 정의한다. 람다 계산법Lambda calculus이라는 것이다. 튜링 기계만큼 원시적이지만 '기계'의 모습은 없다. 심벌을 단순히 다루는 함수만으로 계산을 정의한다.

튜링기계와 람다 계산법은 표현력이 똑같다. 튜링 기계로 돌릴 수 있으면 람다 계산법으로도 계산할 수 있고 그 반대도 그렇다.

...

이 두 언어는 각각 다른 관점에서 소프트웨어를 보도록 유도한다. 튜링기계는 소프트웨어를 기계에게 전달하는 명령으로 보게 한다. 람다 계산법은 소프트웨어를 상위의 세계에서 논리적으로 따져가는 계산식으로 보게 한다.

두 개의 판이한 기원이 있다는 건 행운이다. 하나만으로는 프로그래밍 기술은 멀리 날 수 없었다. 튜링기계와 람다 계산법의 두 중력이 맞물릴 때 프로그래밍 기술은 비로소 좀 더 높이 올라설 수 있었다. 이 두 중력은 프로그래밍 언어의 연구도 전혀 다르게 이끌었고, 그래서 다채롭고 유용한 성과를 프로그래밍 세계에 선사해 주었다.

- 이광근, 『컴퓨터과학이 여는 세계』, 인사이트, 2017, p155 and p160

함수형 프로그래밍

세 번째 패러다임은 최근에 들어서야 겨우 도입되기 시작했지만, 새 패러다임 중 가장 먼저 만들어졌다. 사실 함수형 프로그래밍은 컴퓨터 프로그래밍 자체보다 먼저 등장했다. 알론조 처치Alonzo Church는 앨런 튜링도 똑같이 흥미를 느꼈던 어떤 수학적 문제를 해결하는 과정에서 람다lambda 계산법을 발명했는데, 함수형 프로그래밍은 이러한 연구 결과에 직접적인 영향을 받아 만들어졌다. 1958년에 존 매카시John McCarthy가 만든 LISP 언어의 근간이 되는 개념이 바로 이 람다 계산법이다. 람다 계산법의 기초가 되는 개념은 불변성immutability으로, 심볼symbol의 값이 변경되지 않는다는 개념이다. 이는 함수형 언어에는 할당문이 전혀 없다는 뜻이기도 하다. 사실 대다수의 함수형 언어가 값을 변경할 수 있는 방법을 제공하기는 하지만, 굉장히 까다로운 조건 아래에서만 가능하다.

함수형 프로그래밍 패러다임은 아래와 같이 요약할 수 있다.

함수형 프로그래밍은 할당문에 대해 규칙을 부과한다.

• 클린 아키텍처, 로버트 마틴

힐베르트의 꿈을 박살낸 괴델, 그리고 괴델의 불완전성의 원리를 다른 형태로 다시 한 번 증명한 알론조 처치와 앨런 튜링

알론조 처치의 람다 계산법이 튜링의 튜링 머신보다 더 먼저다. 근본중의 근본은 절차형 프로그래밍보다 함수형 프로그래밍. 처치: 1936년 4월, 튜링: 1936년 12월. https://en.wikipedia.org/wiki/History_of_the_Church%E2%80%93Turing_thesis

Turing adds another definition, Rosser equates all three.

- https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#Circa_1930%E2%80%931952

처치는 튜링머신이 자신의 람다대수보다 더 우아하게 괴델의 불완전성의 원리를 증명한다고 생각했음.

“abstraction describes what the module does, and implementation describes how it does it.”

“magnetic, optical, biological, hydraulic, pneumatic, quantum-based, and even domino-based mechanisms (many of these implementations were proposed as whimsical “can do” feats).”

두 가지 상태를 나타낼 수 있는 무언가는 모두 컴퓨터의 재료로 쓸 수 있다. 현재는 0V와 5V

“The use of Boolean algebra for analyzing the abstract behavior of logic gates was articulated in 1937 by Claude Shannon, leading to what is sometimes described as the most important M.Sc. thesis in computer science.”

섀넌, 부울대수와 논리게이트를 연결하고.. 나중에는 정보이론을 만듦. https://newspeppermint.com/2016/01/21/m-10theory/

10. 정보이론: 클로드 섀넌, 1948

이 이론은 심지어 뒤집어 엎을 기존의 이론이 없었기에 혁명적인 이론이라고 말할 수도 없는 이론입니다. 섀넌의 정보이론은 오늘날 통신과 컴퓨터 과학의 기본이 되는 수학적인 기초를 제공했습니다. 정보이론이 없었다면, 비트(bit)는 아직도 드릴의 날을 가리키는 단어였을 것입니다.

충분한 시간이 있다면 네트워크 상태가 아무리 좋지 않아도 데이터를 온전하게 전달할 수 있다는 것을 증명함. 신호의 세기가 강하면 노이즈가 발생하고 약하면 멀리 못 간다. 이 딜레마를 완전히 다른 방식으로 해결함. 우리가 네트워크를 믿고 쓸 수 있는건 섀넌 덕분. 나중에는 카지노를 정복했다(?) 책 머니 사이언스 (https://m.yes24.com/Goods/Detail/1943196) 참고

Appendix 1

“Lemma 1: Any Boolean function can be represented by a Boolean expression containing only And, Or, and Not operators.”

“disjunctive normal form (DNF)”으로 증명 가능. 특정한 매개변수 하나에 대해서만 true가 나오는 함수 여러개를 or로 연결하는 방법으로 모든 진리표를 구현할 수 있다.

“In order to appreciate the significance of this result, consider the infinite number of functions that can be defined over integer numbers (rather than binary numbers). It would have been nice if every such function could be represented by an algebraic expression involving only addition, multiplication, and negation. As it turns out, the vast majority of integer functions, for example, for and cannot be expressed using a close algebraic form. In the world of binary numbers, though, due to the finite number of values that each variable can assume (0 or 1), we do have this attractive property that every Boolean function can be expressed using nothing more than And, Or, and Not operators. The practical implication is immense: any computer can be built from nothing more than And, Or, and Not gates.”

“Lemma 2: Any Boolean function can be represented by a Boolean expression containing only Not and And operators. Proof: According to De Morgan law, the Or operator can be expressed using the Not and And operators. Combining this result with Lemma 1, we get the proof.”

---

적당히 고민하고 답이 안나오면 답지를 보고 내가 어디서 막혔었는지 파악하고 같은 행위를 반복하지 않게 하는게 절대 답지를 보지 않고 오랫동안 고민하는 것보다 효과적인 학습법이라는 연구가 있었는데.. 링크를 못찾겠네. 오히려 오랫동안 안풀리는 문제를 붙잡고 있으면 잘못된 사고 회로를 계속 반복 훈련을 하는 것과 마찬가지라서 이후에도 무의식적으로 같은 실수를 오히려 더 반복하게 됨.

일정 수준 이상에서는 답지의 도움을 받지 않고 끝까지 해내는 끈기를 훈련할 필요가 있겠지만, 이 책이 처음부터 너무 어렵게 느껴진다면 답지를 자유롭게 보고 자신이 뭘 몰랐는지 빠르게 파악하는게 훨씬 효과적이라고 생각함.

[swimmingone]

https://youtu.be/92WHN-pAFCs

[Deocksoo]

명재: 튜링 머신과 람다 계산법이 수학적으로 동일하다는걸 누가 증명했다. 이게 굉장히 아름답다. 튜링 머신은 절차형 프로그래밍의 뿌리, 람다는 함수형 프로그래밍의 뿌리다.

프로그래밍 과제 하는데 시간이 꽤 오래 걸리더라. 답지를 적극적으로 활용하는 것을 권장한다.

[myeongjae-kim]

구현순서: https://github.com/myeongjae-kim/nand2tetris/issues/1