제5장 자동기계 Automaton

(1)

제5장 자동기계 Automaton

2013. 09. 02

가천대학교

(2)

목 차

5.1 마음과 기계 5.2 튜링기계 5.3 자기증식기계

5.4 알고리즘

익힘 문제

(3)

3

5.1 마음과 기계

Automaton

자동기계, 자동장치, 로봇 같은 사람, 복잡한 사고나 판단도 할 수 있는 기계.

Why Automaton?

신이 자신의 형상에 따라 인간을 만들듯이,,,,

오랜 옛 부터 사람들은 자신과 같은 기계를 꿈꾸었다.

인지과학의 핵심

기계가 인간의 마음을 구사할 수 있다면  기계가 정신노동 가능

인간의 마음을 분석해야만 기계화 가능.

인간의 마음을 기계로 유추하는 것.

Automaton: 어원은 자동기계라는 뜻의 그리스어. 인간의 특정한 행동을 수행할 수 있는 복잡한 기계 장치. 단순 계산으로 시작하여 스스로 학습 능력을 발휘하여 창작활동까지 할 수 있는 기계.

인공두뇌.

(4)

자동기계

사람은 왜 사람 같은 기계를 만들려고 하는가?

기계에도 마음이 있는가?

마음이란?

사람은 왜 마음을 기계로 유추하려는가?

사람과 기계는 무엇이 다르고 무엇이 같은가?

Computer Science의 목적

왜 사람과 같은 컴퓨터를 만들려는 것일까?

ex. 월급계산, 청구서 계산 및 발행 등의 간단한 업무에서 복잡한 의사 결정 업무 등을 위하여

가능할까? 가능하다면 언제일까?

어린 아이도 잘 가르치면 말을 하는데,,, 컴퓨터는?

중장비가 인간을 중노동에서 해방시켜주었듯이

컴퓨터가 정신적인 중노동을 해방시켜주기를 기대.

마음: 인간이 정보를 처리하는 과정

(5)

5

5.1 마음과 기계

Machine

기계 :

일정한 운동에 의하여 일을 하는 동적 장치

자동기계 :

주어진 일을 스스로 수행하는 동적 장치

Computer?

언어로 정보를 처리하는 전기 기계.

유한 상태 기계 finite state machine

다목적 기계? 프로그램에 따라서 다양한 일을 할 수 있으니까 인간의 마음: 프로그램?

프로그램 ?

기계: 다수의 부품으로 구성되어 일정한 상대 운동에 의하여 유용한 일을 하는 동적 장치

(6)

5.1 마음과 기계

기계의 발전

다음 두 기계의 차이점은?

- 단순한 동작과 복잡한 기능의 차이?: 상태 기억, 상태 변환

자동판매기

배 배 배 배 배

배 배 배

배 배 배 배 배

배 배

배 배 배 배 배 배 0

100

200 300

배 배 배 배 배

배 배 배 배 배 배 배 배

배 배

배 배 배 배 배 배 500

400

(7)

Gate Flip-Flop

7

5.1 마음과 기계

기계의 발전

상태 ? 유한 상태 기계?

컴퓨터: 게이트: 단순 연결 플립플롭: 상태 기억

두 뇌: 100억 개 이상의 신경세포의 연결. 수상돌기와 축색돌기

회로 소자 기억소자

(8)

5.1 마음과 기계

기계 :

물리적인 일 + 정신적인 일 복잡한 일을 하는 도구.

일련의 규칙에 의하여 일련의 조작을 수행하는 체계

자동기계 Automaton

제어 기구에 의하여 복잡한 동작을 스스로 실행하는 체계

Descarte:

동물 = 마음이 없는 순수한 자동기계 인간: 신체(자동기계)+마음(비기계).

La Mettrie:

인간의 마음 = 기계. 유물론자 唯物論者

(9)

9

5.1 마음과 기계

Pascal

1645년 +, - 계산기 제작

인간의 생각 = 기계적인 요소. 이성 : 기계적 = 감성 : 비기계적.

계산기의 동작  인간의 마음을 유추

Leibniz

인간의 사고 = 숫자 계산

인류 공용 언어 = 논리적 체계 = 언어는 내포와 외연 관계로 표현 + - / * 를 모두 할 수 있는 계산기 개발

(10)

5.1 마음과 기계

Babbage

모든 유형의 계산이 가능한 계산기 설계. Leibniz 기반.

자료, 명령어, 계산의 3 요소로 실행. 미 구현.

Boole

수학 계산 = 체계적인 상징 조작 절차.

논리학 + 계산 수학  기호논리학 출발

성과

- 수리적인 계산을 체계적으로 기술하면 기계로 수행 가능 - 기계적 계산 과정 = 인간의 이성적 사고

(11)

11

