컴퓨터 과학공부1

1챕터 어떤 질문에도 대답해 주는 인공지능 : 궁극의 기계 질문을 하고 답변을 해 주는 것을 기계로 정의 하자. 지능에 대한 논의를 '문제가 주어 졌을 때 그 문제를 어떻게 해결'하는지로 좁혀서 생각하자. 문제를 푸는 절차를 알고리즘이라고 한다. 알고리즘에 관한 이론이 현재 "계산 이론"이라고 일컬어 진다. 이 계산이론을 바탕으로 컴퓨터가 발전했다. 알고리즘은 소프트웨어. 뇌는 하드웨어. 알고리즘을 실행하는 기계를 최초로 생각한 사람은 튜링. 튜링기계는 무한히 긴 1개의 테이프와 그 테이프에 쓰여진 문자를 읽고 쓰기 위한 헤드가 한개 붙어 있는 구조. 할 수 있는 것은 왼쪽이나 오른쪽으로 한칸씩 이동, 테이프에 글자를 쓰거나 읽는 것 음.. 이게 어떻게 능력을 발휘하는 건지는 추후에.. 힐베르트의 23개의 미해결 문제 중 <주어진 명제의 정리 여부를 판정하는 알고리즘 찾기> 여기서 그 때 당시 알고리즘은 기계적으로 실행할 수 있는 명확한 지침의 집합으로 표현되어 사용되었다. 특히 10번째 문제 디오판토스 방정식이 유리수해를 갖는지 판단하는 절차(알고리즘) 구하기가 있다. 처음부터 알고리즘이 존재하지 않는다는 생각을 하지 않았으나, 러시아 수학자 마티야세비치가 해당 문제를 푸는 알고리즘이 존재하지 않는다는 것을 증명함. 이를 계산 불가능 문제라고 한다. 이는 튜링이 알고리즘이 존재하지 않는다는 것은 <튜링기계로 계산할 수 없는 것>이라 규정한 것과 같음. 비슷하게 괴델의 불완전성 정리도 본질적으로 같은 논리임. 이는 곧 계산할 수 없는 문제의 존재, 기계의 한계를 말한다. 그렇지만 여기서 부터 오히려 컴퓨터 과학 등에서 많은 이론이 생성되어 발전하였다. 즉, 알고리즘이 없다는 것은 어떤 말인가가.. 알고리즘이란 무엇인가로 다시 주목을 받음. 괴델 수(명제와 같은 대상을 수치화해서 숫자로 처리 -> 비트열) 촘스키의 성구구조문법.. 생성문법으로 발전.. 즉, 인공언어의 설계와 해석..으로 발전.

2챕터 튜링은 대각선 논법을 사용하여 <계산할 수 없는 문제>가 있다는 걸 증명했다. 이 논법은 모순, 크레타 사람은 거짓말쟁이다. 역설 같은 거다. 여기서 수학적 귀납법을 살펴 보자. 이 논법은 중요하다. 일반적인 귀납법과는 다르다. 순환 논법이 되지 않게 세심하게 사용하면 강력한 증명 도구가 된다. 흔히 특수한 예에서 보편적 명제를 도출하는 것이 일반적 귀납법이라면, 수학적 귀납법은 특수한 예들 n개가 성립하면 n+1도 성립함을 증명하여.. 모든 수에 대해 항상 성립함을 증명하는 것이다. 이것이 어떻게 적용되는지는 추후에...

3챕터 현대수학은 매우 엄격한 형식주의로 만들어져 있다. 1챕터의 내용을 상기. 그래서 자연수를 정의하여 사용한다. 완전히 정의 하지 않고 사용하면 오류가 발생. 즉, 계산 할 수 없는 문제가 발생한다. 정의와 공리 내에서 문제에 답을 내고.. 정의와 공리는 그 논리적 세계를 이룬다. 1) 제로는 자연수이다. 2) x가 자연수라면 x의 후자는 자연수이다. 3) 1)과 2)에서 정의된 것만이 자연수이다. 자연수가 충족해야 할 기본적인 성질을 자연수의 공리라고 한다. 공리1) 제로는 어떤 자연수의 후자도 아니다. 공리2) 다른 2개의 자연수는 각각 다른 후자를 가진다. 공리3) 제로가 어느 성질을 가지고, 어떤 자연수가 그 성질을 가지고 있을 경우, 그 다음 숫자도 같은 성질을 가진다면, 모든 자연수는 동일한 성질을 가진다. <공리3은 수학적 귀납법의 원리>를 나타내고 있다.(챕터2이 내용) 기저: 제로가 어느 성질을 가진다. 가정: 어떤 자연수가 그 성질을 가진다. 단계: 그 다음 숫자도 그 같은 성질을 가진다. 증명: 모든 자연수가 그 성질을 가진다. 이렇게 수학적 귀납법이 중요한 이유는...추측하자면, 엄격한 형식주의의 수학에서 강력한 증명 도구가 되기 때문?

4챕터 알고리즘을 실행하는 기계(튜링기계, 계수기계 등) 기계를 움직이는 알고리즘(흐름도, 기계어 등) 이제 실제 기계가 어떻게 사고하고 문제를 풀어 가는지 생각해 보자. 계수기계를 가지고 설명.