교재 : 컴퓨터 과학 총론 (13th Edition) (책으로 공부하며 작성한 글입니다.) 1. 함수와 함수의 계산 - 수학에서 함수(function)는 가능한 입력 값의 집합과 출력 값의 집합 사이에서 하나의 가능한 입력에는 하나의 출력만이 배정되는 대응 관계를 말한다. - 주어진 입력에 대해 함수가 배정하는 출력을 결정하는 과정을 함수의 계산이라 부른다. - 수학에서 도출된 중요한 결론 중 하나는 어떤 함수들은 너무 복잡해서 이들의 경우 입력 값에 기초하여 출력을 결정하기 위해 사용할 수 있는 잘 정의된 단계 과정이 존재하지 않는다는 것이다. -> 계산 불가능한 함수 2. 튜링 기계 (Turing machine) 1) 튜링 기계의 원리 - 읽기/쓰기 헤드를 사용하여 테이프 상에 기호를 읽고 쓸 수 있..
