유한 상태 기계

오토마타 벤 다이어그램

유한 상태 기계(finite-state machine, FSM) 또는 유한 오토마톤(finite automaton, FA; 복수형: 유한 오토마타 finite automata)는 컴퓨터 프로그램과 전자 논리 회로를 설계하는 데에 쓰이는 수학적 모델이다. 간단히 '상태 기계'라고 부르기도 한다.

유한 상태 기계는 유한한 개수의 상태를 가질 수 있는 오토마타, 즉 추상 기계라고 할 수 있다. 이러한 기계는 한 번에 오로지 하나의 상태만을 가지게 되며, 현재 상태(Current State)란 임의의 주어진 시간의 상태를 칭한다. 이러한 기계는 어떠한 사건(Event)에 의해 한 상태에서 다른 상태로 변화할 수 있으며, 이를 전이(Transition)이라 한다. 특정한 유한 오토마톤은 현재 상태로부터 가능한 전이 상태와, 이러한 전이를 유발하는 조건들의 집합으로서 정의된다.

예시

수리 기계와 인식기

수리 기계(acceptors)와 인식기(recognizers)는 입력값이 기계에서 받아들여졌는지 이진값인 '예 또는 아니오'로 결과를 출력한다. 유한 오토마타의 모든 상태는 받아들여지는지 또는 받아들여지지 않는지에 대한 값을 가지고 있다. 모든 입력이 처리되었을때, 만약 현재 상태가 받아들여질 수 있는 상태라면 그 입력값은 기계에 의해 받아들여진 것이다. 반대로 현재 상태가 받아들여질 수 없는 상태라면 그 입력값은 거부된 것이다.

유한 오토마타는 언어를 정의하는 데에도 사용될 수 있다. 받아들여지는 모든 단어를 포함하고 그 문법으로 기계를 구성할 수도 있다. 이렇게 유한 오토마타로 구성이 가능한 언어를 "유한 오토마타가 받아들일 수 있는 언어"라고 한다. 정의에 의해 유한 오토마타가 받아들일 수 있는 모든 언어는 정규 표현식이다. 또한 역도 성립한다. 즉, 모든 정규 표현식은 유한 오토마타가 받아들일 수 있다.

변환기

유한 상태 변환기는 상태와 주어진 입력값에 기반하여 출력값을 생성한다. 전산언어학 분야에서 응용 프로그램을 제어하는 데 사용된다. 유한 상태 변환기는 다음과 같이 두 종류가 있다.

• 무어 모델(Moore model)

이 종류의 유한 상태 오토마타는 오직 진입 동작만을 사용한다. 즉 출력값은 오직 현재 상태에 따라서만 결정된다. 무어 기계의 장점은 행위를 단순화시킬 수 있다는 것이다. 엘리베이터 문을 예시로 들자면 유한 상태 기계는 “문을 열어라”와 “문을 닫으라” 라는 상태를 변경해 주는 두 명령어를 인식할 수 있다. “열리는 중”의 상태에 있는 진입 동작은 모터를 돌려 문을 열기 시작하는 것이고 “닫히는 중”의 상태에 있는 진입 동작은 모터를 반대로 돌려 문을 닫는 것이다. “열림”과 “닫힘”의 상태는 완전히 열리거나 닫힌 상태에서 모터를 정지시킨다.

무어 모델은 수학적으로 (S, S₀, Σ, Λ, T, G)으로 구성된 6-튜플로 정의된다.

• S는 상태의 유한 집합이다.
• S₀는 초기 상태이며 S의 원소이다.
• Σ는 입력 값의 유한 집합이다.
• Λ는 출력 값의 유한 집합이다.
• T는 현재 상태와 입력 값을 기반으로 다음 상태값을 반환하는 상태 전이 함수이다: S × Σ → S
• G는 현재 상태를 기반으로 출력 값을 반환하는 상태 전이 함수이다: S → Λ

• 밀리 모델(Mealy model)

이 종류의 유한 상태 오토마타는 오직 입력값만을 사용한다. 즉 출력 값은 입력 값과 현재 상태 모두에 의존한다. 밀리 기계는 일반적으로 상태의 수를 줄이는데 사용한다. 앞의 무어 기계와 같은 엘리베이터 문을 예시로 들자면 무어 모델과 달리 중간의 “열리는 중”과 “닫히는 중”의 상태가 없다. 또한 진입 동작이 아니라, 다음과 같이 현재 상태와 입력 값에 모두 영향을 받는 두 종류의 입력 행위가 있다. “만약 문을 열어라 라는 입력 값이 들어온다면 문을 열기 위해 모터를 작동시킨다”와 “만약 문을 닫아라 라는 입력 값이 들어온다면 문을 닫기 위해 모터를 반대 방향으로 작동시킨다”라는 두 입력 행위가 존재한다.

밀리 모델은 수학적으로 (S, S₀, Σ, Λ, T, G)으로 구성된 6-튜플로 정의된다.

• S는 상태의 유한 집합이다.
• S₀는 초기 상태이며 S의 원소이다.
• Σ는 입력값의 유한 집합이다.
• Λ는 출력값의 유한 집합이다.
• T는 현재 상태와 입력값을 기반으로 다음 상태값을 반환하는 상태 전이 함수이다: S × Σ → S
• G는 현재 상태와 입력값을 기반으로 출력값을 반환하는 상태 전이 함수이다: S × Σ → Λ

정의

• 시작 상태(start state)는 유한 오토마타가 입력값을 처리하기 전의 상태이다.
• 받아들여지는 상태(accept states 또는 final states)는 유한 오토마타가 모든 입력값을 처리했을 때의 상태가 받아들여질 경우 이 상태의 집합을 의미한다. 받아들여지는 상태는 한개 또는 여러개일 수 있으며 이는 동치이다. 일반적으로 받아들여지는 상태는 이중 원으로 표현한다.

결정적 유한 오토마타

 이 부분의 본문은 결정적 유한 오토마타입니다.

• 결정적 유한 오토마타 (Deterministic Finite Automata, DFA)는 $(Q,\Sigma ,s_{0},\delta ,F)$으로 구성된 5-튜플이다.
  • $Q$는 상태의 공집합이 아닌 유한 집합이다.
  • $\Sigma$는 입력 문자이다. (유한하며, 비어있지 않은 기호의 집합이다).
  • $\delta$는 상태 전이 함수이다: $\delta :Q\times \Sigma \rightarrow Q$
  • $s_{0}$는 초기 상태이며, $Q$의 원소이다.
  • $F$는 최종 상태의 집합이며, $Q$의 원소이다.

비결정적 유한 오토마타

 이 부분의 본문은 비결정적 유한 오토마타입니다.

• 비결정적 유한 오토마타 (Nondeterminstic Finite Automata, NFA)는 $(Q,\Sigma ,s_{0},\delta ,F)$으로 구성된 5-튜플이다.
  • $Q$는 상태의 공집합이 아닌 유한 집합이다.
  • $\Sigma$는 입력 문자이다. (유한하며, 비어있지 않은 기호의 집합이다).
  • $S$는 유한하며, 비어있지 않은 상태의 집합이다.
  • $\delta$는 상태 전이 함수이다: $\delta :Q\times \left(\Sigma \cup \left\{\epsilon \right\}\right)\rightarrow {\mathcal {P}}(Q)$
  • $s_{0}$는 초기 상태이며, $Q$의 원소이다.
  • $F$는 최종 상태의 집합이며, $Q$의 원소이다.

비결정적 유한 오토마타는 결정적 유한 오토마타와는 다르게 입력 기호에 대해서 $\epsilon$-transition 에 의해 0개 이상의 이동이 가능하다. 만약 가능한 다음 상태의 경우가 없다면, 기계는 입력을 거부한다.

개념과 용어

상태란 전이를 시작하기 위해 대기하고 있는 시스템의 행동적 노드를 의미한다. 일반적으로 상태는 같은 유발점에 대하여 같은 반응을 보이지 않는 시스템 때문에 정의되었다. 예컨대, 자동차 오디오에서, 라디오를 듣고 있을 때(라디오 "상태"), "다음"버튼을 누를 때(다음 "유발점") 다른 방송국으로 넘어가지만, CD를 듣고 있을 때 (CD "상태")에서 "다음" 버튼은 다음 곡을 재생하는 것이 있다. 같은 유발점이 현재 상태에 대해 다른 동작을 보일 수 있다. 어떤 유한 상태 기계의 표현에서는, 동작과 상태를 다음과 같이 연관짓는 것이 가능하다.

• 진입 동작: 상태에 진입 할 때 수행되는 동작
• 퇴장 동작: 상태로부터 퇴장 할 때 수행되는 동작

전이란, 어떠한 조건이 만족되거나 이벤트가 발생하였을 때 수행되는 일련의 동작을 의미한다.

결정론

유한 오토마타는 결정적 유한 오토마타(Deterministic Finite Automata, DFA) 와 비결정적 유한 오토마타(Non-Deterministic Finite Automata, NFA) 오토마타로 나눌 수 있다.

