곱셈만으로 튜링 완전성을 달성하는 FRACTRAN 언어

FRACTRAN은 튜링 머신(Turing Machine)의 대안으로, 곱셈과 분수를 사용하여 계산을 수행하는 언어이다. 소수를 레지스터(Registers)로 활용하여, 소수의 지수를 통해 값을 저장하고 연산을 수행한다. 특히, FRACTRAN은 정수를 입력과 출력으로 사용하며, 로그의 법칙(Laws of Logarithms)을 기반으로 연산을 수행한다는 특징을 가진다.

FRACTRAN 인터프리터는 C 언어로 구현될 수 있으며, 약 30줄의 코드로 구성된다. 인터프리터는 시작 정수, 분수 배열, 결과 배열 등을 입력으로 받는다. 덧셈, 곱셈, 곱셈-덧셈 연산(Addition, Multiplication, Multiply-Add)을 수행하는 예시 프로그램이 제공되며, 이를 통해 FRACTRAN의 연산 방식을 이해할 수 있다. 실제 사례로는, 2+3=5를 계산하기 위해 소수 2와 3을 레지스터로 사용하고, 2^3 * 3^2 = 72를 시작 값으로 설정한다.

Geipel(2017)의 연구에 따르면, FRACTRAN 프로그램의 실행 속도를 10배 향상시키는 기법이 존재한다. 이 기법은 사이클 감지(Cycle Detection)를 통해 반복되는 연산을 건너뛰는 방식으로 작동한다. 특히, 데이터 레지스터와 로직 레지스터를 구분하여, 사이클 매칭(Cycle Matching)을 효율적으로 수행한다. 이러한 최적화는 FRACTRAN 프로그램의 실행 시간을 단축하는 데 기여한다.

커뮤니티에서는 FRACTRAN을 '수학 시험 문제와 같은 코드'로 묘사하며, 콘웨이(Conway)의 독창적인 아이디어에 대한 경외심을 표현한다. FRACTRAN은 튜링 완전성을 곱셈과 분수만으로 달성한다는 점에서 이론적인 흥미를 유발하며, 컴퓨터 과학(Computer Science) 분야에 대한 새로운 시각을 제시한다. 또한, FRACTRAN의 간결함은 프로그래밍 언어 설계(Programming Language Design)에 대한 영감을 제공할 수 있다.