FRACTRAN

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

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

간단한 FRACTRAN 프로그래밍 예제

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

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

와 같은 형태로 표현한다

덧셈 프로그램

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

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

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

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

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

뺄셈 프로그램

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

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

최댓값 구하기 프로그램

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

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

소수 생성 프로그램

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

${\displaystyle \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의 소수 거듭제곱을 포함한다.

${\displaystyle 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를 출력하는 프로그램은 다음과 같다.

${\displaystyle \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를 괴델 수 ${\displaystyle 2^{3}3^{2}}$로 변환 후 입력하여, 괴델 수 ${\displaystyle 5^{6}}$,곧 6을 출력한다.

피보나치 프로그램

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

${\displaystyle \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)}$

같이 보기

• 콜라츠 추측