5.2 튜링기계

셈이란 무엇인가?

Alan Turing의 생각

계산 과정 = 논리적인 사고 상태, 입력, 상태 변환, 출력

0 5 8 12

덧셈 준비 5 더하기 3 더하기 4 더하기는?

0 5 8 12

12 상태

출력

상태 변환 상태 변환 상태 변환

Alan Turing: 케임브리지 킹스칼리지 수학 전공.

컴퓨터 최초 개발. 독일군의 암호인 ‘애니그마’를 해독하는 컴퓨터 개발.

조깅하다가 인간의 사고 기능을 생각하여 기계 발명.

(12)

5.2 튜링기계

튜링의 생각을 객관화

오토마톤: 디지털 컴퓨터의 추상적 모델 유한 자동기계, 유한 상태 기계

유한한 수의 입력과 상태와 출력

전산학 computer science?

Def.

Science of Algorithm

문제를 해결하기 위한 처리 절차를 연구하는 학문.

절차  계산 절차  유한한 단계의 명확한 계산 절차

처리 절차 = 마음 = SW?

(13)

13

5.2 튜링기계

5.2.1 자동기계 이론 알고리즘 Algorithm

유한한 단계를 거쳐서 문제를 해결하기 위한 절차 명확한 처리 절차 = 기계적으로 처리할 수 있는 논리

.

Hilbert의 문제?

모든 수학 문제를 풀 수 있는 알고리즘이 존재하는가 안하는가?

Turing의 답은?

튜링 기계가 할 수 있는 일?

명확한 절차(처리)가 할 수 있는 일

무하마드 알콰리즈미: 9세기 페르시아의 수학자 천문학자. 알고리즘의 유래

(14)

5.2 튜링기계

5.2.1 자동기계 이론 힐버트의 문제?

- 모든 수학 문제를 풀 수 있는 일반적인 알고리즘은 존재하는가? 1900년 제시.

- Alan Turing이 그림과 같이 답을 제시

모든 수학 문제

처리 단계들을 명확하게 표현할 수 있는

문제

기계로 풀 수 있는 문제

알고리즘으로 기술할 수 있는 문제 알고리즘으로

기술할 수 없는 문제 기계로 풀 수 없는 문제

(15)

15

5.2.2 튜링 기계

튜링기계

- 테이프, 헤드, 제어장치로 구성된 자동기계 모델.

문자 집합 C = {0, 1} or C = {a, b, c}

상태 집합 S = {S₁, S₂, … , S_n}

제어장치 S₁ S2 S₃

1

테이프

상태 헤드

알고리즘(함수)

0 0 1 1 1 0 0 0 0 1 1 1

(16)

16

5.2 튜링기계

기계 M = (S, C, δ, H)

상태 집합 S = {S₁, S₂, … , S_n}

문자 집합 C = {0, 1} or C = {a, b, c}

δ: transfer function H: holting state S₀

Transfer Function

입력 결과

δ : S ⨉ C → C ⨉ {L, R} ⨉ (S ∪ {S₀}) 상태,문자 문자, 이동, 상태

(17)

17

5.2 튜링기계

>>> 예제 5.1 튜링 기계 M

₁

S = {S

₁

}

C = {0, 1}

δ : S

₁

⨉ (0, 1) → (0, 1) ⨉ {L, R} ⨉ (S

₁

, S

₀

) H = {S

₀

}

모든 전이 함수



δ(S

₁

, 1) = (S

₁

, 1, R)



δ(S

₁

, 0) = (S

₀

, 1, R)

y = f(n) = n + 1

내부 상태: S1 내부 상태: S1

1 1 1 0 0 1 1 1 0 0

(18)

5.2 튜링기계



δ(S

₁

, 1) = (S

₁

, 1, R) 1번



δ(S

₁

, 0) = (S

₀

, 1, R)

2번

3번

4번

입력

상태 0 1 비 고

S₁ 1, R, S₀ 1, R, S₁ 출력, 방향, 다

1 1 1 0 0 1 1 1 0 0

내부 상태: S₁ 내부 상태: S₁

1 1 1 0 0 1 1 1 0 0

S₁ S₀

1,1,R

0,1,R

(19)

19

5.2 튜링기계

튜링기계와 컴퓨터의 비교

구분 튜링 기계 컴퓨터 비 고 처리기 제어장치 CPU

주기억장치 내부 상태 RAM

보조 기억장치 테이프 디스크/테이프/,,,

프로그램 전이 함수 C, C++, BASIC 추론 규칙

(20)

20

5.2 튜링기계

>>> 예제 5.2 튜링 기계 M

₂ // 모든 문자 a는 b로 변환하라

S = {S₁} C = {a, b}

K = {a, b, □} // □는 공백 문자