결정적 유한 오토마타에서 모든 상태는 각각의 가능한 입력에 대해 정확히 하나의 변환된 상태를 가질 수 있다. 비 결정적 유한 오토마타에서 입력은 주어진 상태에 대해 한 가지 또는 여러 가지의 변환된 상태를 가지게 할 수 있다. 여러 알고리즘(the powerset construction 등)을 사용하여 어떠한 NFA라도 동일한 기능을 가지는 DFA로 변환할 수 있다.

비결정적 유한 오토마타의 결정적 유한 오토마타로의 변환

멱집합 구성(Powerset Construction) 혹은 부분집합 구성방식은 유한 오토마타 변환의 표준이라고 할 수 있는 방법이다. 이 방식에서, 같은 정규 언어를 인식하는 비결정적 유한 오토마타는 결정적 유한 오토마타로 변환된다. 이 이론에서 중요한 점은, 비결정적 유한 오토마타가 더 유연함에도 불구하고 그것들은 결정적 유한 오토마타가 인지하지 못하는 어떠한 언어도 인지할 수 없다는 점이다. 또, 비결정적 유한 오토마타를 결정적 유한 오토마타로 변환하는 가장 큰 이유는, 더 쉽게 구성되는 비결정적 유한 오토마타를 컴퓨터에서 효율적으로 실행할 수 있는 결정적 유한 오토마타로 바꾸기 위함이다. 하지만, 만일 비결정적 유한 오토마타가 n개의 상태를 가지고 있다면, 얻어지는 결정적 유한 오토마타는 최대 2ⁿ 개의 상태를 가지고 있으며, 이는 지수적으로 증가하므로 종종 큰 비결정적 유한 오토마타에 대해 이 변환은 비실용적이다.

멱집합 구성 알고리즘

 이 부분의 본문은 라빈-스콧 멱집합 구성입니다.

M₂=<Q, Σ, q_2,0, δ₂, A₂>가 언어 L을 인식하는 비결정적 유한 오토마타라고 하자. 이 때, 결정적 유한 오토마타 M= <Q,Σ,q₀,δ,A>는 다음의 조건을 만족하며, 언어 L을 인식할 수 있다.

• Q = 2^Q₂ , 즉 Q₂의 멱집합 (Power Set)
• q₀ = { q_2,0 }
• δ(q,a) = ∪_p∈qδ(p,a)
• A = {q ∈ Q | q ∩ A₂≠0 }

비결정적 유한 오토마타 M₂=<Q, Σ, q_2,0, δ₂, A₂>와 같은 언어를 인식하는 결정적 유한 오토마타 M= <Q,Σ,q₀,δ,A>을 얻기 위해, 다음의 과정을 따라 변환을 하면 된다.

• (1) 최초에 Q = ∅이다.
• (2) 먼저, { q_2,0 } 을 Q에 넣는다. { q_2,0 }는 결정적 유한 오토마타 M의 최초 상태이다.
• (3) 그리고 Q의 각 state q에 대하여,
  • Q의 상태가 각 Σ에 대해 없을 경우, δ(q,a) = ∪_p∈qδ(p,a)를 추가한다. 단, 여기서 우변의 δ는 M₂의 것이다.
  • 이 새로운 상태에서, δ(q,a) = ∪_p∈qδ(p,a)를 δ에 추가한다. 우변의 δ는 M₂의 것이다.
  • Q에 더 이상 상태가 추가될 수 없을 때, 과정을 끝낸다.

이 방식은, 다른 오토마타에서 비슷한 알고리즘과 구분하기 위하여 특별히 라빈-스콧 멱집합 구성이라고도 불리는데, 이는 1959년 M. O. 라빈과 데이나 스콧이 이 방식을 고안했기 때문이다.

예시

밑의 NFA는 네 가지 상태를 가진다. 1은 최초 상태이고, 3과 4는 받아들여지는 상태이다. 각각의 알파벳은 0과 1의 두 기호로 구성되어있으며, 각각은 ε-move를 가진다.

이 비결정적 오토마타로부터 얻어지는 결정적 오토마타의 최초 상태는 모든 비결정적 오토마타가 1로부터 ε-move를 통해 도달 가능한 상태이다. 즉, 이 경우에는 {1,2,3}이 된다. {1,2,3}으로부터 입력 기호 0에 의한 전이는 상태 1에서 상태 2로 가는 화살표를 따라가거나, 상태 3으로부터 상태 4로의 방향을 따라야 한다. 덧붙여서, 상태 2와 상태 4는 밖으로 나가는 ε-move를 가지지 않는다. 그러므로, T({1,2,3},0) = {2,4} 가 되고, 같은 방식으로 비결정적 유한 오토마타로부터 생성된 결정적 유한 오토마타는 밑의 그림과 같다.

이 예시에서, 결정적 유한 오토마타는 시작 상태로부터 5개의 도달 가능한 상태를 가진다. 나머지 11개의 부분 집합은 도달 불가능하다.

비결정적 유한 오토마타와 결정적 유한 오토마타의 항등성

비결정적 유한 오토마타와 결정적 유한 오토마타가 서로 변환 가능한 이유는, 서로 항등(equivalence) 관계에 있기 때문이다.

M₁=<Q, Σ, q_1,0, δ₁, A₁>가 언어 L을 인식하는 비결정적 유한 오토마타라고 하자. 또, 변환에 의해 얻어진 결정적 유한 오토마타를 M₂=<Q, Σ, q_2,0, δ₂, A₂> 라고 하자. 이를 증명하기 위하여, 모든 문자열 w에 대하여, δ₁*(q_1,0, w) = δ₂*(q_2,0, w) 임을 귀납법에 의해 보이면,

• 기초 단계 :

w = Λ일 때, δ₂*(q_2,0, Λ) = q_2,0 (δ₂*의 정의에 의하여) ={q_1,0} (결정적 유한 오토마타 M₂의 정의에 의하여) =δ₁*(q_1,0, q_2,0 ) (δ₁*의 정의에 의하여)

• 귀납 단계 :

어떤 문자열 w에 대하여 δ₁*(q_1,0, w) = δ₂*(q_2,0, w) 라고 가정하자. 이때 문자열 w 와 Σ의 기호 a에 대해, δ₁*(q_1,0, wa) = ∪_{p∈δ1*(q1,0, w)}δ_1,0(p,a) =δ₂ ( δ₁*(q_1,0, w),a) =δ₂*( q_2,0, wa)

그러므로, 어떤 문자열 w에 대해서도 δ₁*(q_1,0, w) = δ₂*(q_2,0, w)이다. ■

역사

고대와 중세(~16세기)

 오토마타 문서를 참고하십시오.

유한 오토마타는 디지털 컴퓨터에 대한 추상적 모델로서, 19세기 중반 다양한 분야의 과학자들이 협력하여 인간의 사고 과정을 컴퓨터 또는 다른 이론적 모델을 통해 표현해 내고자 하는 데서 연구의 기원을 찾을 수 있다.

유한 오토마타의 개념이 나오기 이전 시대의 경우, 유한 오토마타와 유사성 또는 관련성이 있는 오토마타(Automata), 즉 자동기계의 개념이 존재하였다. 이는 인간에 의한 복잡한 제어 없이 스스로 제 기능을 하는 기계들(self-operating machine)를 의미한다. 인류는 오래전부터 이러한 자동기계에 흥미를 느끼고 만들고 개발시켜 왔다. 오토마타, 즉 자동기계는 헬레니즘 시대와 고대 그리스 시대부터 이미 존재했다고 알려져 있다. 헬레니즘 시대(Hellenistic World)의 오토마타는 장난감, 종교적 신상(idol), 또는 기본적 과학 원리들을 증명하는 도구 등으로 만들어졌다.

고대 그리스 수학자인 알렉산드리아의 헤론은 수력으로 작동하는 오르간, 소화기, 사이펀과 같은 기계들에 대한 기록을 남겼으며, 이것들은 최초의 오토마타라고 여겨진다. 뿐만 아니라 아르키메데스는 스스로 작동하는 천체 모형을 만들었다고 전해진다.

