stanford-oval/wikipedia huggingface dataset:
The Gray Race
평가

| 전문가 평가> 평가 점수.출처 | 전문가 평가> 평가 점수.점수 |
| --- | --- |
AllMusic: 
Robert Christgau: 
Los Angeles Times: 
NME: 1/10
Rolling Stone: 
Spin: 7/10
유한 상태 기계

유한 상태 기계(finite-state machine, FSM) 또는 유한 오토마톤(finite automaton, FA; 복수형: 유한 오토마타 finite automata)는 컴퓨터 프로그램과 전자 논리 회로를 설계하는 데에 쓰이는 수학적 모델이다. 간단히 '상태 기계'라고 부르기도 한다.
유한 상태 기계는 유한한 개수의 상태를 가질 수 있는 오토마타, 즉 추상 기계라고 할 수 있다. 이러한 기계는 한 번에 오로지 하나의 상태만을 가지게 되며, 현재 상태(Current State)란 임의의 주어진 시간의 상태를 칭한다. 이러한 기계는 어떠한 사건(Event)에 의해 한 상태에서 다른 상태로 변화할 수 있으며, 이를 전이(Transition)이라 한다. 특정한 유한 오토마톤은 현재 상태로부터 가능한 전이 상태와, 이러한 전이를 유발하는 조건들의 집합으로서 정의된다.
예시 > 수리 기계와 인식기

수리 기계(acceptors)와 인식기(recognizers)는 입력값이 기계에서 받아들여졌는지 이진값인 '예 또는 아니오'로 결과를 출력한다. 유한 오토마타의 모든 상태는 받아들여지는지 또는 받아들여지지 않는지에 대한 값을 가지고 있다. 모든 입력이 처리되었을때, 만약 현재 상태가 받아들여질 수 있는 상태라면 그 입력값은 기계에 의해 받아들여진 것이다. 반대로 현재 상태가 받아들여질 수 없는 상태라면 그 입력값은 거부된 것이다.
유한 오토마타는 언어를 정의하는 데에도 사용될 수 있다. 받아들여지는 모든 단어를 포함하고 그 문법으로 기계를 구성할 수도 있다. 이렇게 유한 오토마타로 구성이 가능한 언어를 "유한 오토마타가 받아들일 수 있는 언어"라고 한다. 정의에 의해 유한 오토마타가 받아들일 수 있는 모든 언어는 정규 표현식이다. 또한 역도 성립한다. 즉, 모든 정규 표현식은 유한 오토마타가 받아들일 수 있다.
예시 > 변환기

유한 상태 변환기는 상태와 주어진 입력값에 기반하여 출력값을 생성한다. 전산언어학 분야에서 응용 프로그램을 제어하는 데 사용된다. 유한 상태 변환기는 다음과 같이 두 종류가 있다.
무어 모델(Moore model)
S는 상태의 유한 집합이다.
S0는 초기 상태이며 S의 원소이다.
Σ는 입력 값의 유한 집합이다.
Λ는 출력 값의 유한 집합이다.
T는 현재 상태와 입력 값을 기반으로 다음 상태값을 반환하는 상태 전이 함수이다: S × Σ → S
G는 현재 상태를 기반으로 출력 값을 반환하는 상태 전이 함수이다: S → Λ
밀리 모델(Mealy model)
S는 상태의 유한 집합이다.
S0는 초기 상태이며 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개의 상태를 가지고 있다면, 얻어지는 결정적 유한 오토마타는 최대 2n 개의 상태를 가지고 있으며, 이는 지수적으로 증가하므로 종종 큰 비결정적 유한 오토마타에 대해 이 변환은 비실용적이다.
정의 > 결정론 > 비결정적 유한 오토마타의 결정적 유한 오토마타로의 변환 > 멱집합 구성 알고리즘

