🥚

Recent Notes

See 20 more →

Turing Machine

5 min read

튜링 머신

  • 다비트 힐베르트
    • 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할 수 있느냐가 연구 주제임

Graph