[서울대학교 공과대학] 컴퓨터의개념및실습 1. Welcome Abroad

서울대학교 민상렬 교수님의 https://www.youtube.com/watch?v=5Ic_AhAFbco 영상을 보고 작성했다 1. 튜링머신 실제 compute 할 수 있는 것은 튜링 머신에서도 항상 풀 수 있다. Turing equivalence란 무한의 메모리와 시간이 주어진다면 실제 compute할 수 있는 것은 튜링 머신에서도 항상 풀 수 있기 때문에 슈퍼 컴퓨터로 풀 수 있는 문제는 데스크탑에서도 풀 수 있고, 데스크탑에서 풀 수 있는 문제는 핸드폰에서도 풀 수 있다는 것이다. 튜링 머신의 예시를 보자. 위의 테이프는 왼쪽, 오른쪽으로 무한한 길이를 가지고 있으며 read-write head를 가지고 있다. 헤드는 타임 스텝마다 1. read symbol 2. write symbol 3. mov..

2023.05.23