이 부분의 본문은 라빈-스콧 멱집합 구성입니다.
M2=<Q, Σ, q2,0, δ2, A2>가 언어 L을 인식하는 비결정적 유한 오토마타라고 하자. 이 때, 결정적 유한 오토마타 M= <Q,Σ,q0,δ,A>는 다음의 조건을 만족하며, 언어 L을 인식할 수 있다.
Q = 2Q2 , 즉 Q2의 멱집합 (Power Set)
q0 = { q2,0 }
δ(q,a) = ∪p∈qδ(p,a)
A = {q ∈ Q | q ∩ A2≠0 }
비결정적 유한 오토마타 M2=<Q, Σ, q2,0, δ2, A2>와 같은 언어를 인식하는 결정적 유한 오토마타 M= <Q,Σ,q0,δ,A>을 얻기 위해, 다음의 과정을 따라 변환을 하면 된다.
(1) 최초에 Q = ∅이다.
(2) 먼저, { q2,0 } 을 Q에 넣는다. { q2,0 }는 결정적 유한 오토마타 M의 최초 상태이다.
(3) 그리고 Q 의 각 state q 에 대하여,
Q의 상태가 각 Σ에 대해 없을 경우, δ(q,a) = ∪p∈qδ(p,a)를 추가한다. 단, 여기서 우변의 δ는 M2의 것이다.
이 새로운 상태에서, δ(q,a) = ∪p∈qδ(p,a)를 δ에 추가한다. 우변의 δ는 M2의 것이다.
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) 관계에 있기 때문이다.
M1=<Q, Σ, q1,0, δ1, A1>가 언어 L을 인식하는 비결정적 유한 오토마타라고 하자. 또, 변환에 의해 얻어진 결정적 유한 오토마타를 M2=<Q, Σ, q2,0, δ2, A2> 라고 하자. 이를 증명하기 위하여, 모든 문자열 w에 대하여, δ1*(q1,0, w) = δ2*(q2,0, w) 임을 귀납법에 의해 보이면,
기초 단계 :
w = Λ일 때,
δ2*(q2,0, Λ) = q2,0 (δ2*의 정의에 의하여)
={q1,0} (결정적 유한 오토마타 M2의 정의에 의하여)
=δ1*(q1,0, q2,0 ) (δ1*의 정의에 의하여)
귀납 단계 :
어떤 문자열 w에 대하여 δ1*(q1,0, w) = δ2*(q2,0, w) 라고 가정하자.
이때 문자열 w 와 Σ의 기호 a에 대해,
δ1*(q1,0, wa) = ∪p∈δ1*(q1,0, w)δ1,0(p,a)
=δ2 ( δ1*(q1,0, w),a)
=δ2*( q2,0, wa)
그러므로, 어떤 문자열 w에 대해서도 δ1*(q1,0, w) = δ2*(q2,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)'을 이론적 또는 실체적으로 구현해 내고자 수많은 시도를 하였다.
역사 > 현대(20세기~) > 앨런 튜링(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)
상태 기록부(state register)
여기서 한 가지 주목할 점은, 튜링 기계의 상태, 가능한 기호, 그리고 수행 작업들 모두 "유한하고, 분명하며 구분가능하다"(finite, discrete and distinguishable)는 것이다. 물론 테이프의 양은 필요에 따라 무한히 길게 늘어질 수 있긴 하지만, 이러한 특징이 바로 튜링 기계가 띠고 있는 유한 오토마타적 성질이라 할 수 있다.
그러나 튜링 기계는 유한 오토마타에 포함되는 개념이 아니라, 역으로 유한 오토마타가 튜링 기계에 포함되는 개념이다. 유한 오토마타는 사실상 '머리'가 오른쪽으로만 움직일 뿐만 아니라, 읽을 수만 있고 쓸 수 없는 튜링 기계의 특별한 집합이다.
튜링 기계가 컴퓨터 과학 분야에서 중요한 이유는, 튜링 기계가 역사상 가장 정교하고 강력한 오토마타이기 때문이다. 실제로, 어떤 계산 또는 연산이 튜링 기계를 통해 모델링될 수 없다면 컴퓨터에 의한 어떠한 효과적 해결책도 없다는 것이 증명되었다고 하며, 이는 곧 튜링 기계가 현재 우리가 갖고 있는 디지털 컴퓨터의 역량과 대등한 수학적 모델이라고 할 수 있음을 의미한다.
역사 > 현대(20세기~) > 존 폰 노이만(John Von Neumann)