오토마타의 형성과 발전은 물시계와 연관이 깊은데, 기원전 250년경에 고대 그리스 과학자 크테시비우스는 기계장치 자동인형이 부착된 최초의 자동물시계 '클렙시드라'를 만들었다고 전해진다.‘클렙시드라’는 크테시비우스 자신이 고안한 톱니바퀴와 펌프장치 등을 활용하여 이전에 존재하던 물시계의 단점을 보완한 획기적인 발명품으로, 기계장치에 부착된 인형이 시간을 가리키는 오토마타 자동물시계였다. 그리스 뿐만 아니라 고대 중국에서도 자동기계에 관한 기록 또는 얘기도 전해지고 있다. 주나라의 무왕(1023-957 BC) 시절에 얀시(Yan Shi)라는 기술자가 왕에게 사람 크기와 사람 모양을 가진, 기술적 일을 하는 기계를 보였다는 기록이 있고, 사마천의 <사기>에 따르면 "장인들로 하여금 자동으로 발사되는 기계장치가 된 쇠뇌를 만들게 하여, 접근하는 자가 있으면 즉시 발사되도록 했다." 라는 자동기계에 대한 기록이 남아 있다. 중세 시대에는 이슬람에서의 과학이 크게 발전해 많은 오토마타가 개발되었다. 8세기 중엽에는 바그다드에서 풍력으로 작동하는 동상이 만들어졌다. 이 동상은 "바그다드의 네 문마다 돔위에 얹혀져 바람이 불면 회전하였다"고 한다. 12세기의 이슬람 과학자 알 자자리는 음료 시중을 드는 자동인형, 자동문과 같은 자동 기계, 그리고 자동 기계로 된 악대 등을 개발하여 사용했다고 전해진다. 유럽에서는 오토마타의 발전에 중세 시대에는 이슬람에 비해 적었지만, 르네상스 시대 이후에 다시 눈에 띄게 발전하였다. 대표적인 예로 레오나르도 다 빈치(Leonardo da Vinci, 1452-1519)를 들 수 있는데, 비록 그 당시에 만들어지진 않았지만 가슴이 열리면 꽃이 나오는 사자 자동인형과 로봇 전투병의 스케치가 남아 있다. 동양에서도 이렇게 자동기계에 관한 관심을 기울인 사람들이 많았다. 조선에는 장영실(1390?~1450?)이 그 집합에 속한다. 그가 제작한 자격루, 옥루, 일성정시의 등의 자동시계를 비롯한 다양한 장치들은 모두 자동기계의 범주 내에 속한다. 중국에서는 11세기 북송시대 천문학자 소송이 12m 높이의 자동물시계 시계탑인 '수운의상대(水運儀象臺)'을 만들었다.

기계론적 사고관을 주장한 르네 데카르트

근대(16세기~19세기)

오토마타 또는 자동 기계는 16, 17세기 들어서부터 본격적으로 발전하기 시작했다. 17세기 유럽에 유행한 르네 데카르트(René Descartes, 1596~1650)의 기계론은 오토마타를 새로운 관점으로 보게 했으며, 오토마타에 대한 이론적, 철학적 토대를 마련하였다. 데카르트는 살아 있는 생명체가 사실상 복잡한 기계와 다를바 없다고 주장하였다.(그는 육체는 물질적인 것이고 영혼은 비물질적인 것이라고 하여 영혼의 존재를 부정하진 않았지만, 인간만이 영혼을 가지고 있다고 생각하였다고 한다.) 그에 따라 자연과 사물을 비교하는 방식의 중심엔 외형 대신 작동 방식이 들어서게 되었고, 그에 따라 자동기계는 더 활발히, 대중적으로 연구되고 개발되었다. 오토마타는 18세기 유럽에서 번창했는데, 대표적인 사람으론 기계오리를 만든 프랑스 발명가 자크 드 보캉송(Jacques de Vaucanson), 자동체스인형을 고안한 헝가리 발명가 볼프강 폰 켐펠렌(Wolfgang von Kempelen), 그리고 여러 자동인형을 만든 자크-드로즈(Pierre Jaquet-Droz)등이 있다.

한편 동양에서는 17세기 에도 시대에 일본으로 오토마타가 유럽으로부터 전해지기 시작했다. 일본에서는 오토마타를 '카라구리(Karakuri)'라고 부르며, 중국 등에서 온 물시계 제작 기술들의 영향을 받아 태엽과 톱티바퀴로 움직이는 자동인형들이 만들어졌다.

현대(20세기~)

현대에 들어서 오늘날까지도 여전히 오토마타 또는 자동기계는 하나의 예술 분야로서 폴 스푸너ㆍ피터 마키ㆍ아키오 니시다ㆍ키스 뉴스테와 같은 작가들에 의해 유지, 발전되고 있다. 그러나 유한 오토마타와 관련해서 현대에서 주목할 점은, 현대에 들어선 자동기계, 그리고 자동기계를 통해 생물을 모방, 창조하려는 시도가 컴퓨터 과학이라는 분야에서도 꽃피기 시작했고, 후에 컴퓨터 과학에서의 굳건한 분야로 자리잡았다는 점이다. 처음으로 유한 오토마타, 또는 유한 상태기계를 생각하게 된 사람들엔 생물학자들, 심리학자들, 수학자들, 공학자들, 그리고 최초의 컴퓨터 과학자들이 들어 있었다. 그들은, 이전의 자동기계들을 통해 본질적으로 구현해 내지 못한 인간의 특징인 '인간의 사고 과정(human thought process)'을 이론적 또는 실체적으로 구현해 내고자 수많은 시도를 하였다.

앨런 튜링(Alan Turing)

앨런 튜링(Alan Turing, 1912~1954)은 1936년 On Computable Numbers, with an Application to the Entscheidungsproblem("결정 문제에 대한 응용을 포함한 계산 가능한 수에 관하여")이라는 논문에서 튜링 기계(Turing Machine)의 개념을 소개했다.

튜링 기계는 다음과 같은 4개의 부분으로 이루어져 있다.

• 테이프(tape)

유한 가지 종류의 알파벳 또는 아무것도 쓰여 있지 않은 셀들의 연속이다. 튜링 기계에선 테이프는 연산에 필요한 만큼 제공되며, 왼쪽 또는 오른쪽으로 얼마든지 이동될 수 있다고 가정되어 있다.

• '머리'(head)

테이프의 각 셀에 있는 기호들을 읽고 쓸 수 있으며, 테이프를 왼쪽 또는 오른쪽으로 한 칸씩 이동시킬 수 있는 튜링 기계의 부분이다.

• 유한한 '표'(table, action table, transition function)

(튜링) 기계가 수행해야 하는 작업들(대체로 5개, 때론 4개이다.)이 적힌 '책상'은 기계의 현재 상태와 현재 읽고 있는 기호가 주어졌을 때 기계가 아래의 것들을 연속적으로 하라고 명령한다.

1. 기호를 지우거나 적고,

2. '머리'를 이동시킨 후,

3. 이전과 같거나 새로운, 어쨌든 정해진 상태에 도달한다.

• 상태 기록부(state register)

유한개의 튜링 기계의 가능한 상태들 중에서 어떤 시점에서의 튜링 기계의 상태를 저장한다.

여기서 한 가지 주목할 점은, 튜링 기계의 상태, 가능한 기호, 그리고 수행 작업들 모두 "유한하고, 분명하며 구분가능하다"(finite, discrete and distinguishable)는 것이다. 물론 테이프의 양은 필요에 따라 무한히 길게 늘어질 수 있긴 하지만, 이러한 특징이 바로 튜링 기계가 띠고 있는 유한 오토마타적 성질이라 할 수 있다.

그러나 튜링 기계는 유한 오토마타에 포함되는 개념이 아니라, 역으로 유한 오토마타가 튜링 기계에 포함되는 개념이다. 유한 오토마타는 사실상 '머리'가 오른쪽으로만 움직일 뿐만 아니라, 읽을 수만 있고 쓸 수 없는 튜링 기계의 특별한 집합이다.

튜링 기계가 컴퓨터 과학 분야에서 중요한 이유는, 튜링 기계가 역사상 가장 정교하고 강력한 오토마타이기 때문이다. 실제로, 어떤 계산 또는 연산이 튜링 기계를 통해 모델링될 수 없다면 컴퓨터에 의한 어떠한 효과적 해결책도 없다는 것이 증명되었다고 하며, 이는 곧 튜링 기계가 현재 우리가 갖고 있는 디지털 컴퓨터의 역량과 대등한 수학적 모델이라고 할 수 있음을 의미한다.

존 폰 노이만(John Von Neumann)

존 폰 노이만(1903-1957)

존 폰 노이만(John von Neumann, 1903년 12월 28일 ~ 1957년 2월 8일)은 헝가리 미국 독일 유태계의 수학자로서 양자물리학(quantum physics), 함수해석학(functional analysis), 집합이론(set theory), 컴퓨터 과학, 경제학과 많은 수학분야에 중요한 공헌을 하였다.

그는 생명체를 일종의 기계로 보았기 때문에 무기물인 기계도 자가 복제가 가능할 것이라고 생각했다. 노이만은 적어도 자신과 같은 정도의 복잡한 것을 만들어 내는 것이 가능하다는 것을 다음과 같은 방법으로 1948년에 논리적으로 증명하는 데 성공하였다.

1. 임의의 어떤 기계라도 만들 수 있는 만능제조 기계(Universal Machine) 을 설계한다.

2. UM 에 어떤 기계 M 을 만드는 프로그램을 담은 테이프 T(M) 을 넣는다면 UM 은 테이프 내용대로 기계 M 을 만들어 낼 것이다.
3. 만약 테이프 내용이 UM 을 만들라는 것일 경우 만능기계인 UM 은 테이프 내용 그대로 자신과 똑같은 또 하나의 UM 을 만들어 낼 것이다.

