제논 기계

수학과 컴퓨터 과학에서 제논 기계 또는 제논 머신(Zeno machine, 약어 ZM, 또는 가속 튜링 기계, accelerated Turing machine, ATM)는 셀 수 있는 무한한 수의 알고리즘 단계를 포함하는 계산을 수행할 수 있는 튜링 기계와 관련된 가설적인 계산 모델이다. 이러한 기계는 대부분의 계산 모델에서 배제된다.

제논 기계의 아이디어는 1927년 헤르만 바일에 의해 처음 논의되었다. 이 이름은 고대 그리스 철학자 엘레아의 제논의 이름을 딴 제논의 역설을 참조한다. 제논 기계는 일부 이론에서 중요한 역할을 한다. 예를 들어, 물리학자 프랭크 J. 티플러가 고안한 오메가 점 이론은 제논 기계가 가능해야만 유효할 수 있다.

 정의 

제논 기계는 무한한 단계를 거친 후에도 계속해서 더 많은 단계를 거칠 수 있는 튜링 기계이다. 이것은 번째 단계를 수행하는 데  단위의 시간이 소요되는 초과업으로 생각할 수 있다. 따라서 첫 번째 단계는 0.5단위의 시간, 두 번째 단계는 0.25단위, 세 번째 단계는 0.125단위 등으로 진행되어 1단위의 시간 후에는 셀 수 있는 무한한 수의 단계가 수행될 것이다.

 무한 시간 튜링 기계 
섬네일|400px|right|톰슨의 램프 사고 실험에 기반한 무한 시간 튜링 기계의 애니메이션. 셀은  이전 단계에서 과  사이를 번갈아 바꾼다. 시퀀스가 수렴하지 않으므로 셀은 에서 이 된다.

제논 기계의 보다 공식적인 모델은 무한 시간 튜링 기계이다. 제프리 키더(Jeffrey Kidder)의 미출판 작업에서 처음 정의되고 조엘 햄킨스(Joel Hamkins)와 앤디 루이스(Andy Lewis)에 의해 확장된 "무한 시간 튜링 기계"(Infinite Time Turing Machines)는 고전적인 튜링 기계 모델의 확장으로, 초한 시간, 즉 모든 유한 시간을 넘어선 시간을 포함한다. 고전적인 튜링 기계는 단계에서 상태(시작 상태에서 빈 테이프, 읽기 헤드는 셀 0에 있음)와 연속적인 상태로 이동하는 절차를 가지고 있다. 이런 식으로 튜링 기계의 상태는 자연수에 해당하는 모든 단계에 대해 정의된다. 는 이러한 속성을 유지하지만, 극한 순서수, 즉 도 아니고 어떤 순서수의 후속도 아닌 순서수에서의 기계 상태도 정의한다. 튜링 기계의 상태는 세 부분으로 구성된다.

 상태
 읽기-쓰기 헤드의 위치
 테이프 내용

고전적인 튜링 기계가 프로그램 시작 시의 상태인 레이블이 지정된 시작 상태를 가지는 것처럼, 는 모든 극한 순서수에서의 기계 상태인 레이블이 지정된 극한 상태를 가진다. 이는 기계가 이 상태에 접근할 다른 방법이 없더라도, 예를 들어 노드 전환이 없더라도 마찬가지이다. 읽기-쓰기 헤드의 위치는 모든 극한 단계에서 0으로 설정된다. 마지막으로 테이프의 상태는 이전 테이프 상태의 상극한에 의해 결정된다. 어떤 기계 , 셀 , 그리고 극한 순서수 에 대해

즉, 시간 에서의 번째 셀은 기계가 에 접근함에 따라 같은 셀의 상극한이다. 이는 수렴하면 극한으로, 그렇지 않으면 로 생각할 수 있다.

 계산 가능성 

제논 기계는 고전적인 튜링 기계의 정지 문제를 해결할 수 있는 능력을 바탕으로 고전적인 튜링 기계보다 더 강력한 계산 모델로 제안되었다. 크리스티안 칼루드(Cristian Calude)와 루트비히 슈타이거(Ludwig Staiger)는 제논 기계에서 실행될 때 정지 문제에 대한 해결책으로 다음 의사코드 알고리즘을 제시한다.

 프로그램 시작
     출력 테이프의 첫 번째 위치에 0을 쓴다.
     루프 시작
         주어진 입력에 대해 주어진 튜링 기계의 연속적인 1단계를 시뮬레이션한다.
         만약 튜링 기계가 정지했다면 다음과 같이 한다.
             출력 테이프의 첫 번째 위치에 1을 쓰고 루프를 벗어난다.
     루프 끝
 프로그램 끝

1단위의 시간이 경과한 후 출력 테이프의 첫 번째 위치를 검사하여 주어진 튜링 기계가 정지하는지 여부를 판단할 수 있다.
이와 대조적으로 오론 샤그리르(Oron Shagrir)는 제논 기계의 상태는  구간에서만 정의되므로 시간 에 테이프를 검사하는 것은 불가능하다고 주장한다. 더욱이 고전적인 튜링 기계는 어떤 타이밍 정보도 가지고 있지 않으므로, 가속하든 안 하든 타이밍 정보를 추가하는 것 자체가 계산 능력을 추가하지 않는다.

그러나 무한 시간 튜링 기계는 초한 단계에 대한 상태를 정의하므로, 주어진 알고리즘을 구현할 수 있으며 올바른 해결책과 함께 시간 에 정지한다. 모든  집합은 무한 시간 튜링 기계에 의해 결정 가능하며,  집합은 반결정 가능하다.

제논 기계는 자체 정지 문제를 해결할 수 없다.

 같이 보기 
 극한에서의 계산
 슈페커 수열
 로스-리틀우드 역설

 각주 

분류:튜링 기계
분류:계산 모형