- Turing Machine의 기본개념 Turing Machine은 Tape을 이용한 오토마타이다. - tape에는 input이 들어가 있고, TM은 tape에서 read와 write 모두 가능하다. - input을 왼쪽에서 오른쪽으로만 읽는 기존의 machine들과 다르게 Left, Right, Stay방향으로 진행 가능하다. (stay의 경우 left right 두번이라고 생각하면 된다) - tape는 infinite한 성질을 가지는데, 맨 왼쪽에서 leftmove할경우 무시하고, rightmove할 경우 blank(오른쪽으로 무한한 blank를 가진다고 이해하면 쉽다)을 계속 읽을 수 있다. - TM이 accept나 reject되지 않고 loop를 가져서 무한히 동작할 수도 있다. 모든 input..
0. 캐시 메모리란? 그 필요성 메모리를 계층적으로 재구성하여 빠르고 큰 메모리인것처럼 Processor(CPU)를 속이는 것. 일반적으로 빠른 메모리는 비싸고 크기가 작고, 느린 메모리는 싼 대신 크기가 크다. 빠른 메모리를 프로세서 가까이에, 느린 메모리는 그 밑에 계층적으로 배치하고, 데이터 지역성을 활용하여 효율적인 메모리 구성이 가능하도록 한다. 데이터 지역성 시간 지역성 한번 참조된 데이터는 곧 재참조될 가능성이 높다는 것을 의미. loop문을 생각해보면 이해가 편하다. 공간 지역성 배열구조처럼 같은 데이터 배열에 연속적으로 접근할때 참조된 데이터 근처에 있는 데이터가 재참조될 가능성이 높음을 의미. -Block : 데이터 전달의 최소단위. -Hit : CPU가 원하는 데이터가 상위계층에 존재..