(Computability and mental processes)
컴퓨터와 마음 : Philip N. Johnson-Laird 지음, 이정모. 조혜자 옮김, 민음사, 1991, page 46~67 (원서 : The Computer and the Mind: An Introduction to Cognitive Science, Harvard Univ. Press, 1988)
마음에 대한 이론이라고 해서 그 내용이 당연히 모호하다고 여겨서는 안된다. 한 가지 유용한 제한방법은 그것들을 계산가능한 형태로 표현하는 것이다. 왜냐하면 계산수학은 원래 아주 자명한 원리들에서 출발하여 무엇이 계산될 수 있는가를 보여주기 위해 발전되었기 때문이다. 계산가능성 (computability) 의 본질은 단순하다. 나는 일련의 예들을 통해 그러한 것을 제시할 것이다. 처음의 두 예는 더하기에 대한 초보적인 산술조작과 관련된 것이다. 그리고서 나는 자기들 각자의 우주 속으로 소풍을 갈 수 있는 로보트에 대한 두 예를 사용하여 어떻게 보다 강력한 계산을 만드는지를 보일 것이다. 이 로보트들은 기계와 문법 간의 관계도 예시해준다. 마지막으로 나는 궁극적인 계산기계를 고려해 볼 것이다. 이러한 예를 생각해 보는 요지는 계산이 컴퓨터와 같은 물리적인 도구에서 쉽게 구현되는 몇 개의 직관적으로 생각할 수 있는 기초적 구성단위에 의존한다는 것을 입증하기 위해서이다. 수학이 아주 엄밀하다고 생각하는 독자들은 이런 결론을 조금도 의심치 않고 다음 장으로 넘어갈 수 있을 것이다.
여러분은 두 개의 한 자리수를 더한 합은 금방 알아차린다. 예를 들면 여러분이 <9 더하기 8 은 ?> 이란 질문을 받으면 바로 <17 입니다> 라고 답할 수 있다. 다음,
139
+288
의 합을 구하기 위해서도 여러분은 이런 지식을 활용해야 한다. 그러나 한 열에서 다음 열로 한 자리씩 올림자리를 올려주는 과정이 추가된다. 즉 가장 오른쪽 열의 수의 합은 17 이고, 다음 왼편 열의 합에 올림자리 1 을 더해 주어야 한다.
이러한 더하기 절차는 간단하지만 효율적이다. 그 절차는 유한한 지시들로 이루어져 있다. 즉 그 지시들을 적절히 따른다면 유한한 단계들을 거쳐 두 자연수들의 합을 산출하게 된다. 여러분은 왜 사물의 유한한 성질에 대해 강조하는가를 의아해 할 것이다. 그러나 만약에 어떤 절차가 여러분으로 하여금 무한한 지시에 대한 지식을 요구하거나 무한한 단계를 수행할 것을 요구한다면, 그 절차는 실제적으로 사용되기 어렵다. 예를 들면 요리법이나 뜨개질의 경우에도 유한한 단계들 안에서 유한한 양의 지식을 사용하여 효율적인 절차를 통하여 원하는 목표에 도달한다. 나는 이러한 종류의 효율적인 절차를 분명히 기술하는 개념으로 <프로그램> 이란 단어를 사용할 것이다. 수학자들은 <알고리즘> 이란 단어를 사용하기도 한다.
더하기를 수행할 수 있는 프로그램을 고안하려 한다고 가정해 보자. 그 프로그램은 앞 장에서 기술한 이진 숫자를 사용하면 간단하게 해결된다. 이진 숫자를 사용하면 두 개의 0의 합은 0이고, 1과 0의 합은 1이라는 식의 간단한 이진 더하기 규칙만을 필요로 한다. 앞 장에서 보았듯이 2 라는 수는 10 으로 쓰여지기 때문에 1 더하기 1의 합은 그 열은 0이 되면서 왼쪽의 다음 열에 1 을 넘겨야 한다. 3 + 2 의 합을 이진법으로 계산하는 것을 고려해 보자 :
우리는 가장 오른쪽부터 더하기를 시작하게 되는데 1 과 0 을 더한 결과는 분명히 1 이다. 그 다음에는 다음 열의 1 에 1 을 더해야 하고, 그 결과는 10 이 된다. 따라서 1 은 다음 열로 올라가게 된다. 이 열은 다른 수가 없기 때문에 그 합은 1 이 된다. 결과로 나온 이진수 101 은 십진수 5 와 같다.
프로그램은 하나의 한 자리 올림수가 열을 한 칸씩 전진하여 올라가는 지시를 포함해야 한다. 한 가지 해결방법은 올림이 발생했는지를 계속 추적하고, 한 번 올림되는 더하기에 대해 별도의 일련의 지시를 명시해야 한다. 그 프로그램은 다음의 지시들을 지닐 수 있다 :
올림이 없는 상태 :
올림이
없는 상태를 유지
1 + 1 = 0 올림상태로 전환
더 이상 더할 숫자가 없으면 기계는 정지한다.
올림이 일어나면, 프로그램은 한 칸 올라간 올림상태로 들어가고 올림을 포함시키기 위해 적절히 수정된 규칙들을 사용한다.
0 + 0 = 1 올림이 없는 상태로 다시 전환됨
올림상태를
유지
더 이상 더할 수가 없으면 기계는 1을 출력하고 정지한다.
이러한 프로그램을 수행할 기계를 설계하는 방식은 여러 가지로 생각해볼 수 있다. 오래된 기계식 계산기처럼 톱니들과 지렛대로 만들어질 수도 있고, 물흐름을 이용하여 수력체계로 만들어질 수도 있으며, 전류가 흐르는 실리콘 칩에 트랜지스터를 부착시켜 만들어질 수도 있다. 또한 그것은 뇌에 의해서도 수행될 수 있다. 이러한 기계들 각각은 이진법의 상징들을 표상하기 위해 각기 다른 매개물, 즉 톱니의 위치, 물의 존재나 부재, 전압의 수준, 그리고 신경충동 등을 사용한다. 그러나 중요한 것은 기계의 물리적인 구조가 아니라 프로그램에 있다. 그림 3.1 은 그 디자인을 요약해 준다. 즉 두 개의 원은 기계의 두 상태를 나타내고, 화살표는 지시들을 나타내며 한 상태에서 다른 상태로의 이동을 보여준다.프로그램은 더해져야 할 숫자쌍들이 한 열씩 입력되면 그 결과로 하나의 숫자를 산출해 낸다.
계산모형의 관점에서 보면 기계는 가장 단순하고 실현가능한 디자인의 한 사례이다. 그것은 유한수의 기본상징들과 지시, 기억상태를 갖기 때문이다. 그런 장치는 <유한상태> 의 기계라고 하며, 그런 기계는 조합 자물쇠에서부터 편물기에 이르기까지 종류가 다양하다.
그림3.1 : 두 개의 이진 숫자들의 합을 구하는 유한상태 기계. 이 기계는 원으로 표현되는 두 상태들을 갖는다. 한 상태는 올림이 일어난 상태이며, 다른 한상태는 올림이 일어나지 않은 상태이다. 화살표는 한 상태에서 다음 상태로의 전이를 나타내고, 화살표 위의 등식은 수행 지시문이다. 즉 등식의 왼편은 더해질 두 숫자들의 입력상태를 나타내고, 오른편은 기계가 산출하는 결과를 나타낸다. 이와 같이 올림이 없는 상태에서 시작되어, 1 + 1 을 수행한 결과는 0 과 올림상태로 전이를 가져온다.
박테리아처럼 자신의 세계를 탐험할 수 있는 로봇을 상상해 보자. 그러나 그 로봇은 단지 일련의 일정한 보폭의 걸음걸이로만 움직일 수 있고, 유람 (excursion) 할 수 있는 시각점에서 동, 서, 남, 북으로만 걸음을 옮길 수 있다고 하자. 그것은 유람하려고 할 때마다 항상 그 시각점으로 돌아와야만 한다. 그림 3.2 는 그러한 움직임의 한 예를 보여준다. 어떻게 우리는 그 로봇이 유람 시각점으로 찾아갈 수 있도록 하며, 그리고 어떻게 그 로봇이 취한 발걸음의 기록만 가지고 가장 짧은 노선을 발견할 수 있도록 하는 <추측항법> 의 체계를 고안할 수 있는가? 유람의 거리에는 제한이 없기 때문에 이 문제는 유한상태의 기계에서 가능한 것보다 더 많은 계산력을 요구한다.
그림 3.2 : 로봇의 <시작점> 으로 돌아오는 유람. R 지점으로부터의 길은 가능한 한 가장 적은 발걸음을 취하는 짧은 노선에 속한다.
계산력이라는 개념은 계산의 속도나 효율성보다는 계산이 무엇을 할 수 있는가를 의미한다. 여러분은 그 비밀이 어떤 새롭고 강력한 유형의 지시에 있을 것이라고 상상할지도 모른다. 그러나 사실상 다소 놀랍게도, 계산속도나 효율성을 높이기 위해 수정해야 하는 것은 지시를 새롭게 하는 것이 아니라 더 좋은 기억을 갖는 것이다. 필요로 되는 것은 계산 동안에 얻어진 중간결과들을 담을 무제한의 기억인 것이다. 기억의 힘인 것이다.
가장 단순한 형태의 무제한적인 기억은 접시더미와 비슷하다. 여러분이 직접 접근할 수 있는 유일한 접시는 접시더미에서 가장 위에 놓여 있는 것이고, 여러분이 새 접시를 놓을 수 있는 유일한 장소는 그 접시더미의 가장 위이다. 한 더미의 상징들이 비슷한 형태로 기억을 구성하여 가장 위에 있는 항목에 접근하도록 한다. 만약에 하나의 프로그램이 그 더미의 아래쪽에 저장된 하나의 상징을 꺼낼 필요가 있다면 그 상징 위에 있는 항목들은 치워져야만 한다. 그러나 일단 하나의 상징이 그 더미에서 치워지면 그것은 더 이상 기억에 존재하지 않는다. 따라서 그것은 즉시 사용되어야 하거나, 아니면 잊혀진다.
로봇의 유람문제를 풀기 위해 나는 더 단순한 장치에서부터 시작하려 한다. 그 장치는 단일 차원을 따라 앞으로나 뒤로만 움직일 수 있다. 로봇의 유람이 항상 유람 시각점에서 끝을 내야만 한다면 앞으로 걷는 발걸음 수와 뒤로 걷는 발걸음 수가 동일해야만 한다. 우리는 로봇에게 셈하는 기계 (카운터) 처럼 작용하는 유람 프로그램을 장착시킬 필요가 있다. 이것은 더미 (stack) 를 사용함으로써 그 여행의 움직임을 기록할 수 있다. 우리는 앞으로 한 걸음 가는 것을 <앞 (forward)>이라는 상징으로, 뒤로 한 걸음 가는 것은 <뒤 (backward)>라는 상징으로 표시할 것이다. 이러한 상징들은 이진 부호로 표시될 수 있다.
이 프로그램은 더미 (스택)가 비어 있는 상태에서 출발한다. 그리고 일반적으로 로봇이 한 발걸음 떼어 놓을 때 그 프로그램은 그 발걸음에 대응하는 상징을 더미의 맨 위에 놓는다. 그러나 하나의 예외는 있다. 한 방향에서 한걸음 걸은 것은 반대방향으로의 한걸음에 의해 삭제된다는 것이다. 따라서 그러한 연속절차가 일어날 때마다 그 더미의 맨 위에 있는 상징은 제거된다. 예를 들어 만약에 로봇이 뒷걸음을 치고, 더미의 맨 위에는 <앞> 이라는 상징이 있다면 그 프로그램은 그것을 더미에서 제거할 것이다. 따라서 로봇이 유람 시작점으로 돌아오는지 아닌지를 결정하는 것은 단순하다. 즉 더미가 비어 있을 때는 언제나 돌아오는 것이다.
우리는 로봇의 더미의 상태를 살펴봄으로써, 로봇이 자신의 우주속으로 들어가고 되돌아올 때 그 프로그램이 어떻게 작용하는지를 알 수 있다. 그 프로그램은 빈 더미에서 출발하여 앞으로 한걸음을 걸으면 <앞> 이라는 상징을 그 더미의 맨 위에 놓는다 :
----→ <앞>
또 다른 한걸음을 앞으로 걸으면 그 프로그램은 또 다른 <앞> 이라는 상징을 더미 위에 올려놓는다 :
----→ <앞>
<앞>
이제 시작점으로 향해 되돌아온다고 하자. 이 움직임은 이전의 것을 무효화하여 더미의 맨 위에 있는 <앞> 이 제거된다 :
<앞> ←----
그 로봇이 한걸음을 더 뒤로 취하게 되면 더미에 있는 상징이 제거된다 :
←----
이 지점에서는 더미가 비었기 때문에 로봇은 시작점에 와 있게 된다.
동 - 서, 남 - 북의 두 차원에서 움직이는 로봇의 여행 프로그램은 이제 분명해졌다. 그것은 두 개의 더미들을 사용한다. 하나는 북쪽과 남쪽을 향한 발걸음을 기록하고 다른 것은 동쪽과 서쪽을 기록한다. 여행의 어떤 지점에 있어서 로봇이 시작점으로부터 떨어진 위치는 두 더미의 내용으로 직접 표상된다. 시작점으로 돌아오는 가장 짧은 노선은 가능한 한 빨리 더미가 비는 것으로서, 각 발걸음은 현재 더미의 맨 위에 놓여 있는 상징에 반대되어야 한다. 그림 3.3 은 로봇이 이전 그림에서 묘사되었던 여행을 할 때 로봇이 가지는 두 개의 여행 도구 (더미) 의 내용을 보여준다.
엄격하게 말해서 이 프로그램은 두 개의 더미를 요구하지는 않는다. 그들의 내용은 단일상징으로 합쳐질 수 있다. 가능한 조합의 갯수가 <NE>, <-E>, <E-> 의 예에서와 같이 유한하기 때문이다. 그러한 쌍들을 갖는 것은 단일 더미로도 충분하다.
그림 3.3 : 로봇의 유람을 위한 여행 프로그램으로 사용되는 더미 (스택) 의 내용, 두 개의 더미에 담기는 내용들은 단일 더미에 저장된 상징에서 조합될 수 있기 때문에 사실상 두 개의 더미는 필요하지 않다. 로봇은 R 지점에서부터 시작점으로 가는 가장 짧은 노선을 취한다.
로봇이 각 발걸음을 옮기는 방향을 결정하는 것은 무엇인가? 여행 프로그램 내에는 그러한 결정을 만드는 지시는 없다. 그것은 단지 주어진 여정이 용납될 수 있는 것인가 아닌가만을 평가한다. 로봇은 가능한 한 빨리 더미들을 비우는 노선을 선택함으로써 시작점으로 돌아온다. 그러한 프로그램은 흥미로운 성질을 갖는다. 더하기에 대한 프로그램은 결정론적이다. 계산하는 각 단계에서 그것이 수행할 수 있는 단 하나의 지시만을 갖고, 선택은 전적으로 입력된 자극과 기억의 현상태에 의해 결정된다. 대부분의 프로그램들은 결정론적이다. 그러나 로봇이 여러 다른 노선들 가운데서 선택하는 것은 허용하는 프로그램은 결정론적이지 않다. 여행에서 돌아오는 부분에서 수행될 수 있는 지시는 하나 이상이 있을 수 있다. 그것은 이 더미나 아니면 다른 더미를 (둘 다 상징들을 갖고 있다고 한다면) 비우는 발걸음을 선택할 수 있다.
때때로 사람들은 일상생활에서 분명히 비결정론적인 기계를 만나게 된다. 예를 들어 내 전화는 최근에 간헐적으로 오류를 일으키게 되었다. 그것은 갑자기 아무 이유 없이 벨이 울리곤 했다. 그러나 사실상 그것은 외부의 결정론적인 원리에 따라 작동하고 있지는 않았던 것이다. 회로내에서 어떤 전선이 풀려 있었기 때문이다. 양자이론이 맞는다면, 아마도 유일한 진정한 비결정론적인 행위란 입자들의 행동일 것이다. 기계들 (컴퓨터를 포함해서) 은 작동원리들을 결정론적으로 따르도록 고안되었다. 만약에 자신의 우주를 멋대로 움직이는 로봇 (아니면 박테리아) 과 같은 무작위적인 행동을 모사할 기계를 원한다면, 우리는 몬테카를로 도박장의 카지노에서 절차를 빌려와서, 결정론적이지만 예언할 수는 없는 사건을 사용할 수 있다. 그러나 어떻게 하나의 결정이 만들어지는가를 무시하는 것이 종종 편리할 때가 있다. 왜냐하면 결과는 결정론적이지 않은 내용일 것이기 때문이다. 이러한 편법은 창조과정을 분석하는 데 유용할 것이다 (제 14장 참조).
하나의 복합상징은 가능한 조합들을 다루는 규칙들에 따라 기초적 상징들을 조합하여 나올 수 있다. 따라서 로마 숫자들에는 그 기초상징들의 가능한 순서들을 명시하는 규칙들이 있다. 문법은 한 영역의 상징들 (또는 언어) 에 대한 규칙들의 집합으로서, 적절하게 형성되는 구성물들을 모두 특정지으며, 그것들의 구조에 대한 기술을 제시한다. 언어학자인 촘스키 (N. Chomsky) 에 의해 처음 제안된 것처럼, 이렇게 정의된 문법은 프로그램과 밀접히 관련된다. 그 관계의 성질은 일차원에서 움직이는 로봇의 문제로 되돌아가 봄으로써 알 수 있다. 로봇의 여행은 어떤 것이라도 일련의 상징들로 표상될 수 있다 :
앞 앞 뒤 앞 앞 뒤 뒤 뒤
그리고 우리는 로봇이 시작점에 있는 것으로 끝나는 모든 가능한 여행들을 규정하는 하나의 문법을 구성할 수 있다.
용인될 수 있는 두 개의 가장 작은 여행은 한 발걸음 앞으로 가고, 다음에 한 발걸음 뒤로 가거나 아니면 그 역으로 행하는 것이다. 따라서 문법내의 처음 두 규칙은 자명하다 :
1. 여행 = 앞 뒤
2. 여행 = 뒤 앞
<여행> 은 하나의 용인 가능한 여행을 지칭하고, <=> 는 그것의 왼편에 있는 상징이 오른편에 있는 상징으로 분석된다는 의미이다.
이러면 중요한 문제점에 봉착하게 된다. 여행에서는 발걸음의 수가 한정되어 있지 않다는 점이다. 어떤 용인될 수 있는 여행을 고려해 볼 때, 그 여행이 얼마나 길든 간에 항상 앞으로 나가는 발걸음으로 여행을 시작하고, 그것에 대응하는 뒷걸음으로 끝낼 수 있다면, 그 결과는 여전히 용인될 수 있을 것이다. 유사하게 뒷걸음으로 여행을 시작하고 그에 대응하는 앞걸음으로 끝을 내면, 그 결과 역시 용인될 수 있을 것이다. 문제는 문법에서 이런 가능성들을 다루는 것이다. 계산이론을 연구하는 논리학자들은 멋진 착상을 해내었다. 규칙들이 이러한 두 가능성을 직접적으로 다루는 것이다.
3. 여행 = 앞 여행 뒤
4. 여행 = 뒤 여행 앞
규칙 3은 어떤 용인되는 여행에다 시작부위에 앞걸음 하나와, 끝나는 부위에 뒷걸음 하나를 첨가한다면 그 결과도 역시 용인되는 여행이 된다는 것을 말한다. 규칙 4 는 그 반대의 첨가를 허용한다. 이런 규칙들은 <여행> 이라는 상징이 등식의 표시 양편에 모두 있기 때문에 순환적이다. 그러나 <회귀 (recursion)> 로 알려진 이러한 순환은 모호하기는 하지만 악순환은 아니다. 우리가 그 문법을 하나의 여행을 분석하는 데 사용한다면 그것은 더 분명해질 것이다.
상징들의 열로 표상되는 여행은 고려해 보자 :
앞 앞 뒤 뒤
규칙 3은 어떤 여행이 <앞 여행 뒤>로 분석될 수 있다면 용인될 수 있다고 말한다. 따라서 규칙 3은 거꾸로 된 나무와 같은 도식으로 기술될 수 있는 분석을 제공한다 :
도표의 꼭대기에 있는 상징 <여행>은 규칙 3의 왼편 상징에 해당되는 것이고, 도표의 아래쪽의 세 개의 상징들은 규칙의 오른편에 있는 것들에 해당하는 것이다. 물론 이 분석은 불완전하다. 우리는 도표의 아래쪽에 있는 <여행>도 용인된 여행을 지칭함을 확실히 해야 한다. 사실상 그것은 원래의 상징열에 있는 <앞 뒤>에 해당하고, 규칙 1은 그것들이 용인될 수 있는 여행을 이룬다는 것을 명시한다. 따라서 완전한 여행의 분석은 다음의 나무도식으로 기술될 수 있다.
마찬가지로 나무도식 대신에 여행의 상징들을 함께 괄호에 묶어 괄호에 적절한 명칭을 붙일 수 있다 :
(앞 (앞 뒤) 뒤)
여행 여행
용인된 여행이 이런 식으로 다른 여행 속에 삽입될 수 있는 횟수에는 제한이 없다.
마지막으로 필요한 규칙은 다음과 같다 :
5. 여행 = 여행 여행
이 규칙은 분명히 일반화된 것을 말한다. 만약에 두 개의 용인될 수 있는 여행이 하나씩 차례로 조합된다면, 그 결과 역시 용인된 여행이 된다. 만약 우리가 세 개 이상의 용인된 여행들을 조합하면 그 결과 역시 용인될 수 있다. 그러나 이러한 사실을 다룰 더 이상의 규칙들은 필요로 하지 않는다. 몇 개의 하위 여행들로 이루어진 여행을 분석하기 위해서는 규칙 5와 같은 순환규칙들이 반복해서 사용될 수 있다.
프로그램과 문법 간에는 일반적인 관계가 있다. 어떤 프로그램의 출력도 하나의 문법으로 다루어질 수 있다. 그러나 문법은 그 자체로는 아무 일도 할 수 없다. 문법은 상징들을 생산해 내거나 분석하는 데 사용되기를 기다리고 있을 뿐이다. 그러나 프로그램은 수행능력이 있다. 프로그램은 상징 열들을 만들어내거나, 상징열을 분석하기 위한 나무도식을 만들어내는 데 문법을 사용할 수 있다.
여행 프로그램이 여행에 대한 문법에 기초할 수 있기는 하지만 그것은 사용할 필요는 없다. 앞에서 언급했던 프로그램들은 문법적인 규칙들을 사용하지 않는다. 이 점이 중요하다. 동일한 계산을 수행하기 위해 고안되는 각기 다른 프로그램 방식은 무제한으로 항상 존재한다. 우리는 문법을 가지고 여행할 수 있지만, 또한 문법 없이도 여행할 수 있다. 우리는 두 수를 십진법 숫자로도 더할 수 있고, 이진법 숫자로도 더할 수 있다. 토끼 가죽을 벗기는 방법이 다양하듯이 프로그램을 설계하는 방법들도 다양하다.
보다 강력한 프로그램이 도입되면서 그 출력을 특징짓기 위해 더 강력한 문법들이 필요로 된다. 반대로, 보다 강력한 문법들이 언어나 상징 영역을 규정하기 위해 도입되면서, 그 구조를 분석하거나 조합하기 위해 더 강력한 프로그램이 요구된다. 이미 언급한 것과 같이 강력함이란 중간결과들에 대한 기억에 의존한다. 유한상태의 기계들은 단지 유한 수의 결과들에 대한 기억만을 지니며, 이것을 기계의 상태로 다룬다. 유한상태의 기계는 여행 프로그램을 수행할 수가 없다. 여행이 얼마나 길어야 하는지에 제한이 없기 때문이다. 그러나 단일 더미와 같은 기억을 첨가하면 그 기계는 더 강력해진다. 그것은 무제한의 중간 결과들을 저장할 수 있고, 따라서 시작점으로 돌아오는 길을 발견할 수 있다. 이와 관련하여 뒤따르는 자연스런 물음은 어떻게 기억이 더 개선될 수 있는가이다.
하나의 자연스런 접근은 기억이 더미처럼 작용하는 제한을 없애고, 어떤 양의 기억에도 제한이 없이 접근하는 것을 허용하는 것이다. 그러한 기억을 나타내고자 착상된 여러 방식들이 있다. 튜링 (A. Turing)은 아마도 가장 단순한 착상을 했었던 것 같다. 그는 어떤 아동의 산수공책을 길게 찢은 조각과 같은 부분 (cell)들로 나누어진 하나의 테이프에 기억을 담는 기계를 생각해 내었다. 그 테이프는 한 부분의 내용을 읽을 수 있는 장치 아래서 앞뒤로 움직일 수 있고, 필요하다면 현재의 상징을 지우고 다른 상징으로 대처할 수 있다. 기계가 테이프의 한 끝에 도달하면 테이프가 더 첨가될 수 있어서 기계의 기억이 모자라지는 않는다. 하나의 상징은 단지 그 기계에 의해 삭제될 때에만 기억에서 사라지므로 이 체계는 더미의 제한성을 면해 주고 있다. 그러나 더미를 두 개 두면, 두 개의 더미 사이에 상징들을 옮겨놓음으로써 무한히 확장 가능한 테이프를 모사할 수 있다.
테이프는 무제한적으로 제공되기 때문에, 하나 이상의 동일한 테이프가 초기자료를 기계에 입력하고, 중간결과들을 저장하고, 최종적인 결과를 내보내는 데 사용될 수 있다. 테이프는 입력과 기억과 출력이 조합된 것으로 작용한다. 만약 이러한 각기 다른 목적들을 위해 분리된 테이프들을 사용하더라도, 기계의 힘은 증진되지 못한다. 또한 병렬적으로 여러 개의 테이프들을 사용하는 것이다. 이차원, 삼차원, 또는 다차원적인 형태의 표상을 사용하는 것도 기계의 힘을 증진시키지는 못한다. 이러한 수정은 어떤 일이 어떻게 행해지고 있는가에, 즉 사용되는 프로그램의 종류와 그 속도와 효율성에 영향을 미칠 수는 있지만, 무엇이 기계에 의해 행해질 수 있는가에는 영향을 미치지 못한다.
유한한 상태의 기계에 무제한적인 테이프를 장치하면, 그 결과는 가장 강력한 계산장치인 튜링기계가 된다. 그것은 네 개의 기초적인 조작만으로 수행할 수 있다. 그 하나는 테이프에 0을 1로 기록할 수 있는 것이고, 둘째는 테이프에 1을 0으로 기록할 수 있는 것이며, 셋째는 테이프의 칸 하나를 왼쪽 옆으로 옮겨갈 수 있는 것이며, 넷째는 테이프의 칸 하나를 오른쪽으로 옮겨갈 수 있는 것이다. 튜링기계는 중간결과들을 테이프 위에 쓰여질 수 있도록 불러낼 수 있다는 점을 제외하면 유한상태의 기계처럼 지시들로 이루어진 프로그램에 의해 제어된다. 각각의 지시는 하나의 조건과 그 조건이 만족되면 수행되는 작동을 명시한다. 그 조건은 테이프 위에 적힌 상징과 기계의 상태에 의해 결정된다. 그리고 작동은 네 개 중 한 조작과 기계의 다음 상태로의 전환을 말한다. 다음은 죄수의 빗금 (tally , 제2장 참조) 으로 표현된 두 수를 더하는 튜링기계에 대한 지시들의 일부이다 :
1936년에 튜링은 계산될 수 있는 것이라면 어떤 것이건, 테이프의 한 칸마다 이진 부호의 한 숫자를 지니는 일차원적 테이프가 있는 유한상태 기계의 프로그램에 의해 계산할 수 있다고 가정했다. 계산이라는 개념이 명료한 것이 아니므로 이러한 가정은 입증될 수가 없다. 사실상 튜링이 제공한 것은 하나의 모호한 개념을 명료하게 분석하는 것이었다. 그는 가능한 - 최소의 - 것을 당연한 것으로 전제하고 들어가는 데에 성공했다. 그 이후의 디지털 컴퓨터 발달이 보여주는 것처럼, 그는 켈빈 경의 <기계적인 (mechanical)> 설명에 대한 요구를 만족시킬 수 있는 정도 이상의 것을 당연하게 여기지 않았다. 다른 누군가가 튜링과 마찬가지로 최소한의 것을 당연한 것으로 전제하는 대안적인 형태의 계산을 발전시키고, 튜링기계에서는 얻어질 수 없는 결과를 산출한다면 튜링의 가정은 반증될 것이다. 그러나 지금까지 계산가능성 (computability) 에 대한 많은 대안적인 개념들이 제안되어 왔으나 그것들의 능력은 모두 튜링기계와 동등한 것임이 밝혀졌다.
튜링기계의 프로그램은 지시들의 집합이다. 각 지시는 기계의 상태와 테이프에 적힌 네 유형의 조작에 대한 하나의 표준 부호를 사용하여 이들을 이진부호로 차례차례 상징화할 수 있다 (우리는 다시 수 상징들의 위력을 알 수 있다). 이에 따라 자연히 각각의 튜링기계는 아주 길기는 하지만 단일한 이진 숫자로 표상될 수 있다. 그 이진 숫자는 지시들 각각에 하나씩 이진 숫자들을 할당시킴으로써 구성된다 (많은 집필가들은 DNA 의 유전정보 표상과 유사하다는 점에 매력을 느낀다). 이러한 부호체계를 고려한다면 어떤 특정 튜링기계의 조작을 모사할 수 있는 소위 <보편 (universal)>기계를 만드는 것이 가능하다. 보편기계는 자료와 특정 튜링기계의 지시인 이진 숫자 부호들을 읽는다. 보편기계의 지시는 특정 튜링기계의 이진 숫자로 부호화된 지시를 해석하고, 이 지시를 입력자료에 적용해 수행하게 한다. 이것은 어떤 튜링기계도 모사할 수 있으므로 보편관계인 것이다. 이것이 현대 디지털 컴퓨터의 이론적 조상이다.
컴퓨터는 튜링기계와는 아주 다른 방식으로 작용한다. 컴퓨터의 기억은 일차원적인 테이프가 아니며, 컴퓨터는 아주 풍부한 기본 조작들로 구조화되어 있다. 그러나 컴퓨터는 적절한 부호로 쓰여진 어떤 프로그램이건 수행할 수 있기 때문에 컴퓨터 프로그램은 특정한 튜링기계와 유사하고, 보편기계와도 유사하다. 디지털 컴퓨터에서 계산될 수 있는 것은 어떤 것도 튜링기계에 의해 계산될 수 있다.
그러나 모든 것이 계산될 수 있는 것은 아니다. 진술할 수는 있지만 그것을 계산으로 해결할 수 없는 문제들이 많이 있다. 예를 들어 임의적으로 선택된 어떤 튜링기계에게 임의적으로 선정한 어떤 자료들을 주었을 때 정지할 것인지 아니면 끊임없이 계산을 진행할 것인지를 결정해줄 보편기계를 고안한다는 것은 불가능하다. 따라서 어떤 문제가 계산 가능한 해를 가졌는지 아닌지를 결정하는 것을 보장할 검사는 없는 것이다.
마음은 계산적인 현상인가? 이에 대해서는 아무도 알지 못한다. 마음은 계산적일 수도 있다. 아니면 어떤 종류의 컴퓨터로도 수행될 수 없는 조작들에 의존할 수도 있다. 그럼에도 불구하고 이러한 조작들이 효율적인 절차들이라면 그것들은 계산의 성질에 대한 튜링의 가정이 잘못되었음을 입증하는 것일 것이다. 그러나 날씨에 대한 이론이 비나 햇빛 등의 날씨 그 자체와 혼동되어서는 안된다. 분명한 사실은 계상가능성이 마음의 이론들에 대한 적절한 개념적 도구를 제공한다는 것이다. 이 도구는 명백하지 않은 것은 아무것도 인정하지 않는다. 필요하다면 어떤 계산도 테이프를 움직이고 테이프 위에 이진부호를 기록하도록 하는 유한 수의 지시들로 항상 환원시킬 수 있다. 그러나 튜링의 가정을 받아들인다면, 어떻게 사람들이 얼굴을 알아보고, 연역적으로 추론하며, 새로운 사고를 창조해 내고, 숙달된 행위들을 통제하는지 등의 심리저기 현상에 대한 명백한 설명은 항상 컴퓨터 프로그램에 의해 모형화될 수 있다.
인지과학에 대해 세 가지 시사되는 의미가 있다.
첫째, 어떤 계산 가능한 과제를 수행하는 데는 무한히 서로 다른 프로그램들이 있기 때문에 인간수행에 대한 고찰을 통해 정확한 이론 이외의 것들을 모두 제거할 수는 없다. 항상 거의 같은 정도로 가능성이 있는 대안적인 이론들이 있을 수 있기 때문이다. 이론들은 경험적인 자료들에 의해 결정을 내리기는 매우 미흡하다. 항상 이론이란 관찰된 사실과 관찰될 수 있는 것을 넘어서 불변적으로 진행되는 것이다.
둘째, 만약에 심적 과정에 대한 어떤 이론이 보편기계와 동등한 정도로 강력하다면, 그 이론에 대한 반박이 어려울 것이다. 뒤에서 보겠지만 그러한 이론은 어떤 형태의 관찰된 반응들도 다룰 수 있을 것이다.
셋째, 마음에 대한 이론들은 컴퓨터 프로그램에서 모형화될 수 있는 형태로 표현되어야만 한다. 어떤 이론이 여러가지 이유들 때문에 조건을 만족시키지 못할 수도 있다. 즉 이론이란 불완전할 수도 있고, 계산 가능하지 않은 과정에 의존적일 수도 있으며, 비일관적이거나 통합성이 없을 수도 있고, 아니면 신비주의처럼 당연히 옳은 것으로 전제하는 것이 많기 때문에 그 이론에 대한 신봉자들에게만 이해되는 수도 있다. 이러한 결함들이 항상 분명한 것은 아니다. 마음을 연구하는 학생들은 자기들이 지금 무엇에 대해 이야기하고 있는지 모른다는 사실을 알지 못하는 때가 있다. 이러한 것을 발견해 내는 가장 확실한 방식은 이론을 모델화하는 컴퓨터 프로그램을 고안하도록 노력하는 것이다. 컴퓨터 모델을 만드는 작업은 직관에 의존하는 정도를 최소화할 수 있다. 컴퓨터 모델로 구체화한 이론이 잘못되는 경우는 있지만, 적어도 일관적이며 너무 많은 것을 가정하지는 않는다. 컴퓨터 프로그램은 기본입자들의 상호작용이나 미생물학적 기제, 국가 경제 등을 모형화한다. 이 책의 나머지에서는 인간의 마음에 대한 계산이론들에 대해 다루게 된다.
읽을거리
튜링 (1936)의 계산모형에 관한 논문은 아주 전문적이다. 전문지식이 없는 사람들에게 권할 수 있는 짧고 아주 좋은 소개서는 트락텐브로트 (Trakhtenbrot, 1936) 의 책이다. 문법과 계산과의 관계는 촘스키 (1959) 의 논문에서 볼 수 있다. 튜링 (1950) 의 논문에서는 기계가 사고할 수 있는지에 대한 물음을 읽기 쉽게 제안하였다. 그가 이 문제를 결론지을 수 있다고 보았던 단 하나의 방식은 조합적 검증, 즉 <사람들이 컴퓨터와 인간과의 차이를 알 수 없을 만큼 컴퓨터가 인간의 수행을 잘 모방할 수 있는가?> 를 검증하는 것이었다. 이러한 문제들은 호프스태터 (Hofstadter, 1979) 의 책에서 재미있게 논의되고 있다.