이 증명에서의 한가지 문제는 자가 복제 기계의 존재성은 만능 제조 기계의 존재성을 전제로 한다는 것이다. 노이만은 이 문제를 해결하기 위해 독일의 컴퓨터 과학자 콘라드 주세 (Konrad Zuse, 1910 ~ 95)의 아이디어를 빌렸다. 노이만은 물리적 계의 이산모델로서 오토마타가 병렬로 연결된 계산공간을 고안해 낸다. 노이만은 결국 약 20만 개에 달하는 29개의 상태를 갖는 오토마타를 2 차원의 평면에 배열하여 자가 복제 기계를 만드는데 성공했다. 사후에 그의 공동연구자 아터 버크스가 논문으로 제작하여 출판하였고 (Theory of Self Reproducing Automata) 미국 IBM의 코드(E. F. Codd)에 의해 단순화되었고 실제로 구현되었다.

크리스토퍼 랭턴(Christopher G. Langton)

인공 생명 개념의 창시자 크리스토퍼 랭턴

크리스토퍼 랭턴(1948~)은 유한 오토마타와 연관이 깊은 개념인 인공 생명(Artificial Life, Alife, AL)의 개념의 창시자라고 할 수 있다. 랭턴은 1987년 로스앨러모스 국립 연구소에서,"생명계의 합성과 시뮬레이션에 대한 워크샵"(Workshop on the Synthesis and Simulation of Living Systems, Artificial Life I)을 최초로 열었으며 이때 인공 생명이라는 단어를 만들었다.

랭턴은 인공 생명분야에 시뮬레이션과 계산적 모델, 그리고 철학적 문제까지 많은 부분 공헌하였다. 그는 정보, 계산과 번식에 관한 문제를 본질적으로 연관짓고, 기본적인 법칙을 정의하였다. 물리학의 법칙중 특히 상전이에 영감을 받아 셀룰러 오토마타의 몇가지 기본 개념과, 정량적 분석을 발전시켰다. 또, 특히 생물학에서, 정렬이 비정렬로부터 분리해 내는 임계점이 복잡계를 형성하는 데에 중요한 역할을 함을 제시하였다. 이런 그의 아이디어는, 비록 다른 근사법을 썼지만, Per Bak이나 James Crutchfield등에 의해서도 동시에 논의되었다.

워렌 맥컬럭(Warren McCulloch)과 월터 피츠(Walter Pitts)

워런 맥컬록(Warren McCulloch)와 월터 피츠(Walter Pitts)는 1943년 A Logical Calculus Immanent in Nervous Activity("신경 활동에 내제된 논리적 고등 계산법")라는 논문을 통해 신경 네트워크 이론, 오토마타 이론, 그리고 컴퓨터 조작 및 인공 두뇌학 이론에 큰 기여를 했다. 그들의 논문을 미주리 대학에서 철학, 심리학, 신경 과학 등을 연구하는 철학자 Gualtiero Piccinini는 다음과 같이 평가하고 있다.

신경 과학과 컴퓨터 조작에서의 그 중요성에도 불구하고, McCulloch와 Pitt의 저명한 1943년의 논문은 거의 역사적, 철학적 주목을 받지 못 했다. 1943년엔 이미 신경 네트워크에 대한 수학적 연구를 하는 활발한 생물물리학자들의 집단이 존재했었다. McCulloch와 Pitt의 논문에서 참신했던 점은 신경 활동, 즉 정신적 활동을 이해하기 위한 그들의 논리와 계산이었다. McCulloch와 Pitt의 공헌은

1. 세련화 및 일반화를 통해 유한 오토마타(컴퓨터 연산 이론에서 중요한 형식주의)의 개념을 도출했던 형식주의
2. 논리 설계(현대 컴퓨터 디자인의 기초적인 부분)의 개념의 영감을 주었던 기술
3. 정신-육체 문제를 다루기 위한 최초의 컴퓨터 연산의 사용
4. 정신과 뇌에 관한 최초의 현대적 컴퓨터 연산 이론

을 포함한다.

G. H. Mealy와 E. F. Moore

George H. Mealy는 1955년 그의 논문 A Method for Synthesizing Sequential Circuits("순차 회로 합성 방법")에서 밀리 기계(Mealy machine)라는 개념을 처음으로 발표했다. 여기서 sequential circuit(순차 회로)이란 디지털 회로 이론(digital circuit theory)의 sequential logic(순차 논리), 즉 논리 회로의 결과값이 현재 입력값 뿐만 아니라 과거의 입력값의 역사에도 의존하는 논리 회로를 말한다. 이러한 논리 회로는 자연스럽게 컴퓨터 메모리와 관련이 많으며, (Mealy와 Moore 등의 학자들에 의해) 유한 오토마타와도 관련이 있다.

Edward F. Moore는 1956년 그의 논문 Gedanken-experiments on Sequential Machines에서 sequential machine(순차 기계 또는 순서 기계)은 유한 개의 상태, 유한 개의 가능한 입력 및 출력 기호들을 가지는 전형적인 유한 상태 기계(finite state machine)라고 했다. 순서 기계의 현재 상태는 오직 이전의 입력값과 이전 상태에 의해서만 결정되며, (무어의 논문에서는) 현재의 출력값은 오로지 현재 상태에만 의존한다는 점에서 순서 기계의 행동은 매우 엄격하게 결정적(strictly deterministic)이라고 할 수 있다고 했다. 무어는 그의 논문에서 두 가지 실험을 보이면서 이러한 순서 기계에 관한 생각을 열거하여, 무어 기계(Moore machine)의 개념을 소개했다. 그 두 가지 실험을 간단히 소개하자면 아래와 같다.

*(1)간단한 실험('simple experiment')

실험자와 테스트하고자 하는 순서 기계 하나가 존재한다. 실험자는 연속적으로 순서 기계에게 입력 기호들의 순열을 주고, 입력 기호들의 순열과 순서 기계로부터 나온 출력 기호들의 순열을 통합하여 순서 기계에 관한 결론을 내릴 것이다.

• (2)복합 실험('multiple experiment')

실험자와 테스트하고자 하는 여러 복제된 순서 기계들이 존재한다. 각각의 순서 기계들은 동일한 초기 상태를 가진다. 간단한 실험에서와 마찬가지로 실험자는 순서 기계들에게 입력 기호들의 순열을 줄 것이며, 이 순열과 출력 기호들의 순열을 통합해 결론을 내린다.

이 두 실험에서 실험자는 사람이어도 되고, 또 다른 기계라 해도 상관없다. 무어가 그의 논문에서 이와 같은 두 개의 실험을 통해 생각하고자 했던 문제는 이 실험을 행하기 위한 명시적인 설명서(explicit instruction)을 주는 방법에 관한 것이었다. 이러한 이론적 실험들에 대한 연구가 어떻게 실제 상황에 도움이 될 수 있는가를 설명하기 위해 무어는 네 가지 예를 들었다.

첫 번째 예는 전쟁 중에 상대편의 것으로 판정된 미지의 기기의 역할과 작동 조건들 등에 대해 알아내는 상황이다. 상대편의 기기를 열어서 구조를 볼 수 없거나, 또는 열어서 보아도 너무 복잡하여 많은 것을 알아낼 수 없다고 가정할 때("블랙 박스 제한", "black box restriction"), 실험자는 오로지 입력 기호 순열과 출력 기호 순열을 바탕으로 이 기계의 작동 조건들에 관한 정보를 얻을 수 있을 것이다.

두 번째 예는 유한 오토마타를 만드는 엔지니어의 경우로, 엔지니어가 만든 유한 오토마타를 입력과 그 결과값으로 판별할 수 있다고 가정했을 때, 만약 또다른 더 적은 상태를 가지는 기기와 비교했을 때 어떠한 차이도 발견할 수 없다면 엔지니어는 더 간단한 상태를 가지는 그 기기로 자신의 유한 오토마타를 변형시킬 수 있을 것이다.

하나의 입력값 및 출력값을 가지는 밀리 기계의 상태 다이어그램

세 번째 예는 정신 의학자와 그의 환자의 예로, 정신 의학자는 뇌에 문제가 있는 환자에게 무언가를 물어보고(입력 기호 순열) 환자의 답을 통해(출력 기호 순열) 이 환자의 어떤 부분이 잘못되었는지 어느 정도 알 수 있을 것이다. 세 번째 상황에도 블랙 박스 제한 조건이 있기에 무어가 제안한 실험과 세 번째 상황이 근사적으로 비슷하다고 할 수 있다.

마지막으로 무어가 든 예시적 상황은 과학자의 실험이다. 과학자는 때로 자신의 실험에서 원하던 결과를 얻지 못할 때가 많다. 이러한 상황에서, 과학자는 직접적으로 자연의 구조나 실험 문제의 해결 방법을 얻을 수 없다는 블랙 박스 제한 조건에 부딪치기 때문에, 우회적으로 돌려 새로운 실험 조건을 만들어(입력 기호 순열) 그 결과를 살펴보며(출력 기호 순열) 문제를 해결해 나갈 것이다.

밀리 기계와 무어 기계는 둘 다 유한 오토마타에 속하는 기계인데, 차이점은 밀리 기계는 결과값이 현재 상태(current state)와 현재 입력값(current inputs)에 의해 결정되지만 무어 기계는 오로지 현재 상태에 의해서만 결정된다는 점이다.

