본문 바로가기

Computer Science/컴퓨터 과학이 여는 세계

컴퓨터과학이 여는 세계_4.2 수리논리학의 역사 및 자동계산기의 역사_이광근 강좌 동영상 튜링이 고안한 튜링기계는 매우 단순한 형태여서 그것을 실제로 만들 수 있다.테이프는 메모리 칩으로 테잎에 읽고 쓰는 장치는 메모리 입/출력 장치로작동 규칙표는 중앙 처리장치로 만들어서 나온 것이 우리가 지금 쓰고 있는 컴퓨터이다. 자동 계산 장치를 고안할려는 인간의 시도는 여럿 있었고 다음과 같다.주판 - 펜으로 쓰는것 다음으로 가장 원시적인 형태라고 생각한다.1600년대 파스칼 계산기 - 세금액을 다루시던 아버지를 돕기 위해 만든 수동 계산기이다. 덧셈, 뺄셈, 반복을 통한 곱셈과 나눗셈도 할 수 있다고 한다.[사진 출처 - 위키 백과]1830년대 배비지 - 배비지는 엔진을 재 디자인해서 계산기를 만드는 방법을 구상했었다. 1920년대 이후 IBM과 ABC 하버드에서 고안한 Mark 그리고.. 더보기
컴퓨터과학이 여는 세계_4.1 질의응답 및 멈춤문제를 자동으로 풀 수 있다면 가능해지는 일들_이광근 강좌 동영상 만약, 아주 만약에 멈춤문제를 증명하는 튜링기계를 만들 수 있다면 어떻게 될까?그렇게 된다면, 여러가지 수학난제들이 바로 해결된다.예를 들어보자골드바흐의 추측: 2이상의 짝수는 소수 두개의 합으로 이루어져 있다. (ex. 8 = 3+5, 12 = 5+7)페르마의 마지막 정리: 자연수 n > 2에 대해서 a^n + b^n = c^n인 자연수a, b, c는 없다. 다음 명제들을 튜링기계로 짠다고 했을 때, 하나씩 다 해보면서, 반례가 존재하는지 확인하는 튜링기계를 만들면 된다. 만들고 난 후, 멈춤문제를 증명하는 튜링기계에게 입력으로 준다. 그렇다면 멈춤문제를 증명하는 튜링기계는 딱 보고 유한시간만에 '이건 반례를 찾아서 끝나겠다.' 아니면 '반례가 없기 때문에 끝나지 않는다.'라고 나오는 것이.. 더보기
컴퓨터과학이 여는 세계_3.4 멈춤문제를 이용한 튜링의 불완전성 증명_이광근 강좌 동영상 멈춤문제: 어떤 튜링기계가 멈출지 멈추지 않을지를 정확히 판단해내는 문제 멈춤문제를 해결하는 튜링기계는 만들 수 없다! 이전에 한 튜링기계가 다른 튜링기계를 따라하는 튜링기계를 만들 수 있다고 하였다. 그런데 이번에는, 어떤 튜링기계를 입력받으면 그것을 쭉 살펴보고 유한시간이 지난 후 '유한시간만에 끝나겠다.' 혹은 '영원히 끝나지 않겠다.' 라는 것을 스스로 판별하는 튜링기계를 고안하려고 한다. 한편 모든 수리명제를 자동판결하는 튜링기계를 만들 수 있다면, 이 멈춤문제를 해결하는 튜링기계를 당연히 만들 수 있다. 그런데, 이 멈춤문제를 해결하는 튜링기계를 만들 수 없다. 따라서 모든 수리명제를 자동판결하는 튜링기계를 만들 수 없다. 다시 말하자면모든 수리명제를 자동판결하는 튜링기계를 만들 .. 더보기
컴퓨터과학이 여는 세계_3.3 멈춤문제를 푸는 튜링기계는 없다_이광근 강좌 동영상 무한의 세계에도 크기 차이가 있다. 예를들어 자연수의 갯수인 무한보다 자연수의 부분집합의 갯수가 더 많다. 또, 정수의 갯수인 무한보다, 실수의 갯수인 무한개보다 작다. 이를 칸토르(Georg Cantor)라는 수학자가 대각선 논법을 이용해 증명하였다. 먼저 자연수가 모든 자연수의 부분집합과 하나씩 대응할 수 있다고 가정한다. 그 후 표를 만드는데, 맨 윗줄에 자연수를 쭉 쓴다. 그후 왼쪽에는 자연수의 부분집합이 될 집합들을 쭉 쓴다. 각각의 부분집합 옆에는 부분집합안에 해당 자연수가 들어가면 'O' 아니면 'X'를 쓴다. 예를들어 위에 표에서, S1 = {2, 5, 6, ... }, S2 = {1, 2, 5, ... }, S3 = {1, 3, 4, 6, ... } .... 인셈이다. 이제 .. 더보기
컴퓨터과학이 여는 세계_3.2 보편만능의 기계 설계: 튜링기계의 하나_이광근 강좌 동영상 보편 만능의 기계(Universal Machine): 하나의 튜링기계이지만, 그 입력에 따라 모든 종류의 튜링기계를 흉내낼 수 있는 특별한 튜링기계 튜링기계는 자연수 하나로 나타내기도 하고, 1열로 쭉 쓸 수 있다. 즉, 어떤 튜링기계가 입력으로 받게 된다면 그 기계를 흉내내는 기계를 만들 수 있다. 이것이 보편만능의 기계, 우리가 컴퓨터라고 부르는 그것이다. 여기서 따라하는 튜링기계가 하드웨어이고, 입력으로 넣는 튜링기계가 소프트웨어이다. 더보기
컴퓨터과학이 여는 세계_3.1 튜링기계 만들기_이광근 강좌 동영상 튜링기계를 만드는 것은 소프트웨어를 만드는 것이다. 물론 아주 Low-Level 언어이기 때문에 쓰는 사람은 거의 없겠지만 말이다. 사람들은 주로 High-Level 언어를 사용해 튜링기계를 만들게 된다. 저번에 예를 들었던 튜링기계를 살펴보자. 이 기계는 '튜링 머신'이라는 포스팅에서 설명했듯 '$'심볼을 맨 오른쪽에 옮기는 일을 한다. 그렇다면 이때 기계의 상태는 무엇을 나타낼까? 우선 저 표를 순서도로 나타내보자.(조금 더 복잡해진것 같지만 기분 탓이니 상관하지 말자...) 이 그림을 보면 A상태는 '$'심볼을 찾은 뒤에는 다시 돌아오지 않는다. 또 찾은후에 B와 C상태를 왔다갔다 한다. 따라서 이 기계의 상태는 다음과 같이 해석할 수 있다.A: '$' 찾기 (찾으면 B로! 아니면 계속.. 더보기
컴퓨터과학이 여는 세계_2.4 튜링기계의 급소: 튜링기계 하나는 자연수 하나_이광근 강좌 동영상 Enumeration of computable sequence 튜링기계 하나를 한개의 자연수로 표현이 가능하다.일단, 튜링기계는 테이프와 그 위에 써질 심볼, 규칙표 그리고 기계의 상태가 필요하다.이것들을 각각 1열로 나열하면 어떤 진수로 표현할 수 있다.이것이 무슨 말이냐 하면 만약 심볼이 1, 2, 3, 4, ... , 9, 0 이 써져있다고 하자. 그렇다면 이것을 1열로 나열하였을 경우 1234567890이 된다. 이것은 10진수로 나타내어진 자연수로 볼 수 있다. 또, 만약 심볼이 1, 2, 3, 4, ... , 9, 0, *, # 이라고 하자. 그렇다면 1234567890*# 이 된다. 이것은 12진수로 생각해서 *은 11로 #은 12로 나타낸채로 계산을 하면 된다. 이것을 N(1).. 더보기
컴퓨터과학이 여는 세계_2.3 튜링기계의 예2_이광근 강좌 동영상 다음과 같은 숫자열을 만드는 튜링기계 설계하기1) 0 1 0 1 0 1 0 1 0 1 0 ...2) 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 .... 1번 2번우선 이런 상태에서 시작한다고 했을 때( '-'는 상관 없음을, '||'는 그대로를 의미한다.) 더보기
컴퓨터과학이 여는 세계_2.2 튜링기계의 예1_이광근 강좌 동영상 튜링기계로 테이프에 쓰여진 심볼을 복사할 수 있다. 예를 들어 0110을 복사하여 0110110을 만든다고 해보자. 이 때 밑에 그림과 같이 마커를 이용해 빈 공간에 마커가 가리키는 심볼을 쓰고, 마커와 기계의 위치를 하나씩 오른쪽으로 이동해 같은 내용을 반복하면 된다. 그런데, 튜링기계에 마커라는 도구는 없지 않았나? 어떻게 마커가 등장한 것이지 라고 생각할 수 있다. 허나 이 마커는 실제 튜링기계에서 다음과 같이 각 심볼뒤에 마커가 위치할 수 있는 빈공간이 하나씩 있다고 생각하자. 이렇게 한다면, 튜링기계 하나에 모두 표현할 뿐더러 기계가 마크를 옮기는 것까지 고려해 튜링기계를 만들 수 있다. 따라서, 튜링기계는 위와 같은 방법으로 복사가 가능하다. 더보기
컴퓨터과학이 여는 세계_2.1 기계적 계산의 정의: 튜링기계_이광근 강좌 동영상 귀델은 기계적인 방식으로 모든 참인 명제를 만들어 낼 수 없음을 풀리지 않는 문제를 풀기 위해 기계를 계속 확장하여도 풀어낼 수 없는 문제가 계속 나온다는 것을 증명하였다. 튜링은 이 증명을 듣고 자신만의 방법으로 튜링기계를 만들어 증명하고자 했다.(튜링기계에 대한 설명은 이쪽으로) 이 기계를 만들고 이것으로 계산하는 것만 기계적인 방법이라고 정의를 내렸다. 그 후 이 기계가 충분히 기계적임을 대표한다는 것을 보이기 위해 여러 방법으로 설득을 한 뒤에 이 기계로도 풀리지 않는 문제가 있음을 밝혔다. 이 기계가 확장되고 확장되어 Universal Machine인 오늘날의 컴퓨터가 되었다. 더보기

티스토리툴바