차례 SNU 046.06 컴퓨터과학이 여는 세계(Computational Civilization) Part Prof. Kwangkeun Yi 400년의 축적 Department of Computer Science & Engineering 다음 컴퓨터라는 도구 인류역사에 유례가 없던 도구 컴퓨터 v.s. 칼, 활, 바퀴, 고무밴드, 자동차, 냉장고, 400년의 축적 컴퓨터라는 도구의 놀라운 특이점은 뭘까? 만능
수학자들의 꿈 컴퓨터 디자인의 탄생비화 수리명제 자동판결 문제(Entscheidungsproblem, decision problem) 928년 @ 국제 수학자대회(CM) 보편만능의 도구(universal machine) 20세기 수학의 좌절을 재확인하는 데 동원된 소품 이것이 20세기 정보혁명의 주인공이 되는 아이러니 Gottried Leibniz(-76) Gottlob Frege(-925) David Hilbert(-943) 모든 명제들의 참/거짓을 기계적으로 판명할 수 없을까? 참인 모든 명제들을 기계적으로 만들어낼 수 없을까? (사진출처: 추론 기계: 추론 규칙 기계적 맛있는 라면만들기: 라면공장 기계 두 정수의 최대공약수 찾기: 막대재기 기계 참/거짓 판별하기: 추론 기계 쌍 uncle(a, b)들의 추론 규칙 male(u) father(f, i) brother(f, u) uncle(u, i) father(c, a) father(c, b) brother(a, b) 쌍 ({g,, gn }, f )들의 추론 규칙 (Γ, T ) (Γ, f ) (사진출처: Google) f Γ (Γ, F ) (Γ, f ) (Γ, f ) (Γ, f ) (Γ, f ) (Γ, f2 ) (Γ, f f2 ) (Γ, f f2 ) (Γ, f ) (Γ, f ) (Γ, f f2 ) (Γ, f f2 ) (Γ {f }, f3 ) (Γ {f2 }, f3 ) (Γ, f3 ) (Γ {f }, f2 ) (Γ, f f2 ) (Γ, f f2 ) (Γ, f ) (Γ, f2 ) (Γ {f }, F ) (Γ, f ) (Γ, f ) (Γ, f ) (Γ, F ) Google)
93 년, 수학계의 좌절 혹은 희소식 기계적인방식만으론사실인지판정할수없는, 그런명제가존재한다. 936 년, 8 월 9 일 vs 5 월 28 일 손기정 알란튜링 (Alan Turing) Kurt Gödel(-978) ( 사진출처 : Google) 계산가능한수에대해서, 수리명제자동판별문 제에응용하면서 (On Computable Numbers, with an Application to the Entscheidungsproblem) 튜링의그때그시절 (/2) 934 년 월, Cambridge U 학부졸업논문제출 935년봄, Part course on Foundations of Mathematics수강 ( 강사 : Max Newman) Newman의강의는 Gödel의불완전성의증명 (ncompleteness Theorem) 으로마무리됨. 기계적인방식으로는참 / 거짓을판명할수없는명제가존재한다. Newman: 참 / 거짓을판명해주는기계적인방식은 있을수없겠지...
튜링의그때그시절 (2/2) Newman 강의를수강후인 935 초여름, 935년 4월말, group theory에대한논문제출및출판 (London Mathematical Society). 이논문은폰노이만논문을작게개선한것. 935년동안은또양자역학에도연구를할까생각함. 수리물리학 Fowler교수를찾아가연구꺼리를얻었으나진전이없었슴. Newman이강의때던진말이튜링의관심을붙듬. 떠나자 : 오리지날논문속으로 On Computable Numbers, with an Application to the Entscheidungsproblem Proceedings of the London Mathematical Society, ser.2, vol.42 (936-37). pp.230-265; corrections, bid, vol 43(937) pp.544-546 이때쯤, 장거리달리기취미를가지기시작. 튜링왈, 달리기를마치고풀밭에누워있는데힐버트의 세번째문제를어떻게풀지가생각나더라.. Computing Machines, 2. Definitions 3. Examples of computing machines 기계적인방식 = 아래의부품들로만드는기계로돌리는 무한 : 빈칸이무한히많은테잎 유한 : 기계상태들 S, 테잎심볼 T, 규칙표 R 규칙표 R S T T {>, <, } S 계산가능한숫자열들 0 0 0 0 를만드는튜링기계 0 0 0 0 0 를만드는튜링기계
4. Abbreviated tables skeleton tables : 반복해서사용할라이브러리 / 서브루틴룰들 rules for finding the left most symbol rules for writing a symbol at the end of the first symbol etc. 5. Enumeration of computable sequence 튜링기계마다자연수하나로표현가능. 규칙표를보자 : 상태심볼 {A, B, C} 은 {S 0, S, S 2 } 테이프심볼 {, $} 은 {T 0, T } A * * > A A $ $ > B 따라서일렬로표현하면 A > A 끝 A $ $ > B S 0 T 0 T 0 > S 0 X S 0 T T > S 즉, S, T, 0,, 9, <, >,, X 로표현한 진수. 6. The universal computing machine, 7. Detailed description of the universal machine 보편만능의기계 (/2): 임의의튜링기계를테 이프에표현하기 7 개테이프심볼이면충분 : S, T, <, >,, 0,, 9, X, 하나의튜링기계를만들수있다, 임의의튜링기계를입력으로받아그기계의작동을하는. 보편만능의기계 ( universal machine ) 임의의튜링기계를테이프에, 심볼의일차원실로 받기 그것대로실행하는튜링기계규칙표만들기
보편만능의 기계(2/2): 규칙표 예술로 표현한 Univeral Turing Machine Roman Verostko, 998, www.verostko.com/manchester/manchester.html 아래과정을 반복하는 규칙표. 읽기: 테잎에서 현재상태 심볼 Si 2. 읽기: 테잎에서 위치심볼( )의 테잎심볼 Tj 3. 규칙찾기: Si와 Tj와 매치되는 규칙을 테잎에서 찾기. 4. 찾은 규칙 Si Tj Tj 0 m Si0 이 시키는 일하기: 심볼복사 + 위치심볼이동 증명 준비: 튜링기계의 급소 (그림출처: 8. Application of the diagonal process 멈춤문제(Halting Problem)를 풀 수 있는 튜링기계는 없다, 튜링기계의 개수는 무한히 많지만 자연수의 개수를 넘을 수 없다 는 것을 보임. 튜링기계마다 자연수 하나(7진수의 자연수)에 대응 만약 있다고 하자 H. 그러면, 모든 튜링기계를 줄 세워 아래 테이블 가능: 입력 무한의 세계에도 크기 차이가 있다 칸토르(Georg Cantor)의 대각선 논법( N < 2 ) N 3 튜 M 0 링 M2 0 기 M3...... 0...... 계 2 모순: 그런데 모든 튜링기계와 다른 튜링기계 D가 있다! D(n) = U M (Mn, n ) H(Mn, n ) + 따라서 멈춤문제를 풀 수 있는 튜링기계 H는 없어야. 칸토르(Georg Cantor)의 대각선 논법( N < 2N ) Google)
9. The extent of the computable numbers 기계적으로계산가능한수들의범위튜링이정의한기계적인계산과정 ( 튜링머신으로돌릴수있는과정 ) 이과연 기계적인계산 의모두인가에대한방어. 세가지로설득 직관적이지아니한가 두개의정의가결국같지아니한가 Hilbert s restricted functional calculus = Turing computable 이렇게계산가능한수의범위가꽤크다, 보라 0. Examples of large classes of numbers which are computable 계산가능한함수로꾸민계산가능한함수는계산가능 계산가능한함수로꾸민재귀함수는계산가능 계산가능한수열의극한값은계산가능 등등. Application to the Entscheidungsproblem (/3). Application to the Entscheidungsproblem (2/3) 기계적인과정으로명제의참거짓을판단할수있을까? 혹은기계적인과정으로모든참인명제를만들어낼수있을까? 모든참인명제를만들어내는튜링기계 A 증명목표 : A 는존재하지않는다. 사실 : A 가존재하면 H 가존재한다. 불가능하다. 왜냐하면, 가능하다고가정하고살펴보면모순이기때문이다. 사실 : H 는존재하지않는다. 따라서 A 는존재하지않는다.
. Application to the Entscheidungsproblem (3/3) 사실 : A가존재하면 H가존재한다. A를부품으로써서 H를쉽게만들수있기때문 : 입력 : 멈출지알고싶은튜링기계 M UM으로 A를흉내낸다. 참인명제를빠뜨림없이만들것이므로 ( 튜링기계 M은멈춘다 ) 또는 ( 튜링기계 M은멈춘다 ) 를반드시만들것이다. 여담 : H 가존재한다면? 많은오리무중이자동증명됨. 예를들어, Fermat: 자연수 n > 2에대해서 a n + b n = c n 인자연수a, b, c는없다. Goldbach: 모든짝수는두솟수의합이다. 참임을확인해가는튜링기계를만들고멈춤문제풀이로해결 : (a, b, c, n) 를모두 훑으면서, a n + b n = c n 이면멈추는기계 모든짝수 k를 훑으면서, 두솟수 (p, q) 를 훑으면서, k p + q이면멈추는기계 UM 이만드는참인명제는, 명제에대한명제가아닌 차명제 (first-order predicates) 뿐으로한정된다. 예를들어, (M 이멈춘다는참거짓을알수없다 ) 는 차명제가아니다. 400 년의축적 : 컴퓨터의탄생 다른트랙 자동계산장치들 주판 600 년대사칙연산 : 파스칼 (Pascal), 꿈 : 인간논리의자동화 ( 기계화 ), Leibniz, Frege, Cantor, Hilbert, Gödel, Turing 튜링학생의불가능재증명논술에서나온소품보편만능의기계 (universal machine) 라이프니츠 (Leibniz) 830년대사칙연산이상 : 배비지 (Babbage) 920년대이후회계장부 (BM), 통계계산 (ABC) 계산내용을외부입력으로 : Mark(Harvard U), ENAC(U Penn) 점점보편만능의기계에가까워가고 튜링 : 튜링이던진디자인이올킬. 구현기술 : 그동안쌓인구현기술이신속히동원됨
다음 400년의 축적 다음 다음 400년의 축적 400년의 축적