컴퓨터는 만능인가

범용성 universality

• NOT, AND, OR 게이트만으로 모든 계산을 할 수 있다.
• NOT, AND, OR말고 NAND 게이트 하나만으로 모든 계산을 할 수 있다.
• 범용 컴퓨터 general-purpose computer: 범용성을 가진 컴퓨터

계산가능성 computability

• Turing-computable: 튜링 머신으로 계산이 가능한 것
• 정지 문제 Halting Problem: 튜링 머신으로 풀 수 없는 문제

컴퓨터는 누가 만들었는가

• 앨런 튜링의 튜링 머신 논문 발표: 현대적 컴퓨터의 원형이 됨
• 존 폰 노이만의 ISA: Instruction Set Architecture 실제로 동작하는 컴퓨터 구조의 원형

유니버설 튜링 머신 UTM

• 튜링의 튜링머신 구조
• 헤드는 CPU, 테이프는 메모리, UTM은 운영체제가 됨

폰 노이만 아키텍처 ISA

• 메모리에 프로그램이 저장되어 이를 불러와서 사용하는 구조

프로그램이란?

• 명령어들의 집합

운영체제도 프로그램인가?

• 운영체제는 상시 실행되는 컴퓨터 프로그램
• 하드웨어단을 감싸고 시스템 서비스를 응용 프로그램에게 제공
• 프로세스, 자원, UI 등을 관리함