Turing Machine

튜링 머신

• 다비트 힐베르트
  • 20세기 가장 위대한 수학자
  • 힐베르트 문제가 이 아저씨
  • 힐베르트의 꿈
    • 정의(def)와 공리(axiom)를 입력하면 모든 수학적 명제를 도출해 줄 수 있는 기계를 만들자
• 쿠르트 괴델
  • 힐베르트의 꿈을 박살냄 ㅎㅎ
  • 불완전성 정리
    • 기계적인 방식으로 모든 수학적 명제를 도출할 수 없다.
• 앨런 튜링
  • 수학만으로 컴퓨터를 만든 컴퓨터 과학의 아빠
  • 괴델의 증명 리메이크 프로젝트
  • 정지 문제
    • 모든 계산을 할 수 있는 보편적 만능 기계를 만들어 두자.
    • 근데 이 기계가 못푸는 것이 있어
    • 증명 끝
    • 결국 방식은 동일함
  • 근데 웃긴게, 이 기계를 만드는 과정이 Computer의 원형이 됨
  • 계산 가능한 수에 대하여, 결정 문제에 대한 응용을 포함한 이라는 논문
• 그래서 튜링 머신은?
  • 어떤 기록할 수 있는 테이프가 있어
  • 그 안에는 기호가 있어
  • 그리고 그 테이프에 read, write를 할 수 있는 장치, 즉 헤드가 있어
  • 그리고 그 헤드는 상태를 가지고 있어
  • 테이프
    • 기호 하나를 읽고 쓸 수 있는 셀이 무한히 연결된 기억 장치 (메모리)
  • 헤드
    • 현재 위치한 셀을 읽고 쓰거나 좌우로 이동할 수 있는 제어장치 (CPU, 프로세서)
  • 기호 집합
    • 테이프에 읽고 쓸 수 있는 기호들의 집합 (정보, 숫자, 문자, binary data)
  • 상태 집합
    • 튜링 머신이 가질 수 있는 상태들의 집합
  • 명령 테이블
    • 현재 상태와 기호에 따라 해야할 일을 지정하는 명령 목록

• 기호 집합
  • X = {0, 1}
• 상태 집합
  • S = {s0, s1, H}
  • s0 : 초기 상태, H : 종료 상태

• 해당 영상을 보게되면, 이를 통해 메모리에 15를 기록하는 방법을 소개한다.
  • n 상태 바쁜 비버 문제
  • 유한 상태 오토마타
• 튜링 머신이 할 수 있는 것
  • 이론적으로 계산 가능한 모든 것을 할 수 있다.
    • 컴퓨터는 못한다. 왜? 무한대의 메모리 공간을 가질 수 없기 때문에.
  • 모든 정보는 0, 1로 표현 가능하다. 이를 비트라 한다.
    • and, or, not 연산이 가능(Bool 대수) → 사칙 연산 가능 → 모든 연산 가능
    • 결과적으로 모든 정보에 대해 보편적으로 연산이 가능한 장치
  • Universal Turing Machine
    • 임의의 튜링 머신 M의 명령 테이블을 보고
    • 그것을 따라하는 튜링 머신 UTM을 만들 수 있다.
  • 해당 영상의 22분 부터 보면 이해가 가능

UTM과 운영체제

• 결론만 말하면, 우리가 사용하는 컴퓨터 아키텍처에서 응용프로그램은 TM
• 이 TM들을 만들수 있는 녀석이 UTM이라고 이해할 수 있다.
• 여기서 이제 폰 노이만 아저씨가 나오는데, 이러한 개념을 바탕으로 이 체계를 만든 사람이다.
• 여기서 차이는 뭐냐면, TM은 상태에 따라 움직이게 되는데, 폰 노이만의 아키텍처는 절차(procedure)를 기준으로 작동한다.
• 결론
  • TM : 프로그램
  • UTM : TM을 돌려주는 프로그램 - 운영체제
  • 그런데, 여기서는 무한대의 테이프가 필요. 아직 달성하지 못함
  • 앨런 튜링이 AI를 제시함.
  • 진정한 튜링 머신 = 궁극의 인공지능
  • Turing Compatable할 수 있느냐가 연구 주제임