튜링 머신

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

폰 노이만 구조

• 일단 이전에 그래서 만들어진 방법으로 프로그래밍을 하는 것은 전설을 꼽고, Punched card와 같은 것으로 수행함
• Board 자체가 프로그램의 역할을 했었음
• 이제 이 대표적인 것이 에니그마.
  • 2차 세계 대전때 암호 해독할 때 사용한 장비
• 폰 노이만
  • 맨하탄 프로젝트 참여
  • 연산할게 너무 많아서 컴퓨터를 만들어버림

폰 노이만 구조(내장형 프로그램 방식 컴퓨터)

• 입력과 출력
• 기능 수행후 출력한다.
• CPU와 메모리가 존재
• 여기서 부터 프로그램이 메모리에 들어가게 된다.
• CPU
  • Control Unit (제어)
  • 산술 장치, 논리 연산 장치

현대 컴퓨터 구조

• 입출력도 분리됨
• 프로그래머는 입출력에 신경을 덜 씀
  • 운영체제가 알아서 해주니까
• bus
  • 내가 진자 타는 버스랑 같은 거다.
  • 데이터(정보, 이진수)를 실어서 나른다.
• Address bus, Data bus가 있고 왔다갔다 하는 구나!
• 메모리와 CPU가 직접 통신하는게 아니고 bus 를 통해서 간접적으로 통신하는구나! 정도만 일단 알아두자.

컴퓨터 메모리 구조

순차접근, 임의 접근

• 순차접근
  • 자기 테이프
  • 순차적으로 보면서 데이터를 찾는다.
• 임의 접근
  • 램은 임의 접근 방식으로 되어 있음
  • 주소와 저장 공간으로 나뉜 것.

CPU Memory

• 주소 통로와, 데이터 통로가 나뉘어 있다.
• 메모리는
  • 데이터를 보내주고
  • 저장하고
  • 이 두가지 일 밖에 하지 않는다.
• control bus는 데이터를 받을 것인지, 쓸 것인지를 요청하는 버스이다.

CPU 기본 구조

• 프로그램 : SSD -> RAM -> CPU
• 고수준 프로그래밍 언어 -> 어셈블리 언어 -> 기계어 (이진수)
• CPU 명령어 집합
  • ADD, COMPARE, IN.. 등 몇개 되지 않는다.

CPU 구성 요소

• ALU
  • 실제 연산 작업을 하는 곳
• 제어 장치
• 레지스터
  • ALU가 일을 하기 위해서 필요한 작업 공간

그래서 폰노이만 구조는?

• 1945년이 설계한 컴퓨터 아키텍쳐
• CPU, RAM, I/O 구조의 프로그램 내장 방식 범용 컴퓨터 구조
• 내장 메모리 순차 처리 방식
  • 동일한 메모리 내부에서 명령어와 데이터가 분리되지 않고 공존하는 구조.
  • 즉, 메모리 안에 명령어(LOAD), 데이터(“3”)이 공존
• CPU
  • ALU
    • 논리연산, 보수연산, 시프트 연산
  • Resister
    • 임시 저장 장치
    • 플립 플롭으로 구성
      • 무언가를 저장해야 한다?
      • 1bit 정보를 보관하고 유지하는 회로구조, 순서 논리회로의 기본 요소라고 함
  • Control Unit
    • CPU 제어 장치
• Bus
  • Control Bus
    • CPU 명령어 수행을 위한 제어신호 전송. 단방향이다.
  • Address Bus
    • CPU에서 주소에 관한 신호 전송. 단방향
  • Data Bus
    • CPU의 연산에 필요한 데이터 전송. 양방향
• Memory
  • 주기억 장치
    • 명령어와 데이터를 저장하는 기억장치. 반도체
  • 보조 기억장치
• 입출력 장치

폰 노이만의 구조에는 병목현상이 발생한다.

• 원인
  • 주기억 장치에 명령어와 데이터 모두를 저장하고 한번에 하나의 명령어를 처리한다.
  • 그렇기 때문에, 명령어와 데이터를 동시에 읽고 쓸수 없다는 문제가 발생
  • 그리고 CPU와 주기억 장치의 속도차이로 인해 병목이 발생
• 해결 방안
  • 명령어 병렬 처리
  • 하버드 구조
    • 물리적으로 명령어 용과 데이터 용으로 데이터 버시를 분리
    • CPU에 고성능 캐시를 활용하고 캐시도 명령어용과 데이터용을 분리

하버드 구조

• 폰노이만 구조의 문제점을 해결하기 위한 구조
• 메모리 속박 문제
  • 데이터 병목 현상
    • 이건 캐시로 해결하긴 함
• 명령어 메모리와 데이터 메모리를 분리하여 병렬적으로 처리하도록 구현한 컴퓨터 아키텍쳐

폰노이만, 하버드 구조

• 명령어 메모리와 데이터 메모리가 물리적으로 분리되어 있음
• 수정 하버드 구조
  • 메모리하고 CPU하고 속도 차이가 크기 때문에 결국 캐시도 분리해서 사용하겠다는 것.
• 구조는 모두 같고, 버스와 메모리만 변경됨
• 버스
  • 명령어 버스와 데이터 버스가 물리적으로 분리됨
• 메모리
  • 명령어 메모리
  • 데이터 메모리
  • 캐시 분리(수정하버드)
    • 명령어 캐시와 데이터 캐시를 물리적으로 분리
    • load와 store 명령어를 동시에 실행

References

• 튜닝 머신
• 폰 노이만 구조
• 정지 문제
• 메모리 구조
• CPU 일하는 방법
• 폰 노이만 구조