δ : (S₁) ⨉ (a, b, □) → (a, b, □) ⨉ {L, R} ⨉ (S₁, S₀) H = {S₀}

모든 전이함수

δ(S₁, a) = (S₁, b, R) δ(S₁, b) = (S₁, b, R) δ(S₁, □) = (S₀, □, L)

(21)

21

5.2 튜링기계

… 예제 5.2

입력

상태

a b □

S

₁

b, R, S

₁

b, R, S

₁

□, L, S

₀

S1 S0

a, b, R

, , L

b, b, R

a b a

b b a b b a

b b a

b b a b b b

b b b b b b

(22)

5.2 튜링기계

>>> 예제 5.3 튜링 기계 M

₃

입력: {0, 1}

문자의 수가 홀수 개인지 짝수 개인지 판단하는 기계

구성 요소는?

전이 함수 도표는?

전이 함수표는?

실제 진행 과정은?

(23)

23

5.3 자기증식기계

Why Self-replicating Machine?

생물이란 무엇인가?

생물의 특징

순서 내 용 비고

1 번식 유전 정보 복제

2 물질대사 탄수화물, 단백질 등 필요

3 내·외부로 이동 운동

4 성장 에너지와 물질 필요

5 자극에 반응

(24)

5.3 자기증식기계

Why Self-replicating Machine?

기계가 생물처럼 새끼를 낳을 수 있다면?

새끼가 또 새끼를 낳을 수 있다면?

자기증식기계

(생물의 생식작용처럼) 자기와 같은 기계를 생산하는 기계.

생물이란 생물의 특성은?

Bacteria, Virus, Prion은 생물인가 아닌가?

(25)

25

5.3 자기증식기계

Hod Lipson의 자기증식기계

2005년 전동 로봇 실험 성공. by 코넬 대학의 호드 립슨.

Nature지 발표

이 로봇은 생물인가 무생물인가?

기존 생물의 조건을 모두 충족하면 생물인가?

로봇 친구가 있는데 죽을 때까지 친구가 로봇인 줄 몰랐다면 로봇에 의 식이 있는 것 아닌가?

(26)

5.3 자기증식기계

생물의 번식과 DNA

생물의 번식 조건: 유전자 전달 유전자gene란?

DNA로 구성(나선구조의 뼈대와 4가지 염기)

DNA Deoxyribonucleic acid

1) (자식에게 전달) 유전 정보 복제.

2) 단백질 합성.

DNA를 RNA에 복제하는 전사 기능.

RNA를 단백질로 바꾸는 번역 기능.

(27)

27

5.3 자기증식기계

DNA 기능

순서 내 용 비고

1 유전자

저장과 복제 유전 정보 저장 및 복제(번식할 때)

2 단백질 합성

전사 단백질을 합성: DNA를 RNA에 복제 번역 RNA를 단백질로 바뀌는 번역

(28)

5.3 자기증식기계

체세포 분열

세포의 증식(번식) 과정

배 배 배

1) 배 배 배 배 배 2) 배 배 배 배 배 3) 배 배 배 배 배 4) 배 배 배 배

(29)

29

5.3.2 폰 노이만의 자기증식기계

보편기계 Universal Machine

기계 M’은 M’’을 만들 수 있는가?

I

_M

: 기계 M의 설계도

I_M

배 배 배 배

배 배 배 배 배 배 기계제작

A

M M’

배 배 기계제작

A

배 배 배 배

(30)

5.3 자기증식기계

Von Neuman의 자기증식기계 설계도

1) 자식기계를 만들 때 설계도로 사용.

2) 자식 기계에게 복제 기능을 제공하기 위한 설계도로 사용

IM

배 배 배 배

기계제작 A

M IM 복제

B IM 이식

C

IM

M’

기계제작 A IM 복제

B IM 이식

C

(31)

31

5.3.3 공작기계 실례

공작 기계의 실례

조선소/강교의 철판 재단

배 배 (배 배 배 )

배 배 (배 배 배 배 ) 제작

기능 (CAM)

배배배배배 배 배 배

(배 배 배 CAD)

CNC 가스 절단기

강교: 강철 교량. 수 많은 철판 조각들을 재단, 용접, 리벳팅하여 제작.

CAD로 부품을 설계하여 파일을 재단기에 보내고, 철판 위를 재단기가 돌아다니면서 설계도를 그리고, 설계도를 따라서 가스절단기가 철판을 분리해낸다.

(32)

5.3 자기증식기계

공작기계

부모기계가 자신이 만드는 제품을 만드는 공작 기계를 만들 수 있으나 자식 기계는 새로운 자식 기계를 만들지 못한다. Why?

(a) 부모 기계 (b) 자식 기계

배 배

배 배 제품 배 배

제작 배배배배배 배 배

배 배 배