예를 들어 자동차가 빨간 신호등을 인식했을 때 바로 멈추면 무어 기계인 것이고, 현재 진행 중이던 일을 마친 이후에 멈추면 밀리 기계인 것이다.

노엄 촘스키(Noam Chomsky)

에이브럼 노엄 촘스키는 미국의 언어학자, 철학자, 정치운동가, 아나키스트, 저술가이자 진보적 교수이다. 현재 매사추세츠 공과대학교의 언어학과 교수이다.

20세기 초, 소쉬르(Fernand de Saussure)가 독립된 과학으로서의 언어 연구를 주창하면서 태동된 언어학은 제일 먼저 구조주의를 과학적인 방법론으로 발전시켜 나갔다. 오래전부터 소리, 의미, 문자를 갖춘 언어를 사용했으며, 문자 연구를 중심으로 역사-비교 언어학에 치중했던 유럽에서는 프라하 학파(School of Prague)가 언어의 본질적 기능에서 소리의 중요성을 인식하고, 청각적 실체를 가진 소리의 분석을 위한 구조주의 방법론을 개발하기 시작했다. 이러한 구조 언어학의 분석 방법 중 대표적인 것이 해리스(Zelig Harris)의 구조주의 방법론인데, 이 이론은 첫 단계로 대상 언어의 자료를 수집하고, 둘째 단계로 수집된 언어 자료 내에서 분석과 교체를 통해 음소, 이음, 형태소(morpheme), 이형태(allomorph)를 추출한 후 이들이 어떠한 방식으로 구조를 이루는가에 대해 연구했다.

촘스키는 이러한 귀납적인 구조주의 방법론에 문제점을 제기하고 나섰다. 그의 언어 분석은 인간의 정신 세계를 중심으로 하는 이성주의에 바탕을 두고 있으며, 인간에게는 언어를 만들어내고 익힐 수 있는 언어 능력이 있으므로 그 능력을 언어 분석에 적극 이용해야 하며, 언어학 연구의 초점도 이러한 언어 능력을 규명하는 데 맞춰져야 한다고 주장했다. 이를 계기로 문법의 재구성이라는 목표를 수행하기에 턱없이 불완전한 언어 자료의 결함을 인간의 언어 능력으로 보완함으로써, 그때까지의 언어학 연구에서 구조주의에 의해 배제됐던 연역적 추리가 지위를 되찾게 됐다. 또한 언어학이 추구하는 바가 귀납적인 문법의 기술에서 연역적인 문법의 설명으로 전환하게 됐다. 노엄 촘스키는 1956년에 촘스키 위계(Chomsky hierachy)이라는 것을 처음 서술하였다. 형식언어(Formal Language)를 생성하는 형식문법(Formal Grammar) 들을 분류해 놓은 계층구조이다.

• Type-0 문법(제약 없는 문법, UG, unrestricted grammars): 이 문법은 모든 형식문법을 포함한다. 튜링기계(Turing Machine) 로 인식가능한 모든 언어를 정확히 생성한다. 그 인식가능한 언어란 튜링기계가 정지(halt)하는 모든 문자열들을 의미한다. 이 언어들은 또한 회귀열거가능 언어 (recursively enumerable languages) 로 알려져있다. 이것은 튜링기계를 항상 정시시켜서(halt) 결정가능한 재귀 언어(decidable recursive language)와는 다르다는 것을 주목해야 한다.
• Type-1 문법(문맥 의존 문법, CSG, context-sensitive grammars): 이 문법은 문맥 의존 언어를 생성한다. 이 문법은 αAβ → αγβ 형태의 규칙을 가진다. 여기서 문자열 α와 β는 $\epsilon$ 일 수 있지만는 $\epsilon$ 이 아니어야 한다. 만일 S 가 어떤 규칙의 우측에 나타나지 않으면 규칙 S → ε 가 허용된다. 이 문법으로 묘사되는 언어는 비결정적 튜링 기계(non-deterministic Turing machine, 테이프가 입력의 길이를 상수으로 제한된 튜링 기계)으로 인식가능한 모든 언어들이다.
• Type-2 문법(자유 문맥 문법, CFG, context-free grammars): 이 문법은 문맥 자유 언어를 생성한다. 이것은 A → γ의 형태를 가지는 규칙으로 정의된다. 이 언어들은 비결정적 푸시다운 오토마타(non-deterministic pushdown automaton)로 인식가능한 모든 언어들이다. 문맥 자유 언어는 대부분의 프로그래밍 언어 문법의 이론적 기초이다.
• Type-3 문법(정규 문법, RG, regular grammars): 이 문법은 정규 언어(regular languages)를 생성한다. 이 언어의 문법은 다음의 둘 중 하나로 정의된다. (1)$A\rightarrow tB$ 또는 $A\rightarrow t$, 여기서 $t\in {V_{T}}^{*}$이고, $A,B\in V_{N}$이다. (2) $A\rightarrow Bt$ 또는 $A\rightarrow t$, 여기서 $t\in {V_{T}}^{*}$이고, $A,B\in V_{N}$이다.

이 중 Type-3 문법(정규 문법, RG, regular grammars)이 생성한 정규 언어(regular languages)는 유한 오토마타로 결정가능한 모든 언어들이다. 모든 유한 오토마타는 모든 정규 언어를 표현할 수 있으며 역으로 모든 정규 언어는 모든 유한 오토마타로 표현될 수 있다. 즉, 유한 오토마타의 집합과 정규 언어의 집합은 일치한다. 덧붙여서 정규 언어는 정규 표현식으로 얻어질 수 있다. 정규 언어는 검색 패턴 등과 같이 프로그래밍 언어의 어휘구조(SQL등)를 정의하는 데 흔히 사용된다.}}

유한 오토마타와 인공 생명

이 문단을 인공 생명 문서로 합치자는 의견이 제시되었습니다. 토론에서 의견을 나누어 주십시오.

기계론적 사고관과 이를 바탕으로 번성한 자동 기계들을 통해 사람들은 생명이란 무엇인가에 대해 의문을 가지게 되었다.그리고 이러한 생각을 바탕으로, 유한 오토마타와 관련이 깊은 인공 생명(Artificial Life, Alife, AL)과 인공 지능(Artificial Intelligence, AI) 등의 개념들이 탄생하였다.

기계론적 사고관, 또는 기계론적 자연관에선 자연에 존재하는 모든 물체들은 수학적, 역학적 법칙을 따라 외부의 원인에 의해서만 움직인다고 말한다. 이 자연관에 따르면 생명체와 비생명체, 유기체와 무기체의 구분은 무의미할 뿐이다. 이에 더해 오토마타, 즉 자동 기계들은 생명체는 아니지만 생명체와 매우 비슷한 행동과 모습들을 보여주었다. 결국 이 둘은 사람들로 하여금 대중적으로 생명체라 여겨지지 않았던 것들도 생명체와 다를 바가 없다는 생각을 심어주었고, 이를 과학적으로 표현한 것이 바로 인공 생명과 인공 지능 등의 컴퓨터 과학 개념이라고 할 수 있다.

이러한 철학적 관점 뿐만 아니라, 역사적, 기술적으로도 유한 오토마타와 인공 생명은 연관이 깊다. 미시간 대학의 전기 공학 및 컴퓨터 과학 교수 Arthur W. Burks의 말에 따르면, 인공 생명이란 "셀룰러 오토마타의 논리와 다른 전산화 가능한 진화학적 구조(computerizable evolutionary structures)로부터 발생한 창의적인 인간-기계 연구"라고 한다. 여기서 셀룰러 오토마타(Cellular Automata, CA)란 유한 오토마타의 한 종류로, 폰 노이만의 1948년 논문인 Theory of Self-reproducing Automata("자가 복제 오토마타 이론")에서 스스로를 복제할 수 있는 로봇에 관하여 구상할 때 처음 나온 개념이다.(1948년에 내용을 완성했으나 출판된 것은 1966년이라고 한다.)

인공 생명

 이 부분의 본문은 인공 생명입니다.

인공생명은 크리스토퍼 랭턴(Christopher G. Langton)(1948~)이 1987년에 처음 제창한 개념으로, 인공생명에서의 철학의 핵심은 "우리가 아는 생명(life as we known it)" 대신 "생명이라 할 수 있는 생명(life as it could be)"이라고 할 수 있다. 한 가지 짚고 넘어갈 점은 비록 크리스토퍼 랭턴이 처음으로 '인공생명'이란 단어를 만들긴 했지만, 오늘날의 인공생명의 기준으로 보았을 때 인공생명이라고 간주되는 것은 이전에도 이미 있었으며, 심지어 바로 랭턴이 태어난 해인 1948년 이론적인 인공생명의 디자인이 이미 구현되었다는 점이다. 그것은 1948년 폰 노이만의 논문 Theory of Self-reproducing Automata에서 제안된 셀룰러 오토마타이다. 뿐만 아니라 비슷한 시기에 Norbert Wiener가 정보 이론과 자가 통제 과정에 관한 분석(analysis of self-regulatory processes)(다른 말로 항상성-homeostasis-라고 함)을 생물 시스템 연구에 적용하여 인공 생명 연구의 출발을 알렸다.

