2023. 5. 23. 17:51ㆍ카테고리 없음
서울대학교 민상렬 교수님의 https://www.youtube.com/watch?v=5Ic_AhAFbco 영상을 보고 작성했다
1. 튜링머신
실제 compute 할 수 있는 것은 튜링 머신에서도 항상 풀 수 있다.
Turing equivalence란 무한의 메모리와 시간이 주어진다면 실제 compute할 수 있는 것은 튜링 머신에서도 항상 풀 수 있기 때문에 슈퍼 컴퓨터로 풀 수 있는 문제는 데스크탑에서도 풀 수 있고, 데스크탑에서 풀 수 있는 문제는 핸드폰에서도 풀 수 있다는 것이다.
튜링 머신의 예시를 보자.
위의 테이프는 왼쪽, 오른쪽으로 무한한 길이를 가지고 있으며 read-write head를 가지고 있다.
헤드는 타임 스텝마다 1. read symbol 2. write symbol 3. move head left or right 3가지 동작을 수행할 수 있다고 하자.
x와 y가 unary로 표현이 될 때 0만 옮기면 x+y를 표현할 수 있다.
앞서 말한 튜링 머신에서는 해당 컴퓨테이션을 어떻게 풀면 될까? 다이아몬드로 input의 경계가 표현이 되고, 0이 x와 y의 구분자이고 헤드가 q0에 있다고 하자. 0을 만나면 1로 바꿔주고 다이아몬드를 만나게 되면 마지막을 0으로 바꿔주면 된다. 헤드는 계속 왼쪽으로 가다가 다의아몬드를 만나면 그 오른쪽으로 헤드를 위치해주면 된다.
그 흐름을 구현한 프로그램이다.
2. 유니버설 튜링 머신
input을 튜링머신과 계산해야할 input도 받는다. (컴퓨터가 프로그램도 받고 데이터도 받는 것과 마찬가지이다)
U는 프로그래머블 하다.
3. Halting Problem
그렇다면 튜링 머신으로 풀 수 없는 문제도 있을까? Undecidable problem이 있는데 이러한 문제는 튜링 머신으로도 풀 수 없다.