FRACTRAN

FRACTRAN은 수학자 존 호턴 콘웨이가 고안한 난해한 프로그래밍 언어이다. FRACTRAN 프로그램은 양의 분수들로 이루어진 하나의 목록의 형태이다. 이 프로그램은 다음의 규칙으로 자연수 입력값 n을 갱신하며 작동한다.

1. 목록의 분수들 중에서 nf가 자연수인 가장 첫번째 분수가 f일 때, 입력값 n을 nf로 바꿔쓴다.
2. 더 이상 nf가 자연수인 분수 f가 없을때까지 위 과정을 반복한 후, 프로그램을 정지한다.

간단한 FRACTRAN 프로그래밍 예제

FRACTRAN 프로그램은 괴델 넘버링을 사용해 입력값과 출력값을 하나의 소인수분해로 표현한다. 예를 들어 a=2, b=1, c=1 을 입력하면

$2^{2}\times 3^{1}\times 5^{1}$

와 같은 형태로 표현한다

덧셈 프로그램

a와 b를 입력하면 a+b를 출력하는 프로그램은 다음과 같다

$\left({\frac {3}{2}}\right)$

이 프로그램은 다음 알고리즘을 따른다.

	상태	행동
${\frac {3}{2}}$	2의 지수>0	2의 지수에서 1을빼고 3의 지수에 1을 더한다
	2의 지수 = 0	정지

a와 b를 입력하면 다음과 같은 소인수분해 $2^{a}3^{b}$가 입력된다, 이 프로그램은 다음과 같은 수열 $2^{a-1}3^{b+1}$, $2^{a-2}3^{b+2}$...을 생성하다가, 결국에 $3^{a+b}$ 곧, $a+b$를 출력한다.

뺄셈 프로그램

a와 b를 입력하면 a-b를 출력하는 프로그램은 다음과 같다.

$\left({\frac {1}{6}}\right)$

최댓값 구하기 프로그램

a와 b를 입력하면 a와 b중 더 큰 값을 출력하는 프로그램은 다음과 같다

$({\frac {5}{6}},{\frac {5}{2}},{\frac {5}{3}})$

소수 생성 프로그램

다음은 존 콘웨이가 제시한 소수 생성 프로그램이다.

$\left({\frac {17}{91}},{\frac {78}{85}},{\frac {19}{51}},{\frac {23}{38}},{\frac {29}{33}},{\frac {77}{29}},{\frac {95}{23}},{\frac {77}{19}},{\frac {1}{17}},{\frac {11}{13}},{\frac {13}{11}},{\frac {15}{2}},{\frac {1}{7}},{\frac {55}{1}}\right)$

n=2를 입력하면,이 프로그램은 다음과 같은 수열

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (OEIS의 수열 A007542)

을 생성하다가, 2의 소수 거듭제곱을 포함한다.

$2^{2}=4,\,2^{3}=8,\,2^{5}=32,\,2^{7}=128,\,2^{11}=2048,\,2^{13}=8192,\,2^{17}=131072,\,2^{19}=524288,\,\dots$ (OEIS의 수열 A034785)

곱셈 프로그램

두 자연수 a,b를 입력했을 때, ab를 출력하는 프로그램은 다음과 같다.

$\left({\frac {455}{33}},{\frac {11}{13}},{\frac {1}{11}},{\frac {3}{7}},{\frac {11}{2}},{\frac {1}{3}}\right)$

FRACTRAN프로그램으로 3곱하기2을 계산하는 과정,a=3,b=2를 괴델 수 $2^{3}3^{2}$로 변환 후 입력하여, 괴델 수 $5^{6}$,곧 6을 출력한다.

피보나치 프로그램

피보나치 수열을 생성하는 프로그램은 다음과 같다.

$\left({\frac {33}{91}},{\frac {13}{11}},{\frac {11}{1}},{\frac {34}{399}},{\frac {19}{17}},{\frac {17}{1}},{\frac {7}{2}},{\frac {5}{187}},{\frac {3}{1}}\right)$

참고 문헌

• Havil, Julian (2007). 《Nonplussed!》. Princeton University Press. ISBN 0-691-12056-0. 
• Conway, John (2010). 〈FRACTRAN: A simple universal programming language for arithmetic〉. Jeffrey C. Lagarias. 《The Ultimate Challenge: the 3x+1 problem》. American Mathematical Society. 249–264쪽. ISBN 978-0-8218-4940-8. Zbl 1216.68068. 
• Roberts, Siobhan (2015). 〈Criteria of virtue〉. 《Genius At Play - The Curious Mind of John Horton Conway》. Bloomsbury. 115–119쪽. ISBN 978-1-62040-593-2. 
• Conway, John H. (1987). 《Open Problems in Communication and Computation》. Springer-Verlag New York, Inc. ISBN 978-1-4612-9162-6. 

외부 링크

• "Prime Number Pathology: Fractran"
• Weisstein, Eric Wolfgang. “FRACTRAN”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Prime Number Pathology
• FRACTRAN - (Esolang wiki)
• Ruby implementation and example programs
• Project Euler Problem 308
• "Building Fizzbuzz in Fractran from the Bottom Up"
• Chris Lomont, "A Universal FRACTRAN Interpreter in FRACTRAN"