존 폰 노이만(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)에 의해 단순화되었고 실제로 구현되었다.
역사 > 현대(20세기~) > 크리스토퍼 랭턴(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등에 의해서도 동시에 논의되었다.
역사 > 현대(20세기~) > 워렌 맥컬럭(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의 공헌은
세련화 및 일반화를 통해 유한 오토마타(컴퓨터 연산 이론에서 중요한 형식주의)의 개념을 도출했던 형식주의
논리 설계(현대 컴퓨터 디자인의 기초적인 부분)의 개념의 영감을 주었던 기술
정신-육체 문제를 다루기 위한 최초의 컴퓨터 연산의 사용
정신과 뇌에 관한 최초의 현대적 컴퓨터 연산 이론
을 포함한다.
역사 > 현대(20세기~) > 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)에 의해 결정되지만 무어 기계는 오로지 현재 상태에 의해서만 결정된다는 점이다.
예를 들어 자동차가 빨간 신호등을 인식했을 때 바로 멈추면 무어 기계인 것이고, 현재 진행 중이던 일을 마친 이후에 멈추면 밀리 기계인 것이다.
역사 > 현대(20세기~) > 노엄 촘스키(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가지 종류로 분류될 수 있다.
Program-based: 프로그램 상의 복잡한 DNA 언어로 구현되며, 자주 사용되는 언어론 Turing Complete와 'Assembly Derivative'가 있다. 셀룰러 오토마타가 자주 사용되지만 필수 사항은 아니라고 한다.
Module-based: 만들고자 하는 개체는 여러 가지 부분, 즉 모듈(module)로 이루어져 있다. 각각의 모듈이 움직이는 방식은 프로그램을 통해 주어지거나 각각의 모듈의 창발적 상호작용(emergent interaction)에 의해서이다.
Parameter-based: 각각의 개체는 유한 개의 변수들을 갖고 있으며, 각각의 변수들은 개체의 하나 이상의 부분들의 상태를 다루거나 조작한다. 개체들이 가질 수 있는 행위들은 이미 프로그램을 통해 유한 개로 정해져 있다.
Neural net-based: 신경 네트워크 또는 'Close Derivative'에 의해 배우고 자라는 개체들의 시뮬레이션이다.
'부드러운' 인공생명의 대표적인 예로는 크리스토퍼 랭턴의 개미(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)는 점에 있다.
인공 생명과 연관된 분야 또는 개념으로는 아래와 같은 것들이 있다.
인공 지능(Artificial Intelligence, AI)
인공 화학(Artificial Chemistry): 화학 반응들을 추상화시키기 위한 인공 생명 집단 내에서의 방법으로서 시작한 분야다.
진화 알고리즘(Evolutionary Algorithms) :최적화 문제(optimization problem)에 적용된 약한 인공 생명 원리의 적용이라고 할 수 있다. 차이점으론 최적화 문제에선 진화 알고리즘은 개체의 적합함(fitness of an agent)을 문제를 푸는 능력으로 정의하는 반면 인공 생명에선 말 그대로 가장 잘 생존하는 능력으로 정의한다는 점이다.
진화 예술(Evolutionary Art): 인공 생명에서 사용하는 기술을 통해 새로운 예술을 만들고자 하는 분야이다.
진화 음악(Evolutionary Music): 인공 생명에서 사용하는 기술을 음악에 적용한 분야이다.
자연발생론(Abiogenesis): 때때로 자연발생론에서 인공 생명에서의 방법론을 사용한다고 한다.
유한 오토마타와 인공 생명 > 인공 생명과 관련된 분야들 > 인공 지능

인공지능(人工知能)은 철학적으로 인간이나 지성을 갖춘 존재, 혹은 시스템에 의해 만들어진 지능, 즉 인공적인 지능을 뜻한다. 일반적으로 범용 컴퓨터에 적용한다고 가정한다. 이 용어는 또한 그와 같은 지능을 만들 수 있는 방법론이나 실현 가능성 등을 연구하는 과학 분야를 지칭하기도 한다.
인공지능이란 분야를 처음 인식하기 시작한 것은 1943년 McCulloch 와 Pitts에 의해서 시작되었으며 그 동기는 뇌에 있어서 뉴런의 기능과 작용에 대한 연구와 명제 논리 그리고 튜링테스트 연구였다. 뉴런으로 연결된 네트워크 학습의 개념이 필요함을 주장하였으면 인간의 사고 과정을 최초로 연결망을 통해 모델화했다는 점에서 인공지능 역사상 의의가 매우 크다고 볼 수 있다.
1956년 여름 다트마우스(Dartmouth) 대학의 캠퍼스에 '생각하는 기계', 즉 지적인 행동을 하는 컴퓨터에 관해 토론하기 위해서 많은 사람들이 모였으며(수학자,심리학자,전기기술자,대학의 연구자 기업가 등등) 이들은 디지털 계산기를 '생각하는 기계'로 만들 수 있다는 신념을 가지고 있었고 이 회의가 인공지능(artificial intelligence: AI)이란 단어를 탄생시킨 계기가 되었다. 이 회의는 공식적으로 '다트마우스 하기 인공지능 연구계획'이라 불리며 그 뒤의 10년간을 지배한 여러 연구성과를 냈다. 이것이 제1차 인공지능 연구의 시작이었다.
인공지능에 대한 연구는 강한 인공지능과 약한 인공지능으로 나뉘는데, 강한 인공지능은 어떤 문제를 실제로 사고하고 해결할 수 있는 컴퓨터 기반의 인공적인 지능을 만들어 내는 것에 관한 연구다. 즉, 인공지능의 강한 형태는, 지각력이 있고, 스스로를 인식하는 것이라고 말할 수 있다.
반면 약한 인공지능은 어떤 문제를 실제로 사고하거나 해결할 수는 없는 컴퓨터 기반의 인공적인 지능을 만들어 내는 것에 관한 연구다. 그와 같은 시스템은 진짜 지능이나 지성을 갖추고 있지는 못하지만, 어떤 면에서 보면 지능적인 행동을 보일 것이다.
여기서 강한 인공지능이 존재할 수 있는지에 관한 철학적인 논쟁이 발생하였다. 강한 인공지능이 존재한다고 주장하는 사람들은 다음과 같은 4가지 논리를 든다.
인간의 마음은 유한 오토마타(Finite Automata)이고, 따라서 처치-튜링 명제는 뇌에 적용 가능하다.
인간의 마음은 소프트웨어이다(유한 상태 기계의 일종이다).
뇌는 순수한 하드웨어이다(말하자면 고전적인 컴퓨터처럼 동작한다).
인간의 마음은 오로지 뇌를 통해서만 존재한다.
그러나 로저 펜로즈를 포함한 몇몇 사람들은 처치-튜링 명제의 적용이 가능하지 않다고 논박한다. 어떤 이들은 인간의 마음은 물리적인 속성을 뛰어넘는 무엇이 있다고 이야기한다.
유한 오토마타와 인공 생명 > 인공 생명과 관련된 분야들 > 인공 화학

인공 화학은 3-튜플 (S,R,A)로 일반적으로 정의된다. 어떤 경우에는 튜플 (S,I)로도 정의된다.
S는 가능한 분자의 집합이다. S={s1...,sn} 이고, n은 무한일 가능성을 내포하는 원소의 개수이다.
R는 S에 속한 분자에 대한 n진법 연산이며, 반응 규칙 R={r1...,rn} 을 의미한다. 각각의 규칙, ri의 화학적 반응은 a+b+c->a*+b*+c* 와 같은 방식으로 기술된다. (단, ri는 연산자임에 주의)
A는 규칙 R을 어떻게 부분집합 P \subset S 에 적용할지에 대한 알고리즘이다.
I는 S의 분자들의 상호 작용에 대한 규칙이다.
인공 화학은 인공생명의 하위 분야이며, 구체적으로는 딱딱한 인공 생명의 하위 분야이다. 이 분야에 깔려있는 아이디어는, 살아있는 것을 구성하기 위해서는, 살아있지 않은 독립체로 이루어져야 한다는 것이다. 예컨대, 세포는 살아있지만, 살아 있지 않은 분자들로 이루어져있다. 인공 화학은, 극도로 기초 부터의 접근이 강조된 인공 생명이라고 볼 수 있다.
유한 오토마타와 인공 생명 > 인공 생명과 관련된 분야들 > 인공 화학 > 중요한 개념

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