3.1 계산 모델

알고리즘 개념을 수학적으로 정확하게 공식화하는 것이 목표

힐베르트 결정 문제 entscheidugsproblem 의 답은 아니오로 밝혀졌다. 모든 수학 문제를 해결하는 알고리즘은 없다. 이를 증명하기 위해 처치와 튜링은 알고리즘의 직관적 개념을 사용할 때 의미하는 바를 수학 정의로 잡아내는 심층 문제를 해결해야 했다. 그런 작업을 통해 그들은 현대 알고리즘 이론과 그에 따른 컴퓨터 과학의 현대 이론에 대한 토대를 마련했다.

3.1.1 튜링 머신

튜링 먼신의 기본 요소는 네 가지

• 일반 컴퓨터와 같은 프로그램
• 핵심 기능만 갖춘 기계의 각 동작을 조정하는 유한상태 제어장치 finite state control
• 컴퓨터 메모리의 역할을 하는 테이프
• 읽거나 쓰기 가능한 테이프의 위치를 가리키는 읽기/쓰기 테이프 헤드

유한 상태 제어장치는 내부 상태인 q_1, q_m 의 유한집합으로 구성된다. 숫자 m 은 변할 수 있다. 충분히 큰 m 에 대해 머신의 성능에 영향을 미치지 않으므로 일반화시켜 고정된 상수로 가정한다.

유한 상태 제어장치를 생각하는 가장 좋은 수단은 튜링머신의 작동을 조정하는 일종의 마이크로프로세서이다. 이는 테이프에 임시 저장 공간을 제공하고 머신의 모든 처리를 수행할 수 있는 중심 장소도 된다.

이 외에도 q_s, q_h 라는 2개의 특수 내부 상태가 있다. 이를 각각 시작 샅애와 정지 상태라고 한다. 이것의 의도는 계산 시작 시 튜링 머신은 시작 상태에 있게 된 계산을 실행하면 내부상태가 변한다. 계산이 완료되면 q_h 상태가 되어 연산ㅇ을 완료 했음을 나타낸다.

튜링머신 테이프는 1차원 물체로 무한대로 뻗어 있다. 이는 정사각 테이프를 연결한 것, 

요약하면 q_s 상태의 유한상태 제어장치로 시작하며 0 번으로 정한 가장 왼쪽의 정사각 테이프에 읽기/쓰기 헤드를 위치시키고 연산을 시작한다. 그러고 나서 프로그램에 따라 한 단계씩 계산이 진행된다. 현재 상태가 q_h 이면 계산이 정지되고 계산 출력은 이 테이프의 현재 내용이 된다.

 

튜링머신용 프로그램은 (q, x, q', x', s) 형식의 프로그램 행으로 구성된 순서 있는 유한목록이다. 

q 는 머신의 내부상태 집합 중에서 한 상태다.

x 는 테이프에 나타낼 기호들의 알파벳, 

프로그램이 작동하는 방식은 각 머신 사이클마다 튜링머신이 프로그램 행 목록을 순서대로 살펴보고 머신의 현재 내부상태가 q 이고 테이프에서 읽는 기호가 x 를 만족시키는 행을 찾는다. 그러한 행을 찾지 못하면 정지한다. 행을 찾을 시 해당 행이 실행, 

먼저 머신의 내부 상태는 q' 로 변경, 테이프의 x 기호는 x' 기호로 덮어쓰기되며, s 의 값에 따라 테이프 헤드가 왼쪽, 오른쪼긍로 이동하거나 정지 상태가 된다. 

튜링 머신의 다음 예를 고려,  

맨 처음이 2 진수 x 이고, 그 다음에 나오는 공백이 나오는 테이프로 시작한다. 머신에는 시작상태와 정지상태 외의 세 가지 내부상태가 있다. 

처음에 머신은 1행이 실행된다. 기록된 내용을 변경하지 않고 오른쪽으로 이동, 머신의 내부 상태를 q_1 로 변경, 

...

 

다양한 함수를 계산하는 데 튜링머신 계산모델을 사용할 수 있다는 것이 입증되었다. 튜링머신으로 모든 작업을 시뮬레이션할 수 있다. 

튜링머신의 계산모델은 알고리즘을 사용해 함수를 계산하는 개념을 완벽히 구현할 수 있다. 이 점은 처치-튜링 논제라 한다. 

튜링머신으로 계산 가능한 함수 클래스는 알고리즘으로 계산 가능할 것으로 자연스레 여겨지는 함수 클래스에 정확히 대응한다.

처치-튜링 논제는 엄밀한 수학적 개념과 알고리즘으로 계산 가능한 함수에 대한 직관적 개념이 서로 같다고 주장한다. 