인공 생명에는 크게 3가지 종류가 있다.

• Soft Artificial Life('부드러운' 인공 생명)

인공 생명을 만드는 데에는 크게 두 가지 기술적 이론이 쓰이는데, 하나는 셀룰라 오토마타(Cellular Automata, CA)이고 다른 하나는 신경 네트워크(Neural Network)이다. 셀룰라 오토마타는 확장성(scalability)과 병렬화(parallelization)의 특성 때문에 널리 쓰이는 것으로, 인공 생명과 매우 밀접한 역사를 지니고 있다. 한편 신경 네트워크는 본래는 뇌와 신경의 구조를 모델적으로 나타내기 위해서 연구되고 있는 분야로, 인공 생명 구현에선 배워가면서 진화해 나가는 생명체의 집단의 역동(population dynamics)을 시뮬레이션 하는데 쓰이는 중요한 기술이다.

'부드러운' 인공생명은 기본적으로 소프트웨어 프로그램 상으로 존재하는 인공 생명을 말한다. 이렇게 만들어진 인공 생명들은 아래의 4가지 종류로 분류될 수 있다.

1. Program-based: 프로그램 상의 복잡한 DNA 언어로 구현되며, 자주 사용되는 언어론 Turing Complete와 'Assembly Derivative'가 있다. 셀룰러 오토마타가 자주 사용되지만 필수 사항은 아니라고 한다.
2. Module-based: 만들고자 하는 개체는 여러 가지 부분, 즉 모듈(module)로 이루어져 있다. 각각의 모듈이 움직이는 방식은 프로그램을 통해 주어지거나 각각의 모듈의 창발적 상호작용(emergent interaction)에 의해서이다.
3. Parameter-based: 각각의 개체는 유한 개의 변수들을 갖고 있으며, 각각의 변수들은 개체의 하나 이상의 부분들의 상태를 다루거나 조작한다. 개체들이 가질 수 있는 행위들은 이미 프로그램을 통해 유한 개로 정해져 있다.
4. Neural net-based: 신경 네트워크 또는 'Close Derivative'에 의해 배우고 자라는 개체들의 시뮬레이션이다.

랭턴의 개미의 첫 200번째 단계까지의 시뮬레이션이다.

'부드러운' 인공생명의 대표적인 예로는 크리스토퍼 랭턴의 개미(Langton's Ant)와 랭턴의 루프(Langton's Loop) 등이 있다. 크리스토퍼 랭턴의 개미 시뮬레이션은 "(1)개미가 하얀색 사각형에 있으면 오른쪽으로 90도 돌고 사각형의 색깔을 바꾼 뒤 한 칸 전진한다 (2)개미가 검은색 사각형에 있으면 왼쪽으로 90도 돌고 사각형의 색깔을 바꾼 뒤 한 칸 전진한다"의 매우 간단한 두 가지 규칙으로 구성되어 있다.

• Hard Artificial Life('딱딱한' 인공 생명)

프로그램을 따라 작동하되 실제 세계에서 작동하도록 외형을 가진 인공 생명을 일컫는 말이다. 로봇과 자동기계(automaton)이 여기에 속한다. 이 분야에선 실제 세계에서 자체적으로 적응하는 지능적 행동들을 구현하는 것이 목적이다. 이러한 행동들을 구현시키기 위해서 사용하는 한 가지의 기술로는 외부 환경이 행동들을 만들도록 하는 것이다. 이러한 '생물적으로 자극 받는'(biologically-inspired)로봇들의 행동은 외부 환경을 잘 인식할 수 있는 기기만 갖추고 있다면 복잡하고 예측 불가능한 외부 환경 속에서 살아갈 수 있다고 한다. 이러한 방식으로 구현된 로봇을 "행위에 기반을 둔"(behavior-based) 로봇이라고 하며, 이러한 로봇들은 곤충을 모방한 로봇 형태로부터 시작해 성공을 거두며 현재 휴머노이드 로봇까지 확대되었다고 한다.

• Wet Artificial Life('젖은' 인공 생명)

Hard Artificial Life와 비슷하지만 외형이 생명체의 외피와 같은 유기물질 등으로 되어 있는 경우의 인공생명을 말한다. 이러한 분야가 유전자 조작 등 유기적 생명체를 만들어 내려고 노력하는 생물 분야와 다른 점은 가장 기본적이고 사소한 부분에서 인공 생명을 만들어낸다(creating artificial life from scratch)는 점에 있다. 인공 생명과 연관된 분야 또는 개념으로는 아래와 같은 것들이 있다.

1. 인공 지능(Artificial Intelligence, AI)
2. 인공 화학(Artificial Chemistry): 화학 반응들을 추상화시키기 위한 인공 생명 집단 내에서의 방법으로서 시작한 분야다.
3. 진화 알고리즘(Evolutionary Algorithms) :최적화 문제(optimization problem)에 적용된 약한 인공 생명 원리의 적용이라고 할 수 있다. 차이점으론 최적화 문제에선 진화 알고리즘은 개체의 적합함(fitness of an agent)을 문제를 푸는 능력으로 정의하는 반면 인공 생명에선 말 그대로 가장 잘 생존하는 능력으로 정의한다는 점이다.
4. 진화 예술(Evolutionary Art): 인공 생명에서 사용하는 기술을 통해 새로운 예술을 만들고자 하는 분야이다.
5. 진화 음악(Evolutionary Music): 인공 생명에서 사용하는 기술을 음악에 적용한 분야이다.
6. 자연발생론(Abiogenesis): 때때로 자연발생론에서 인공 생명에서의 방법론을 사용한다고 한다.

인공 생명과 관련된 분야들

인공 지능

인공지능(人工知能)은 철학적으로 인간이나 지성을 갖춘 존재, 혹은 시스템에 의해 만들어진 지능, 즉 인공적인 지능을 뜻한다. 일반적으로 범용 컴퓨터에 적용한다고 가정한다. 이 용어는 또한 그와 같은 지능을 만들 수 있는 방법론이나 실현 가능성 등을 연구하는 과학 분야를 지칭하기도 한다.

인공지능이란 분야를 처음 인식하기 시작한 것은 1943년 McCulloch 와 Pitts에 의해서 시작되었으며 그 동기는 뇌에 있어서 뉴런의 기능과 작용에 대한 연구와 명제 논리 그리고 튜링테스트 연구였다. 뉴런으로 연결된 네트워크 학습의 개념이 필요함을 주장하였으면 인간의 사고 과정을 최초로 연결망을 통해 모델화했다는 점에서 인공지능 역사상 의의가 매우 크다고 볼 수 있다.

1956년 여름 다트마우스(Dartmouth) 대학의 캠퍼스에 '생각하는 기계', 즉 지적인 행동을 하는 컴퓨터에 관해 토론하기 위해서 많은 사람들이 모였으며(수학자,심리학자,전기기술자,대학의 연구자 기업가 등등) 이들은 디지털 계산기를 '생각하는 기계'로 만들 수 있다는 신념을 가지고 있었고 이 회의가 인공지능(artificial intelligence: AI)이란 단어를 탄생시킨 계기가 되었다. 이 회의는 공식적으로 '다트마우스 하기 인공지능 연구계획'이라 불리며 그 뒤의 10년간을 지배한 여러 연구성과를 냈다. 이것이 제1차 인공지능 연구의 시작이었다.

인공지능에 대한 연구는 강한 인공지능과 약한 인공지능으로 나뉘는데, 강한 인공지능은 어떤 문제를 실제로 사고하고 해결할 수 있는 컴퓨터 기반의 인공적인 지능을 만들어 내는 것에 관한 연구다. 즉, 인공지능의 강한 형태는, 지각력이 있고, 스스로를 인식하는 것이라고 말할 수 있다.

반면 약한 인공지능은 어떤 문제를 실제로 사고하거나 해결할 수는 없는 컴퓨터 기반의 인공적인 지능을 만들어 내는 것에 관한 연구다. 그와 같은 시스템은 진짜 지능이나 지성을 갖추고 있지는 못하지만, 어떤 면에서 보면 지능적인 행동을 보일 것이다.

여기서 강한 인공지능이 존재할 수 있는지에 관한 철학적인 논쟁이 발생하였다. 강한 인공지능이 존재한다고 주장하는 사람들은 다음과 같은 4가지 논리를 든다.

1. 인간의 마음은 유한 오토마타(Finite Automata)이고, 따라서 처치-튜링 명제는 뇌에 적용 가능하다.
2. 인간의 마음은 소프트웨어이다(유한 상태 기계의 일종이다).
3. 뇌는 순수한 하드웨어이다(말하자면 고전적인 컴퓨터처럼 동작한다).
4. 인간의 마음은 오로지 뇌를 통해서만 존재한다.