기계 배 배 제작

배 배

제품 제작

기계 제작

배배배배배

배 배 배 배 배

(33)

33

5.3 자기증식기계

공작기계

자식 기계에게 공작기계 설계도를 이식시킬 수 있으면 자식 기계도 새로운 자식 기계를 만들 수 있다.

(a) 부모 기계 (b) 자식 기계 자기 증식이 가능한 기계

제품 제작

배배배배배 배 배

배 배 배

기계 배 배 제작

배 배

제품 제작

기계 제작

배 배 배 배 배 설계도

복제

설계도 복제 배 배 배 배 배 (1) 배 배 배 배

(2) 배 배배배 배

배배배배배

(34)

34

5.4 알고리즘

Algorithm

아랍의 수학자 ‘무하마드 알 고와드미’의 이름에서 유래.

수학

1) 잘 정의되고 명확한 규칙들의 집합.

2) 문제 해결을 위해 실행하는 유한한 단계의 처리절차

컴퓨터학.

1) 기계가 문제 해결을 위해 실행하는 명령어들의 집합.

2) 기계가 문제 해결을 위해 실행하는 유한한 단계의 처리절차

(35)

35

5.4 알고리즘

Algorithm

알고리즘의 조건

구 분 내 역 비 고

입력 외부 자료 > 0개 내부 자료로 실행 가능 출력 최소 1개 이상의 결과 알고리즘의 목적

명확성 각 처리 단계가 명확해야 오류 예방, 기술 도구 필요

유한성 명령들은 유한한 수만큼 실행 종료 기능

효과성 모든 명령들은 수행 가능해야 쉽고 간단하고 기본적이어야

(36)

5.4 알고리즘

알고리즘의 효율

^{종 류} ^{내 역} ^{비 고(실례)}

O(1) 자료의 수에 관계없이 자료를 접근하는 유형 해싱

O(log n) 큰 문제를 작은 문제로 나누어 처리하는 유형 이진 탐색

O(n) 자료를 선형으로 처리하는 유형 선형 탐색

O(n log n) 작은 문제로 나누어 처리하고 다시 모으는 유형 쉘 정렬

O(n²) 이중 루프(loop) 안에서 자료를 처리하는 유형 버블 정렬 O(n³) 삼중 루프(loop) 안에서 자료를 처리하는 유형 3 way join

O(n^k) 이상 k가 상수로서 다항식 시간 알고리즘이 아닌 유형 NP-완전 문제

(37)

37

5.4 알고리즘

알고리즘의 평가 기준

_{종 류} _{내 역}

정확성 입력에 대하여 유한 시간 안에 올바른 결과 생산 여부

처리 시간 중요한 연산만으로 작업 시간을 측정

중요한 연산이 여러 개면 합계를 계산하거나 가중치 사용 소요 공간 사용되는 기억장치의 소요량

최적성 더 좋은 연산을 수행하는 알고리즘의 존재 여부

(38)

5.4 알고리즘

알고리즘 처리 절차

종 류 내 역 비 고

설계 특정 문제를 해결하는 알고리즘 고안 설계 도구 검증 입력에 대한 올바른 결과 산출 여부 판단

분석 알고리즘 실행에 필요한 시간과 공간 결정 처리율, 응답시간 기억장치 종류 시험 오류 확인과 제거, 성능 분석 시험 자료 작성

(39)

40

5.4 알고리즘

Euclid Algorithm 순서도

두 가지 형태: 어느 것이 효과적?

두 수 A, B 입력

A를 B로 나누고 나머지를 R에 저장

R = 0 ?

STOP y

n

A를 B로 바꾸고 B를 R로 바꾼다 START

PRINT B

두 수 A, B 입력

A를 B로 나누고 나머지를 R에 저장

STOP START

PRINT B While R not= 0

A를 B로 바꾸고 B를 R로 바꾼다 A를 B로 나누고 나머지를 R에 저장

(40)

5.4 알고리즘

호제법 알고리즘

Procedure GCD(A, B) // 최대공약수 알고리즘

// A: dividend, B: divisor begin

read A, B

R = A mod B // R: 나머지 mod_label:

if R = 0 then ; else

begin

move B to A move R to B goto mod_label end // if end

print B // 최대공약수 인쇄 end // proc end

(41)

42

5.4 알고리즘

알고리즘과 기계의 미래

1930년대 알고리즘 연구 시작 1960년대 컴퓨터 박사학위 수여 간단한 튜링 기계  복잡한 컴퓨터

생각하는 기계

인간의 지능을 갖춘 기계

인간 지능의 가장 큰 능력 : 상상력  창의력.

인공지능의 실패 원인: 방향 잘못. ex. 튜링 테스트

전자공학이나 전산학보다 인간의 두뇌를 더 잘 알아야