이 점의 의의를 이해하려면 실제 분석에서 연속 함수 continuous functoin 의 정의를 고려하는 것이 도움된다. 

연속성 또는 계산 가능성 computability 과 같은 근본적인 정의를 내릴 때는 사람의 직관적 개념이 수학적 정의와 잘 일치하게 하면서 올바른 정의를 선택하는 것이 중요하다. 

선험적인 면에서 알고맂므으로 계산 가능하게 보이는 모든 함수를 튜링 머신으로 계산할 수 있는 점은 분명치 않다. 

 

확인 문제 3.1 : (자연 속에서의 계산 불가능한 프로세스) : 자연 속의 프로세스가 튜링 머신으로 계산 불간으한 함수를 계산해낸다는 것을 어떻게 알 수 있을까?

확인 문제 3.2  : (튜링 번호) 단일 테이프의 튜링머신들마다 1,2,3... 목록 중에서 한 번식 부여할 수 있다는 것을 보여라. 이때 그 번호는 해당 머신을 유일하게 지정해야 한다. 이 번호를 해당 튜링머신의 튜링 번호라 한다. 

양자 컴퓨터도 처치-튜링 논제를 따른다. 즉, 양자 컴퓨터는 튜링 머신에서 계산 간으한 것과 같은 클래스의 함수를 계산할 수 있다. 그 차이는 함수 계산의 효율성에 있다. 

 

기본 튜링머신 모델에서는 많은 변형이 존재, 테이프 종류가 다른 튜링 머신, 

기본 튜링머신과 2테이프 튜링 머신이 서로 같은 계산 모델일까? 각 계산모델이 서로 다른 쪽 계산모델을 시뮬레이션 할 수 있다는 의미에서 이 둘은 같다. 

 

튜링머신의 또 다른 변형은 이 모델에 무작위성을 도입하는 것, 계산 가능한 함수 클래스가 변경되지는 않는다.

 

힐베르트의 결정문제, 수학의 모든 문제를 결정하는 알고리즘이 존재하지 않는다.

이러한 결정불가성의 현상은 처치와 튜링이 만든 한 예를 뛰어넘어선 것으로 알려졌다. 예를 들어 두 위상공간이 동등한지를 결정하는 문제는 결정 불가능한 것으로 알려져 있다. 

결정 불간으한 동적 계의 거동과 관련된 간단한 문제들이 있다. 

결정불가성은 그 본래의 관심사 외의 양자 계산 및 양자 정보에서도 큰 관심의 주제를 예고한다. 

 

3.1.2 회로

튜링머신은 이상적인 계산장치 모델에 가빠다. 실제 컴퓨터는 크기가 한정돼 있지만 ㅠㅌ링머신의 경우 무제한 크기의 컴퓨터로 가정, 

대아능로 계산모델인 회로 모델, 이 모델은 계산 능력 측면에서 튜링머신과 동등하지만 더 편리하고 현실적이다. 

회도는 도선 wire 와 게이트 gate 로 구성, 각각 정보를 전달하고 계산 작업을 수행한다. 

이 비트는 NOT 게이트를 통과해 1에서 0으로, 0에서 1로 비트를 바꾼다. 

도선은 공간 속에서 비트의 이동을 나타내거나 단순이 시간에 따른 비트의 이동을 나타낼 수도 있다.

좀 더 일반적으로 회로에는 입력과 출력 비트, 도선, 논리 게이트들이 많이 포함될 수 있다. 

논리 게이트란 어떤 고정된 수 k 개의 입력 비트에서 어떤 고정된 수 l 개의 출력 비트로 가는 함수를 의미한다. 

루프를 허용하지 않는 회로를 비순환적이라 하며, 계산 회로 모델에서의 회로는 비순환적으로 구성하는 관례를 따른다.

 

AND, OR, XOR, NAND, NOR 게이트는 2개의 비트를 입력으로 받아 하나의 비트를 출력으로 생성한다. 

AND 는 두 입력이 모두 1인 경우 1,

OR 는 두 입력 중 하나 이상이 1인 경우에만 1, 

XOR 은 두 입력을 모듈러 2에 관해 더해서 출력

NAND와 NOR 은 두 입력에 AND 와 OR 을 적용한 후 출력된 것에 ,NOT 를 적용한다. 

 

회로 속에서는 비트를 분할하기도 하는데, 한 비트를 분할해서 2개 비트의 복사본으로 만드는 연산을 팾ㄴ아웃이라 한다. 또한 두 비트를 크로스오버 연산할 수도 있는데, 두 비트의 값을 서로 교환한다. 

 

회로 요소들을 조합하면 다양한 계산을 수행할 수 있다.