그러나 로저 펜로즈를 포함한 몇몇 사람들은 처치-튜링 명제의 적용이 가능하지 않다고 논박한다. 어떤 이들은 인간의 마음은 물리적인 속성을 뛰어넘는 무엇이 있다고 이야기한다.

인공 화학

인공 화학은 3-튜플 (S,R,A)로 일반적으로 정의된다. 어떤 경우에는 튜플 (S,I)로도 정의된다.

• S는 가능한 분자의 집합이다. S={s₁...,s_n} 이고, n은 무한일 가능성을 내포하는 원소의 개수이다.
• R는 S에 속한 분자에 대한 n진법 연산이며, 반응 규칙 R={r₁...,r_n} 을 의미한다. 각각의 규칙, r_i의 화학적 반응은 a+b+c->a*+b*+c* 와 같은 방식으로 기술된다. (단, r_i는 연산자임에 주의)
• A는 규칙 R을 어떻게 부분집합 P$\subset$S 에 적용할지에 대한 알고리즘이다.
• I는 S의 분자들의 상호 작용에 대한 규칙이다.

인공 화학은 인공생명의 하위 분야이며, 구체적으로는 딱딱한 인공 생명의 하위 분야이다. 이 분야에 깔려있는 아이디어는, 살아있는 것을 구성하기 위해서는, 살아있지 않은 독립체로 이루어져야 한다는 것이다. 예컨대, 세포는 살아있지만, 살아 있지 않은 분자들로 이루어져있다. 인공 화학은, 극도로 기초 부터의 접근이 강조된 인공 생명이라고 볼 수 있다.

중요한 개념

• 구성: 구성은 닫혀 있으며, 스스로를 포함하는 분자의 집합이다. 그러므로 이 집합은 집합 외부에 대하여 아무것도 생성하지 못하며, 집합에 속해 있는 어떠한 분자도 집합 안에서 생성 될 수 있다.
• 닫힌 집합
• 스스로를 포함하는 집합
• 구성에 대한 하세 도표

진화 알고리즘

이 문단을 유전 알고리즘 문서로 합치자는 의견이 제시되었습니다. 토론에서 의견을 나누어 주십시오.

 유전 알고리즘 문서를 참고하십시오.

미시간 대학의 John Holland는 1975년에 게임 이론과 공학에서의 문제를 포함한 다양한 문제에 유전학적 선택을 적용하는 방법론을 개발하였다. 진화 알고리즘(Evolutionary Algorithm) 또는 유전 알고리즘(Genetic Algorithm)이라고 불리는 이 과정은 다음과 같은 규칙에 따라 작동한다.

1. 적당한 환경에서 몇가지 유전자형의 집단으로 시작한다.
2. 표현형에서 성공적인 유전자형 짝들을 선택한다.
3. 가장 성공적인 설계에 대응하는 유전자형들을 번식시킨다.
4. 새 후손으로 가장 덜 성공적인 유전자형을 대체하고 2단계로 돌아가서 사이클을 되풀이한다.

이 규칙에서도 알 수 있듯이 진화 알고리즘 또는 유전자 알고리즘은 19세기의 찰스 다윈(Charles Darwin, 1809~1882)이 주장한 진화론에서의 자연선택과 적자생존에 기반을 둔, 자연에서의 진화 현상을 컴퓨터적, 알고리즘적으로 응용하여 문제를 푸는 과정이다. 진화 알고리즘에서 쓰는 용어는 아래와 같다.

• 문제에 대한 각각의 가능한 해 → 유기체(organism) 또는 개체(individual)
• 가능한 해의 집합 → 개체군(population)
• 각각의 해의 특징을 구성하는 요소 → 염색체(chromosome)
• 염색체를 변형하는 연산자 → 유전연산자(genetic operator)

진화 알고리즘에는 여러 가지 종류가 있다.

1. 유전 알고리즘(GA),
2. 진화 전략(ES),
3. 진화 프로그래밍(EP),
4. 유전자 프로그래밍(GP)

이들은 주로 3가지의 진화적 프로세스, 즉 선택(selection), 돌연변이(mutation), 생식(reproduction)을 사용한다. 이러한 각각의 진화적 접근에는 세 가지 공통적인 요소들이 있다.

1. 적응도(fitness): 개체가 다음 세대에 얼마나 영향을 주는지를 결정한다.
2. 생식 연산자(reproduction operator): 개체가 다음 세대에 자손을 만들게 한다.
3. 유전 연산자(genetic operator): 부모의 정보를 통해 자손의 정보를 결정한다.

이러한 진화 알고리즘의 중요한 장점으론, 단순히 병렬적으로 나열된 가능한 해 중 진짜 해를 찾아나가는 것보다 더 효율적으로, 복수 개체 사이의 상호 협력(선택과 교배)을 통해 해를 찾아나갈 수 있다는 점이다. 뿐만 아니라 신경 네트워크(neural network) 등에서는 작업을 위해 평가 함수의 미분값이 필요할 때가 있는데, 이와 달리 진화 알고리즘은 현재 상태로만 판단하기 때문에 단순하고 쉬운 알고리즘이며 불연속적인 평가 함수에 대해서도 적용이 가능하다. 하지만 진화 알고리즘의 단점으론 어떤 문제를 진화 알고리즘을 이용해서 푸는 일반적인 방법이 없다는 점과 진화 과정에서 고려해야 하는 변수들이 많다는 점들이 있다.

진화 알고리즘의 예로는 개미를 키우는 MICROANTS가 있다.

진화 예술

진화 예술은 컴퓨터에 의해 만들어지는 예술의 한 형태로, 진화 디자인 가운데 예술적 창의성을 가장 큰 특징으로 갖는다. 진화 예술의 기본 배경은 사용자가 자연도태와 유사한 방식인 '선택'메커니즘을 통해 자신이 선호하는 작품을 만들고자 하는 것이다. 모든 진화 예술에서는 하나 이상의 부모 작품이 돌연변이 및 교배되어 다수의 자손 작품을 발생하게 되며, 적합도 평가에 기초해서 다음 세대를 구성할 작품이 선택된다. 가령, 미적인 이미지를 만드는 진화 예술 시스템은 임의의 값으로 초기화된 이미지 집단을 컴퓨터 화면에 보인다. 예술성을 평가할 기준을 컴퓨터 프로그램으로 만드는 데에는 아직 한계가 있기 때문에, 진화 예술가가 직접 이미지를 선택함으로써 자신이 선호하는 작품이 생존해서 더 좋은 작품으로 진화하도록 한다.

진화 예술 시스템은 평가를 통해 선택된 이미지들을 돌연변이해서 다음 세대의 이미지를 만들어낸다. 이렇게 만들어진 이미지는 이전 세대의 것 보다는 미적으로 개선된 것이다. 진화 예술가는 다시 평가에 참여하고 진화계산에 의해 새로운 세대의 이미지가 발생한다. 이런 과정은 원하는 이미지가 만들어질 때까지 반복될 수 있다. 물론, 초기 집단에서 임의로 만들어진 이미지 대신에 이전에 만들었던 작품이나 아직 완성되지 않은 작품을 사용할 수도 있다. 진화 예술에서 진화알고리즘은 끊임없이 새로운 것을 발생시키기 위해 사용된다. 본질적으로 적합도를 평가할 수 있는 기준이 존재한다면 문자열로 표현할 수 있는 모든 것을 진화알고리즘에 의해 진화시킬 수 있다. 예술성을 평가할 기준을 컴퓨터 프로그램으로 만드는 데는 아직 한계가 있기 때문에, 진화 예술에서 작품에 대한 적합도 평가는 사용자가 한다. 즉, 프로그램이 다수의 예술작품을 발생하고 사용자가 자신의 선호도에 따라 작품을 선택하면, 재결합을 통해 새로운 세대의 작품이 발생하게 된다.

진화 음악

진화 음악은 진화 예술에서 소리를 다루는 부분이다. 진화 음악은 진화 알고리즘으로부터 생성되는 알고리즘적인 음악이다. 진화 음악은 개인, 또는 여러 사람이 만들어낸 소리(멜로디 등)나 그 소리의 일부분을 사용하거나 완전히 랜덤하게 시작된다. 그 다음 계산적인 생물학적 과정(예를 들어 자연선택, 돌연변이, 재결합)을 사용하여 생산된 소리가 더 음악적이 되도록 만든다.

진화 음악의 합성은 소리를 생성하거나 악기를 종합하는 기술과도 연관되어 있다. 진화 음악은 사용자나 청중들에게 음악의 기능이 적합하도록 만들어주는 상호작용적인 진화 알고리즘을 사용하지만, 아직 계산적으로 음악의 품질을 측정하기는 어려움이 있다. 그러나 음악의 품질에 대한 자동 계산의 정확성을 높이는 것에 대한 연구도 현재 이루어지고 있다. 진화 계산 기술은 조화나 반주 작업에도 사용된다. 이러한 진화 연산 작업을 구현하는 기술로는 유전 알고리즘이나 유전 프로그래밍이 있다.

자연발생론

