Computer $\in$ UTM
All methods of computing can be performed on UTM
Computers == UTM
처치 튜링 가설
알고리즘으로 할 수 있는 모든 일은 튜링 기계로 실행 가능하다.
충분한 시간과 공간이 주어진다면 모든 컴퓨터는 모든 알고리즘을 실행 가능
사람과 컴퓨터와 대화했을 때 둘을 구분하지 못하는가?
어느 방 안에 중국어를 모르는 사람(이하 참가자)이 들어간다. 이후 참가자는 중국어로 된 질문과 이에 대응하는 적절한 중국어 응답이 적힌 지시사항의 목록, 그리고 다른 사람과 소통하기 위한 필기도구를 제공받는다. 이 상태에서 중국인 심사관이 중국어로 질문을 써서 방 안으로 집어넣는다면, 참가자는 중국어를 전혀 모르더라도 목록을 토대로 알맞은 대답을 중국어로 써서 심사관에게 건넨다.
중국어를 모르는데도 중국어를 하는 것처럼 보인다.
알파고도 바둑이 뭔지는 모르지만 바둑을 잘 둔다.
Searle’s Claim 튜링 테스트를 통과하더라도 “이해”하고 있는 것이라고 할 수 없다. ****
계산 불가능한 문제가 있을까?
특정 프로그램의 정지 여부를 판단할 수 있을까?