컴퓨터는 정보를 처리하는 기계다

요약

정의 : a machine that processes the information
정보의 정의: 섀넌의 정보이론(1948년)
- 정보는 어떤 사건의 불확실성을 정량적으로 표현한 것
- 사건 X가 있으면 사건 X의 정보량은 이 사건에 발생할 확률의 마이너스 로그승 $I(X) = -\log_2 P(X)$ $I (X) = - lo g_{2} P (X)$ ex) 주사위를 던져서 숫자 2가 나올 확률을 다른 사람에게 전달할떄 정보량
  - $log_26$
- 최소한 정보가 의미 있으려면 사건이 2개가 일어나야함

정보를 처리하기 위해선 위에서 기술한 정보의 상태를 변환할 수 있는 물리적 장치가 필요함
논리 연산자들
- NOT, AND, OR 등임
NOT 게이트는 트랜지스터를 통해 만들 수 있음
NOT, AND, OR을 이용해서 XOR게이트, NAND 게이트, NOR 게이트 6가지 게이트를 만들면 직접회로를 만들 수 있음
- XOR: 같으면 0, 다르면 1
- NAND: NOT + AND
- NOR: NOT + OR
직접회로에서 직접도를 높이면 우리가 알고있는 CPU가 됨

A ───-┬────────(XOR 게이트)──── S (Sum)
      │
      ├──(AND 게이트)── C (Carry)
      │
 B ───┘

1936년, 앨런 튜링(Alan Turing)
"On Computable Numbers, with an Application to the Entscheidungsproblem"*
- 튜링 머신은 다른 모든 튜링 머신을 시뮬레이션 할 수 있다.
- 어떤 구조를 만족하는 오토마타는 Turing Computable 한 문제를 범용적으로 계산하는데 사용될 수 있다
튜링 머신은 헤드와 테이프를 사용하여 기계적으로 계산을 수행하는 모델.
컴퓨터 과학에서 이론적으로 계산 가능한 모든 것을 설명하는 모델로 사용됨.
- 무한한 테이프(Tape): 데이터를 저장하는 공간 (무한한 길이)
- 읽기/쓰기 헤드(Head): 테이프에서 데이터를 읽거나 변경
- 상태(State): 현재 기계의 내부 상태
- 전이 함수(Transition Function): 현재 상태와 테이프 기호에 따라 새로운 상태로 전이하고, 테이프를 변경하거나 이동
튜링 완전성
- 모든 입력 x에 대해 유한한 시간내에 계산 가능하다.
- 불가능한 문제
  - 정지 문제
    - 어떤 튜링 머신 M과 입력 x가 주어졌을 때, M(x)가 언제든지 멈출지 아닌지 판별하는 문제
  - 주어진 논리식이 항상 참인지 판별하는 문제
오토마타 이론은 계산 가능성의 경계를 정의한다

1950년대 폰노이만 => 컴퓨터 아빠
폰노이만 아키텍쳐의 주요 개념
- 메모리
- 인스트럭션 셋 아키텍쳐
- 연산 장치
- 버스
인스트럭션셋 아키텍쳐를 이용해서 범용 컴퓨터를 만듦
- 프로그램 내장 방식: 내장형 프로그램 방식을 처음 도입한 사람,램에 프로그램을 올린다.
- 하나의 메모리 사용
- 순차적 실행 방식
  - CPU가 메모리에서 명령어를 읽고, 해석하고, 실행하는 순서로 동작
이전의 컴퓨터들은 특정 연산을 하드웨어적으로 설계 되었음
폰노이만 구조를 통해, 소프트웨어만 바꿔서 실행가능하게 됨

프로그램은 명령어의 집합