자연발생설(自然發生說, Abiogenesis)은 생명체가 부모 없이 스스로 생길 수 있다는 가설이지만, 인공생명에서 다루는 자연발생론이란 생명의 기원에 대한 알고리즘적 시뮬레이션을 의미한다.

표현 방법

상태/이벤트 표

상태 전이 표

현재 상태 → 입력 값 ↓	상태 A	상태 B	상태 C
입력값 X	...	...	...
입력값 Y	...	상태 C	...
입력값 Z	...	...	...

몇가지 종류의 상태 전이 표가 사용된다.가장 흔히 쓰이는 표현 방법은 다음과 같다: 현재 상태(예:B)와 입력값(예:Y)의 조합은 다음 상태(예:C)를 나타낸다. 전체 동작 정보는 표에서 직접 표현되지 않고, 각주를 이용하여서 추가하는 것만 가능하다. 전체 동작 정보를 포함하는 유한 상태 기계는 가상 유한 상태 기계(Virtual finite-state machine)의 상태 표를 이용하여 정의 가능하다.

UML 상태 기계

통합 모델링 언어(UML, 영어: Unified Modeling Language)는 상태 기계를 나타낼 수 있는 표기법을 갖고 있다. UML 상태 기계는 고전적인 유한 상태기계의 이점은 살리면서, 한계를 극복할 수 있다. UML 상태 기계는 동작와 전이의 연장선상에서 위계적으로 중첩된 상태와 직교 영역이라는 개념을 도입하였다. UML 상태 기계는 밀리 모델과 무어 모델의 특징을 동시에 가진다. 행위와 전이에서, 밀리 모델처럼 시스템의 상태와 이벤트의 발생 모두에 의존적이며, 또 무어 모델처럼 상태보다는 전이에 더 관련깊은 진입 동작과 퇴장 동작에 의존적이기도 하다.

SDL 상태 기계

기술 표준언어(SDL, )는 전이 동작을 표현하기 위한 그래픽 심볼을 포함한 ITU 인증 표준이다

• 이벤트 보내기
• 이벤트 받기
• 타이머 시작
• 타이머 취소
• 동시에 다른 상태 기계를 시작
• 결정

SDL은 추상 데이터 타입(ADT, 영어: Abstract Data Types)과 유한 상태 기계를 실행 가능하게 하기 위해, 실행 시맨틱을 삽입한다.

다른 상태 다이어그램

이 외에도 유한 상태 기계를 표현할 수 있는 방법은 많다.

사용되는 곳

4-비트 트랜지스터-트랜지스터 논리 카운터의 회로도이다.

하드웨어적 응용

디지털 회로에서, 유한 오토마타는 설계 가능 논리 소자, 프로그래머블 로직 컨트롤러, 논리 회로 그리고 플립플롭 또는 전자계전기를 사용하여 구축될 수 있다. 즉, 하드웨어적 응용에는 상태 변수를 저장할 프로세서 레지스터, 상태 전이 함수를 결정할 여러 가지 논리들과 유한오토모타의 출력을 결정할 논리들이 필요하다.

소프트웨어적 응용

다음과 같은 개념들이 일반적으로 유한 오토마타를 사용한 소프트웨어 구축에 사용된다.

• 오토마타 기반 프로그래밍
• 가상 유한 상태 기계

또한 이를 이용하여 다음과 같은 곳에 응용된다.

응용 프로그램의 설계

유한 오토마타는 미래의 상태에 대한 출력값이 이전 상태에 의존하여 동작을 생성한다. 기본적으로 유한 오토마타는 다음과 같은 것들로 구성된 컴퓨터 프로그램이라 할 수 있다.

• (1) 프로그램이 대응해야 하는 이벤트(Events)
• (2) 이벤트를 기다리는 프로그램 상태(States)
• (3) 이벤트에 대한 응답 시 상태들간 트랜지션(Transitions)
• (4) 트랜지션 동안 취해진 액션(Actions)
• (5) 이벤트들 간 액션에 필요한 값을 갖고 있는 변수들(Variables)

유한 오토마타는 다양한 많은 유형들의 이벤트에 의해 작동이 이루어지는 상황에서 가장 유용하고, 특정 이벤트에 대한 응답은 이전 이벤트의 순서에 기반한다. 유한 오토마타를 작동하게 하는 이벤트들은 키보드, 마우스, 타이머, 또는 네트워크 활동 같은 컴퓨터 외적인 요소에서 발생되거나, 응용 프로그램의 다양한 부분들 또는 다른 응용 프로그램들과 같은 컴퓨터 내적인 곳에서 발생될 수 있다. 이러한 유한 오토마타의 성질에 따라 자바스크립트, C# 등을 사용한 응용 프로그램 설계에 사용된다.

텍스트 필터링

자바나 C#, SQL 등의 프로그래밍 언어에서 결정적 유한 오토마타를 사용하여 지정된 글자가 적합한지 판별할 수 있다. 예를 들어 이메일의 기본적인 형식은 "문자열"+"@"+"도메인" 인데, 주어진 문자열과 이 형식이 일치하는치 판별할 수 있다. 자바에서는 java.util.regex 패키지에서, C#은 System.Text.RegularExpressions 네임스페이스에서, SQL언어는 직접 정규 문법을 사용할 수 있다. 사용자가 정규 문법을 사용해서 만든 코드는 각각의 프로그래밍 언어의 컴파일러에서 자동으로 결정적 유한 오토마타로 변환되어 사용된다.

컴파일러의 설계 (어휘분석기)

 이 부분의 본문은 컴파일러 설계입니다.

컴파일러(compiler, 순화 용어: 해석기, 번역기)는 특정 프로그래밍 언어로 쓰여 있는 문서를 다른 프로그래밍 언어로 옮기는 프로그램을 말한다. 이러한 작업을 수행하기 위해서는 프로그래머가 입력한 코드를 미리 정의된 자유 문맥 언어의 의미 단위로 나눌 수 있어야 한다. 이때, 유한 오토마타가 사용된다. 프로그래밍 언어의 의미 단위는 거의 예외 없이 정규집합으로 표현 될 수 있다.

대부분의 어휘 분석기 생성기들은 의미 단위를 나타내는 정규표현의 순열을 입력으로 받아서 어떠한 토큰도 인식 할 수 있는 하나의 유한 오토마타를 생성한다. 일반적으로 생성 과정은 일단 정규 표현을 ε-전이를 가진 비결정적 유한 오토마타로 변화시키고 나서 상태들의 부분집합을 이용하여 결정적 유한 오토마타를 구성한다. 각 최종 상태는 발견된 특정한 의미 단위들을 나타내므로 이러한 오토마타들은 무어기계라고 할 수 있다.

예를 들어, 파스칼 언어에 있어서 모든 변수(identifier)들의 집합은 하나의 언어이다. 각 변수는 하나의 문자(letter)로 시작되어야 하며 문자 다음에는 임의 개수의 문자나 숫자(digit)가 혼용하여 사용될 수가 있다. 다음의 문법은 변수에 대한 정확한 정의를 나타내는 규칙들이다.

• <id>→<letter><rest>
• <rest>→<letter><rest> | <digit><rest> | λ
• <letter>→a | b | … | z
• <digit>→0 | 1 | … | 9

이때 주어진 문자열이 변수인지를 확인할 때 결정적 유한 오토마타가 사용된다.

패리티 비트 생성

패리티 비트(Parity bit)는 정보의 전달 과정에서 오류가 생겼는지를 검사하기 위해 추가된 비트이다. 전송하고자 하는 데이터의 각 문자에 1 비트를 더하여 전송하는 방법으로 2가지 종류의 패리티 비트(홀수, 짝수)가 있다. 패리티 비트는 오류 검출 부호에서 가장 간단한 형태로 쓰인다.

• 짝수(even) 패리티는 전체 비트에서 1의 개수가 짝수가 되도록 패리티 비트를 정하는 것인데, 이를테면 데이터 비트에서 1의 개수가 홀수이면 패리티 비트를 1로 정한다.
• 홀수(odd) 패리티는 전체 비트에서 1의 개수가 홀수가 되도록 패리티 비트를 정하는 방법이다.

이러한 패리티 비트를 출력하는 과정에 유한 오토마타가 사용된다. 오른쪽 그림의 패리티 비트를 출력하는 유한 오토마타에서, A는 짝수 패리티, B는 홀수 패리티의 상태를 각각 나타낸다. 만일 입력이 010011일 경우에 M의 동작은 다음과 같다.

δ(A, 0) ＝A => output 0

δ(A, 1) ＝B => output 1

δ(B, 0) ＝B => output 1

δ(B, 0) ＝B => output 1

δ(B, 1) ＝A => output 0

δ(A, 1) ＝B => output 1

즉 출력되는 결과는 011101이다.

같이 보기

• 튜링 머신
• 앨런 튜링
• 노엄 촘스키
• 존 폰 노이만
• 기계론
• 인공생명
• 자동기계

외부 링크

• 앨런 튜링 홈페이지
• Moore or Mealy model?
• "Amazing Game of Life Demo"
• "3D Game of Life"
• "LifeWiki"